Overlay Algorithm for Simple Subdivision of Arbitrary Polygon in Plane
The overlay algorithm is an important branch in computational geometry field, it is an important process for computing exact Minkowski sum of two convex polyhedrons. By improving the existing plane sweep algorithm, the overlay algorithm for simple subdivision of arbitrary polygon in plane is given. The algorithm can be used to overlay arbitrary polygon after subdivision into simple polygon in the plane. It has lower time complexity than the existing overlay algorithm. The whole algorithm consists of three steps: line segment intersection, reconstructing topology and constructing the DCEL for overlay graph. The results show that the algorithm can compute the overlay of two planar subdivisions in linear time.
Helen Zhang, Gang Shen and David Jin
X. J. Guo et al., "Overlay Algorithm for Simple Subdivision of Arbitrary Polygon in Plane", Advanced Materials Research, Vols. 219-220, pp. 223-227, 2011