Package gmisclib :: Module convex_hull2d
[frames] | no frames]

Module convex_hull2d

source code

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: <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 and modified to work with complex numbers.

saveAsEps(P, H, boxSize, path)
Save some points and their convex hull into an EPS file.
source code
Calculate the convex hull of a set of complex points.
source code
test() source code
  epsHeader = '%%!PS-Adobe-2.0 EPSF-2.0\n%%%%BoundingBox: %d %d ...
  __package__ = 'gmisclib'

Imports: sys, random

Function Details


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