Research On The Algorithm For Touring A Sequence Of Disjoint Convex Polygons In The Plane

This paper focus on the optimal touring problem of disjoint convex polygons in the plane, the target is to find a global shortest path starting from the given start point, then touring every convex polygons by order, at last ending at the given target point. This problem is not only a theoretical problem in geometric computing field, but also an abstract model for many practical applications. Finding efficient solutions for this problem have both theoretical significance and practical values.Based on a review of relevant research results in this field, this paper pointed out the problems of existing method, that is their data structures are complex which is hard to implement and they also have higher time complexity. To solve these problems, this paper explores some classic problems associated with touring polygons problem, as well as some basic knowledge such as how to judge the position between point and polygons, position between line and line and also the reflection point and perfect reflection. On this basis, combined with the idea of greedy algorithm, this paper put forward the solutions that take advantage of local optimum to transfer the problem to a sequence of local problems, then combine and optimize them to get the global solution. Therefore, this article discusses several cases of local optimum as well as the process to construct last step shortest path map, using the line sweeping method with combination and optimization to put forward an algorithm whose time complexity is O(kn). This algorithm helps to solve the data structure and time complexity problem mentioned above. Finally, design the appropriate data structures and programming to implementation, nalysis visualization algorithms operating results verify the correctness and effectiveness of the algorithm.