Simple Polygon Construction Method Research

Planar polygon is a enclosed area connected by a set of ordered not-collinear points intwo-dimensional space. It is a convenient and accurate description tool for real objectshape, and it is easy to be implemented in computer. Polygon can be classified into twocategories; there are simple polygon and non-simple polygon. Simple polygon meansthat the non-adjacent edge is disjointed and the closed geometry does not exist within aloop. It is widely used in computer graphics, graphics and image processing, solidmodeling, such as character recognition, geographic information system (GIS),geographic information sensor network,etc. Therefore, it is necessary to design analgorithm that is more efficient and can satisfy the actual requirements for constructinga simple polygon. At present, the existing construction algorithms can be classified intothe discrete point set construction method and line segment set construction method.The discrete point set construction methods mainly include: Binary sort method,Coordinates translation Angle method, Gravity azimuth method, Convex hull structuremethod and Visible region method,etc..Based on existing method of construction simple polygon for discrete points, aconstructing algorithm based on intersection test of line segment set was proposed inthis paper. This algorithm take an improved plane sweep method for detecting linesegment intersection, then exchange endpoints of intersecting line segment to generatenon-intersecting line segment, repeat the above procedure until the simple polygon isconstructed. It can construct simple polygon when initial solution is poor, existself-intersecting edges polygon. In addition, according to the problem of high timecomplexity and polyline, this paper proposes a kind of the Voronoi diagram (V diagram)incremental constructing algorithm. Firstly, the adjacent relation of vertices isdetermined according to Voronoi graph of initial vertices,improve algorithm efficiency by reduce the search range, secondly, the vertex set isdivided to different region for determining the initial quadrilateral, finaly, rgional pointis iteratively inserted into the initial quadrilateral to structure simple polygon,combining the adjacent relation between vertices with the rule of minimal perimeterincrement. The theoretical analysis shows that the time complexity of this algorithm isO[n log(n)], where n is the quantity of vertices.To verify the performance of this algorithm, a solution and comparison of the bayg29and ch31in travelling salesman problem have been made. The differencebetween simple polygon perimeter which was constructed by Voronoi diagram (Vdiagram) incremental constructing algorithm and TSP minimum perimeter is very small,but efficiency of the algorithm was greatly improved, as indicate that the algorithm isfeasible.