Overlay Algorithm for Simple Subdivision of Arbitrary Polygon in Plane

Abstract:

Article Preview

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.

Info:

Periodical:

Advanced Materials Research (Volumes 219-220)

Edited by:

Helen Zhang, Gang Shen and David Jin

Pages:

223-227

DOI:

10.4028/www.scientific.net/AMR.219-220.223

Citation:

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

Online since:

March 2011

Export:

Price:

$35.00

In order to see related information, you need to Login.

In order to see related information, you need to Login.