ChapterZero

I wanted to give PyCairo programming a go, and I’ve always been fascinated by some of the simple but important issues in computational geometry, like Voronoi diagrams and Delaunay triangulations, or in this case, calculating the boundary of the convex hull of a set of points.

Here’s the code: framework.py and convex_hull.py; PyGtk and PyCairo are required. The interface is basic: you enter points by clicking in the window, and the program updates the convex hull and its boundary as you add the points (you can resize the window during operation if you really want to pack in the points … to verify the probably exponential running time of the algorithm ).

The algorithm used to find the boundary is painfully obvious in hindsight: if an edge connecting two points in the set is such that all the points in the set lie to one side of it, then that edge is on the boundary of the hull.

My next goal is to orient the boundary– an algorithm for this follows immediately from an algorithm for the orientation of the boundary of a generic triangle, but I haven’t yet found a suitable algorithm. All the algorithms I’ve come up with seem forced, and more important, hairy to code.

(While I’m talking about Python and mathematical graphics, check Ghost Diagram out for a beautiful and more serious example of the possibilities)