9
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

Reporting Intersections of Polygons

Pages 1-15 | Received 01 Oct 1985, Published online: 19 Mar 2007
 

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.

C.R. Categories:

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.