Convex Hulls: Gift Wrapping Algorithm

Math 282 Computational Geometry

Preliminaries

For points a, b, c, in the plane, the signed area of triangle abc is half the cross product (b-a)×(c-a).

signedArea[a_,b_,c_]:=((b[[1]]-a[[1]])(c[[2]]-a[[2]])-(b[[2]]-a[[2]])(c[[1]]-a[[1]]))/2

We can use this to define Boolean functions (i.e., functions that return true or false) to determine whether point c is to the left of directed segment ab or collinear to ab.

leftOf[a_,b_,c_]:=(signedArea[a,b,c] > 0)
leftOn[a_,b_,c_]:=(signedArea[a,b,c] >= 0)
collinear[a_,b_,c_]:=(signedArea[a,b,c]==0)

Gift Wrapping Algorithm

For now, assume that points are in general position (i.e., all x-coordinates are unique and no three points are collinear), and that numerical errors don’t happen.

findLowest

First, we need a subroutine that returns a point guaranteed to be on the convex hull. We choose to find the point with the smallest y-coordinate. If multiple points have the smallest y-coordinate, then we choose the rightmost of them. 
Input: a list of points, given as ordered pairs
Output: the index of the (rightmost) lowest point in the list

findLowest[pts_]:=Module[{n=Length[pts],low},
low=1;
Do[
If[(pts[[i,2]]<pts[[low,2]] )||(pts[[i,2]]==pts[[low,2]] && pts[[i,1]]>pts[[low,1]]),
low=i],
{i,2,n}];
low
]

Try it out:

findLowest[{{1,0},{2,3},{4,-1},{5,-1},{3,3}}]

The gift wrapping algorithm

The following Module implements the gift wrapping algorithm.
Input: a list of points, given as ordered pairs
Output: convex hull of the points, given as a list of ordered pairs, in counterclockwise order

giftWrapping[pts_]:=Module[{startIndex,hull,curIndex,nextIndex,i},
(* start at the "lowest" point *)
startIndex = findLowest[pts];
hull={pts[[startIndex]]};
curIndex=startIndex;

While[True,
(* search for the point that makes the largest angle *)
nextIndex=1;
For[i=2,i≤Length[pts],i++,
If[  !!! write a boolean expression here to complete the algorithm  !!! ,
nextIndex=i];
];
curIndex=nextIndex;

(* quit if we are back to the starting point *)
If[curIndex==startIndex, Break[]];

(* otherwise, append the next point to the hull *)
AppendTo[hull,pts[[nextIndex]]];

(* TESTING: print the partial hull *)
Print[Graphics[{{Purple,Line[hull]},{Blue,PointSize[0.02],Point[pts]}},Frame->True,ImageSize->Small]]
];
hull
]

Try it out:

pts=RandomReal[{0,10},{50,2}];

giftWrapping[pts]

Exercises

Complete the code above.

Analyze the runtime of the gift wrapping algorithm experimentally.

What configuration of points results in worst-case runtime?

What configuration of points results in best-case runtime?