Computational geometry demos

Most of these are quick hacks to demonstrate that an algorithm described in some paper actually can be implemented, or can be implemented to run in the given time. Some include rudamentary animations.

Even on my hacks, I try to be careful about correctly handling degenerate cases. If you see errors, turn on Detail, take a snapshot of the screen and java console (e.g., with xv on unix systems) and send it to me.

These algorithms do not take the time to verify properties that they expect of the input---e.g., no duplicated points, simple polygons should not have intersections and should always be oriented counterclockwise (CCW). Input that violates these assumptions, therefore, will cause strange results or error messages on the Java console. (I have tried to catch all infinite loops)

Convex hulls in 2d

These take a set of points (or generate random points) and compute the convex hull by different algorithms. The java console shows statistics on the number of various operations. Since moar of these applets share some essential code, it happens (in Netscape at least) that you can enter a point set in one and compute the convex hull with each of the others just by going to the page and clicking the applet's Update button.

Algorithms on simple polygons


Arrangements in the plane

Page maintained by Jack Snoeyink, last name at cs (computer science). unc (u of north carolina). edu (educational)