Research On Algorithms Of Generation And Merging And Boolean Operations Of Polygons

Related operations of polygons plays a more and more important role with the development of geographic information system,computer aided design,surface reconstruction of 3D objects,medical or satellite image data processing and other fields in recent years.The related operations of polygons can be divided into generating,merging and Boolean operations,which are important problems in computational geometry.The deep researches were made on the algorithms related to polygons in this paper,which can be divided into four parts: polygon aggregation algorithms,line segments generating simple polygon,polygon triangulation and polygon Boolean operation algorithm.The one of the purposes of the new algorithms is to simplify the algorithm process and reduce the time complexity.The other is to shorten the length of the connection line and reduce the cost in practical applications.The polygon merging is to connect two disjoint polygons into one.The key idea of the algorithm is to delete the points on both sides of the polygon with a shorter distance,and to form a new polygon with the remaining vertices.Then the new polygon is triangulated by Delaunay triangulation.The quadrilateral is formed by diagonal lines with Delaunay edges.Finally,the edge difference of these quadrilaterals is calculated and the minimum value is found.The corresponding points of and are determined.The corresponding edges are deleted and the desired polygon with the shorted length is obtained.The algorithm was analysed and its time complexity was given.The algorithm of generating simple polygon is to connect line segments of the line segment set S into a simple polygon.The basic idea is to calculate the convex hulls of line segment set layer by layer at first.Then these convex hulls are changed into simple polygons by selecting the nearest point or the next nearest point according to Delaunay triangulation.Then the polygons are calculated and the intersection points are deleted.Finally,these simple polygons are merged into asimple polygon.The algorithm was analysed and its time complexity was given.The algorithm for polygon Boolean operations was given.The main idea of this algorithm is first to compute intersection points first according to the intersection algorithm of polygon chains.After traversing the polygon clockwise,the classification is based on the direction of the edge of the new polygon constructed by the intersection point and the end point.The intersection,union and difference sets of two polygons are calculated according to the rules of solving union,intersection and difference finally.