Template chull_graham documentation

• General description;
• Algorithm;
• Template parameters;
• Arguments;
• Alters;
• Requires (precondition);
• Ensures (postcondition);
• Calls routines;
• Notes;
• Version;
• Authors & credits.

General description:

Algorithm:

nump = number of points in parray

1. pmin <- point with min x-coordinate (break ties by min y coordinate);
2. pmax <- point with max x-coordinate (break ties by max y coordinate);
3. Reorder the points in parray so that:
• pmin is the first point in parray;
• followed by the points below or on the line from pmin to pmax;
• followed by pmax;
• followed by the points above the line from pmin to pmax.


/* find vertices of the lower convex hull */

4. imax <- index of pmax in parray (i.e., pmax = parray[imax]);
5. Reorder points in parray[2:imax-1] so that they are sorted by increasing x-coordinate (break ties by increasing y-coordinate);
6. m <- 2;
7. i <- 3;
8. while (i <= imax) do
1. while (m > 1) and (parray[m-1], parray[m], parray[i]) have left orientation or are collinear do
1. m <- m-1;
2. m <- m+1;
3. Switch parray[m] and parray[i];
4. i <- i+1;


/* find vertices of the upper convex hull */

9. imax <- m;
10. Reorder points in parray[i:nump] so that they are sorted by decreasing x-coordinate (break ties by decreasing y-coordinate);
11. while (i <= nump) do
1. while (m > imax) and (parray[m-1], parray[m], parray[i]) have left orientation or are collinear do
1. m <- m-1;
2. m <- m+1;
3. Switch parray[m] and parray[i];
4. i <- i+1;
12. while (m >  imax) and (parray[m-1], parray[m], parray[1]) have left orientation or are collinear do
1. m <- m-1;
/* final value of m = number of convex hull points */

Template parameters:

• POINT_ITER = type of random access iterator to point array
• POINT = point type.  POINT_ITER = (POINT *)
• ORESULT = type returned by orientation function orient
• Scalar, i.e., integer, float, double, etc.
• Could also be some user defined scalar type.

Arguments:

• POINT_ITER firstp = iterator to first element in point array [firstp, endp);
• POINT_ITER endp = iterator to element after (past-the-end of) last element in point array [firstp,endp);
• Array [firstp,endp) is an array of points in the real plane;
• bool (*compare) (POINT & p1, POINT & p2) = point comparison function
• return 1 if (p1.x < p2.x) or (p1.x == p2.x and p1.y < p2.y);
• return 0 otherwise;
• ORESULT (*orient) (POINT & p1, POINT & p2, POINT & p3) = function to determine orientation
• returns scalar value of type ORESULT;
• returns value > 0 if (p1,p2,p3) have left (negative) orientation;
• returns value < 0 if (p1,p2,p3) have right (positive) orientation;
• returns 0 if (p1,p2,p3) are collinear;
• POINT_ITER & endc = iterator to element after (past-the-end of) last  convex hull vertex.
• Upon termination, array [firstp, endc) contains the convex hull vertices listed in counter-clockwise order.

Alters:

• Reorders elements of point array [firstp,endp);
• endc.

Requires (preconditions):

• firstp <= endp;
• Array [firstp,endp) is an array of points in the real plane;
• (Note: The x and y coordinates of points are never directly accessed and need not be explicitly stored.)

Ensures (postconditions):

• The elements of the array [firstp,endp) are a permutation of the elements of the initial array #[firstp,endp);
• firstp <= endc <= endp;
• If (firstp < endp), then (firstp < endc);
• If (*ip1.x != *ip2.x) or (*ip1.y != *ip2.y) for some POINT_ITER ip1, ip2, where (firstp <= ip1 < ip2 < endp), then
• firstp + 1 < endc;
• For every POINT_ITER ip1, ip2, ip3 where (firstp <= ip1 < ip2 < ip3 < endc),
• orient(*ip1, *ip2, *ip3) > 0;
• For every POINT_ITER ip, where (firstp <= ip < endp),
• *ip is in the convex hull of [firstp,endc).

Calls routines:

• min_element  (Standard Template Library);
• max_element  (Standard Template Library);
• iter_swap (Standard Template Library);
• sort (Standard Template Library).

Notes:

• The lower and upper convex hulls are constructed separately to improve robustness and ensure that point pmax is reported as a convex hull point.

Version:

• Version 1.0.

Authors & credits:

Last updated by R. Wenger: 14 May 1999