Research On The Optimization Algorithms For Touring A Sequence Of Convex Polygons In The Plane

In this paper,the main study content is the optimal touring problem of convex polygons in which the adjacent polygons may intersect with each other,but the nonadjacent polygons do not intersect in the plane,a start points,and an end point t in the plane,our goal is to obtain a shortest path that starts from s,visits each given polygon in order,and ends at t finally.This problem is an important extension of the TSP problem and also a theoretical research problem in the field of computational geometry.Therefore,the study on this issue not only has important theoretical value,but also has more important practical application value.In this paper,based on the discussion of the TSP gallery WRP simple polygons and their concave and convex,local shortest paths and the existing results related to this research question,the optimal traversal of convex polygon sequences in the plane Made a more in-depth study,pointed out the problems existing in the research results,i.e.,the data structure used is more complicated and difficult to realize and the time complexity is higher.In order to solve these problems,this dissertation first studies some basic knowledge and basic algorithms related to this research question,such as the positional relationship between point and line,the distance from point to line,the position of point and convex polygon,In addition,combined with the idea of dynamic programm,this paper converted the touring polygons problem into the problem of computing the shortest path of visiting the line segments by analyzing the geometrical features of the given convex polygons,and using a forward partition process combined with a backward search process for finding the access edge of each convex polygon.Thus,we proposed an O(kn)algorithm for solving the original problem.On this basis,through the construction of the corresponding test data,programmed to achieve the design of the algorithm,the visualization of the results of the operation of the algorithm and compared with the theoretical results verify the feasibility and effectiveness of the algorithm designed in this paper.