A new linear algorithm for intersecting convex polygons. (English) Zbl 0533.52001

O’Rourke, Joseph; Chien, Chi-Bin; Olson, Thomas; Naddor, David

Comput. Graphics Image Process. 19, 384-391 (1982).

Summary: An algorithm is presented that computes the intersection of two convex polygons in linear time. The algorithm is fundamentally different from the only known linear algorithms for this problem, due to Shamos and Hoey. These algorithms depend on a division of the plane into either angular sectors (Shamos) or parallel slabs (Hoey), and are mildly complex. Our algorithm searches for the intersection points of the polygons by advancing a single pointer around each polygon, and is very easy to program.

MSC:

52A10	Convex sets in \(2\) dimensions (including convex curves)
68Q25	Analysis of algorithms and problem complexity

Keywords:

kernel of a polygon; angular sectors