Reporting Intersections of Polygons

Abstract

An algorithm is given for reporting pairs of intersecting polygons from among a given set of polygons. A plane-sweeping algorithm is used together with a segment tree of the type introduced by Bentley and Wood [2] to report intersections between rectilinearly oriented rectangles. Bentley and Wood use a segment tree to store the line segments formed by the intersection of a sweep line with the set of rectangles. When arbitrarily polygons are used instead of rectangles, the cross-sections of the polygons are of continually varying length, and the standard segment tree is not satisfactory. In order to handle this difficulty the concept of pseudo-coordinates is introduced.

Keywords:

• Plane-sweep
• algorithm
• polygon
• segment tree

C.R. Categories:

• F.2.2