Intersecting convex polygons
Given two convex polygons, the first question one should ask before proceeding is: "Do they intersect?". A logarithmic time algorithm is provided by Chazelle and Dobkin (1980) in a paper appropriately named "Detection is easier than computation".
Given that the polygons intersect, many algorithms computing the intersection xist. The interesting point here is a result (by Guibas) demontrating a one-to-one correspondence between the intersection points of the polygons and the bridges between them.
Two convex polygons (light red and blue) and their intersection (light purple). The intersection points are shown in red. Each point corresponds to a bridge (shown as dotted red lines) between the polygons.
Toussaint (1985) uses Guibas' result, and his previous algorithm for finding the bridges to compute the intersection points. His algorithm uses the bridges to compute the intersection points. Once these are found, similar to merging convex hulls, convex chains joining the intersection points form the intersection of the polygons.
The details of the algorithm, especially the computation of the intersection points from the bridges can be found in Toussaint's paper:
G.T. Toussaint. A simple linear algorithm for intersecting convex polygons. The Visual Computer. 1: 118-123. 1985.
The next problem involves finding the critical support lines between two convex polygons.
December 17th, 1998