Overlay Algorithm For Simple Subdivision Of Arbitrary Polygon In Plane

Computational Geometry is an important research field of computer theoretical science. The subject has already made a tremendous development and produced a series of theoretical results, and it has great significance in theory and application. Overlay algorithm as an embranchment of the research field of Computational Geometry, its research results play an important role in dynamic simulation, robotics, geography information system, and so on, especially in the field of robotics, it is an important step for computing robot collision-free path by using Minkowski sum. Therefore, how to calculate the path of obstacle avoidance quickly and accurately for the robot has been an important research subject of the home and foreign scholars.Firstly, overlay algorithm is a very important step for computing the Minkowski sum of two polygons, and finding all intersection points of segment lines is the first step of overlay. On the basis of studying the current situation both here and abroad, we have made a deep study of existing algorithm for finding intersection point. By giving color attributes to the layers, the algoritm for finding intersection points of segment lines based on plane sweep is proposed, we analysis the detail execute process and execute efficiency of the algorithm, and discuss the application of the algorithm in several fields.Secondly, on the basis of studying the current overlay algorithm, we found that some algorithms exist deficiencies, such as cannot compute the overlay of plane subdivide into concave polygons. To overcome the disadvantage of the current algorithms, and improve the execute efficency of computing overlay, by using the thought of BFS graphic, the overlay algorithm for simple subdivision of arbitrary polygon in plane is given in this paper. The algorithm can compute arbitrary simple subdivision of polygon in plane. The whole algorithm composed of three steps: line segment intersection, reconstructing topology and updating the DCEL for overlay graph.Thirdly, we display the detail execute process of the overlay algorithm by an example, and analysis the correctness and complexity of the algorithm.Finally, the research content in this paper is verified by experiment, by comparing with the existing algorithm, we particularly analyze the results, thus confirmed the correctness and excute efficiency of the algorithm.