Python Cookbook

Module: Finding the Convex Hull of a Set of 2D Points

Credit: Dinu C. Gherman

Convex hulls of point sets are an important building block in many computational-geometry applications. Example 17-1 calculates the convex hull of a set of 2D points and generates an Encapsulated PostScript (EPS) file to visualize it. Finding convex hulls is a fundamental problem in computational geometry and is a basic building block for solving many problems. The algorithm used here can be found in any good textbook on computational geometry, such as Computational Geometry: Algorithms and Applications, 2nd edition (Springer-Verlag). Note that the given implementation is not guaranteed to be numerically stable. It might benefit from using the Numeric package for gaining more performance for very large sets of points.

Example 17-1. Finding the convex hull of a set of 2D points

""" 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. Emits 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, emitting the result as an EPS file. Usage: convexhull.py <numPoints> <squareLength> <outFile> Dinu C. Gherman """ import sys, string, random # helpers def _myDet(p, q, r): """ Calculate determinant of a special matrix with three 2D points. The sign, - or +, determines the side (right or left, respectively) on which ...