Subject 2.04: How do I find the intersection of two convex polygons?
Unlike intersections of general polygons, which might produce a quadratic number of pieces, intersection of convex polygons of n and m vertices always produces a polygon of at most (n+m) vertices. There are a variety of algorithms whose time complexity is proportional to this size, i.e., linear. The first, due to Shamos and Hoey, is perhaps the easiest to understand. Let the two polygons be P and Q. Draw a horizontal line through every vertex of each. This partitions each into trapezoids (with at most two triangles, one at the top and one at the bottom). Now scan down the two polygons in concert, one trapezoid at a time, and intersect the trapezoids if they overlap vertically. A more difficult-to-describe algorithm is in [O’Rourke], pp. 242-252. This walks around the boundaries of P and Q in concert, intersecting edges. An implementation is included in [O’Rourke].
