chull.h File Reference

Convex hull algorithm. More...

#include "point.h"

Go to the source code of this file.

Functions
int	mlib::convex_hull (dpoint *P, int n)
	Find convex hull for an array of points.

Detailed Description

Convex hull algorithm.

http://cm.bell-labs.com/who/clarkson/2dch.c

Ken Clarkson wrote this.  Copyright (c) 1996 by AT&T..
Permission to use, copy, modify, and distribute this software for any
purpose without fee is hereby granted, provided that this entire notice
is included in all copies of any software which is or includes a copy
or modification of this software and in all copies of the supporting
documentation for such software.
THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.

Function Documentation

convex_hull()

int mlib::convex_hull	(	dpoint *	P,
		int	n
	)

Find convex hull for an array of points.

Parameters

P	points array
n	number of points

Returns

number of points in the convex hull

If r is the number of points returned by this function, the input array is rearranged so that the first r points make the convex hull.

Works in O(n log n); I think a bit faster than Graham scan; somewhat like Procedure 8.2 in Edelsbrunner's "Algorithms in Combinatorial Geometry", and very close to:

A.M. Andrew, "Another Efficient Algorithm for Convex Hulls in Two Dimensions",
 Info. Proc. Letters 9, 216-219 (1979)

(See also http://geometryalgorithms.com/Archive/algorithm_0110/algorithm_0110.htm)

The results should be "robust", and not return a wildly wrong hull, despite using floating point.