Reassembling polygons from edges

Abstract

Many geometric algorithms accept as input a set of polygons specified by their sequence of vertices and give as output a set of polygons which result from some operation on the input polygons. For instance, the output may represent the contour of the union of the polygons. In many cases a plane-sweep algorithm is used for such a problem. Typically such an algorithm will output the edges in the order that they would be encountered by a sweep line. Thus, one is left with the problem of determining which polygon each edge belongs to and ordering the edges in their natural cyclic order around each polygon. This is the problem considered in this paper, where it will be referred to as reassembling the set of edges. Although it is relatively easy to reassemble a set of edges of polygons in a single sweep, a naive approach will use O(N) space where N is the number of edges. This paper gives a space-efficient algorithm for doing the reassembly. It involves a forward and a backward sweep over the data.

Keywords:

• Polygon
• plane-sweep algorithm
• derived polygon
• space efficient algorithm

C.R. Categories:

• F.2.2