Intersection Problems

"Science is all metaphor." - Timothy Leary

"The more simple any thing is, the less liable it is to be disordered."

Thomas Paine 1776 (from Common Sense)

"Complexity does not necessarily imply disorder." - Philip Ball

Read Eric Plante's Tutorial on the rotating-caliper method for intersecting two convex polygons. His page also has a beautiful interactive Java applet you can play with. You can find details and proofs of correctnes of the algorithm in the PostScript file below.

Godfried T. Toussaint, "A simple linear algorithm for intersecting convex polygons," The Visual Computer, vol. 1, 1985, pp. 118-123.

compressed PostScript file convex.intersection.ps.gz

Research Interests Homepage