[frames] | no frames]

# Module convex_hull2d

source code

convexhull.py

Calculate the convex hull of a set of n 2D-points in O(n log n) time. Taken from Berg et al., Computational Geometry, Springer-Verlag, 1997. Prints output as EPS file.

When run from the command line it generates a random set of points inside a square of given length and finds the convex hull for those, printing the result as an EPS file.

Usage: convexhull.py <numPoints> <squareLength> <outFile>

Dinu C. Gherman

Small Bug: Only works with a list of UNIQUE points, Evan Jones, 2005/05/18 If the list of points passed to this function is not unique, it will raise an assertion. To fix this, remove these lines from the beginning of the convexHull function:

Taken from http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66527 and modified to work with complex numbers.

 Classes DuplicatePoints
Functions

 saveAsEps(P, H, boxSize, path) Save some points and their convex hull into an EPS file. source code

 convexHull(P) Calculate the convex hull of a set of complex points. source code

 test() source code
 Variables epsHeader = `'%%!PS-Adobe-2.0 EPSF-2.0\n%%%%BoundingBox: %d %d ...` __package__ = `'gmisclib'`

Imports: sys, random

 Function Details

### convexHull(P)

source code

Calculate the convex hull of a set of complex points. If the hull has a duplicate point, an exception will be raised. It is up to the application not to provide duplicates.

 Variables Details

 ````'''``%%!PS-Adobe-2.0 EPSF-2.0` `%%%%BoundingBox: %d %d %d %d` `/r 2 def %% radius` `/circle %% circle, x, y, r --> -` `{` ` 0 360 arc %% draw circle` `...` ```