Template chull_check documentation

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

General description:

The template chull_check receives as input two arrays of points, varray and parray. It returns 1 if varray contains the extremal vertices listed in counter-clockwise order of the convex hull of all the points in varray and parray. Otherwise, it returns 0.

Algorithm:

The algorithm is divided into two parts. The first part, chull_check_ext, checks that points in an array varray are the extremal vertices of their convex hull listed in counter-clockwise order. The second part, chull_check_int, checks that points in an array parray are in the interior or on the boundary of the convex hull of the points in array varray. The second part has a precondition that points in array varray are the extremal vertices of their convex hull listed in counter-clockwise order.

varray = array [1:numv] of points
parray = array [1:nump] of points

numv = number of points in varray
nump = number of points in parray

chull_check(parray, nump, varray, numv)

if (chull_check_ext(varray, numv) == 0) return(0);
if (chull_check_cont(varray, numv, parray, nump) == 0) return(0);
return(1);

chull_check_ext(varray, numv)

if (numv < 2), then return(1);
if (numv == 2), then

if (varray[1] == varray[2]), then return(0); /* identical points */
else return(1);

for i = 1 to (numv-2) do

if (varray[i], varray[i+1], varray[i+2]) have right orientation or are collinear, then return(0);

if (varray[numv], varray[1], varray[2]) have right orientation or are collinear, then, return(0);
if (varray[numv-1], varray[numv], varray[1]) have right orientation or are collinear, then return(0);
for i = 2 to (numv-1) do

if (varray[1], varray[i], varray[i+1]) have right orientation or are collinear, then return(0);

return(1);

chull_check_cont(varray, numv, parray, nump)
/* Precondition: points in varray[1..numv] are extremal vertices of their convex hull listed in counter-clockwise order */

if (nump == 0), then return(1);
if (numv > 2), then

for i = 1 to nump do

if (varray[1], varray[2], parray[i]) have right orientation, then return(0);
j <- index of first vertex in varray[3,numv] such that (varray[1], varray[j], parray[i]) have right orientation or are collinear (or j <- numv+1 if there is no such j);
if (j == numv+1), then return(0); /* (varray[1], varray[numv], parray[i]) have left orientation */
if (varray[j-1], varray[j], parray[i]) have right orientation, then return(0);

else if (numv == 0), then return(0);
else if (numv == 1) then

for i = 1 to nump do

if (parray[i] != varray[1]), then return(0):

else /* (numv == 2) */

for i = 1 to nump do

if the x-coordinate of parray[i] does not lie on or between the x-coodinates of varray[1] and varray[2], then return(0);
if (varray[1], varray[2], parray[i]) are not collinear, then return(0);

return(1); /* passed all checks */

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 firstv = iterator to first element in vertex array [firstv, endv);
POINT_ITER endv = iterator to element after (past-the-end of) last element in vertex array [firstv,endv);

Array [firstv,endv) is an array of points in the real plane;

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;

int & failnum = failure number encoding type of failure;
POINT_ITER & failv = vertex in vertex array causing check to fail (exact interpretation depends on type of failure);

(firstv <= fail < endv) or (failv == 0);

POINT_ITER & failp = point in point arraycausing check to fail (exact interpretation depends on type of failure).

(firstp <= failp < endp) or (failp == 0);

Alters:

failnum, failv, failp.

Requires (preconditions):

firstv <= endv;
firstp <= endp;
Arrays [firstv,endv) and [firstp,endp) are arrays 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):

returns (1) if the points [firstv,endv) are extremal vertices listed in counter-clockwise order of the convex hull of ([firstv,endv) union [firstp,endp));
otherwise, returns (0).

Calls routines:

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

Version:

Version 1.0.

Authors & credits:

Created by R. Wenger.

Last updated by R. Wenger: 14 May 1999