Template chull_2pass documentation

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

General description:

The template chull_2pass reorders an array of points so that vertices of the convex hull of the points are listed in counter-clockwise order at the beginning of the array. It is a variation of an algorithm by Andrew (IPL, 1979) which is based on an algorithm by Graham (IPL, 1972.) This variation, by de Berg, van Kreveld, Overmars, Schwarzkopf (Computational Geometry, 1997,) makes two passes
over the set of points, one to construct the lower hull and another one to construct the upper hull.

Algorithm:

parray = array [1:nump] of points

nump = number of points in parray

Reorder points in parray[1:nump] so that they are sorted by increasing x-coordinate (break ties by increasing y-coordinate);
m <- 2;
i <- 3;
while (i <= imax) do

while (m > 1) and (parray[m-1], parray[m], parray[i]) have left orientation or are collinear do

m <- m-1;

m <- m+1;
Switch parray[m] and parray[i];
i <- i+1;

/* find vertices of the upper convex hull */

imax <- m;
Reorder points in parray[i:nump] so that they are sorted by decreasing x-coordinate (break ties by decreasing y-coordinate);
while (i <= nump) do

while (m > imax) and (parray[m-1], parray[m], parray[i]) have left orientation or are collinear do

m <- m-1;

m <- m+1;
Switch parray[m] and parray[i];
i <- i+1;

while (m > imax) and (parray[m-1], parray[m], parray[1]) have left orientation or are collinear do

m <- m-1;

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:

iter_swap (Standard Template Library);
sort (Standard Template Library).

Version:

Version 1.0.

Authors & credits:

Created by R. Wenger.

Last updated by R. Wenger: 14 May 1999