Optimal Traversal Algorithms Of Disjoint Segments In Order Based On Convex Chain Storage

This paper studied the optimal traveling problem for disjoint ordered segments in plane, our goal is to find the optimal traversal path starting from a given starting point, traveling through all the segments and eventually reaching the given end point. The problem is a Euclidean shortest path problem (ESP) and it is also a theoretical problem of computational geometry, at the same time, this problem is an abstract model of many practical applications problems. It is not only of great theoretical significance, but also of high practical value to study the method to solve this problem.On the basis of the summary of the research results in this field, the paper points out that the application of Rubber-band algorithm to solve the problem may produce oscillation, resulting in higher algorithm time complexity. In order to solve these problems, this paper firstly studies some classical problems associated with traversing segments, and the basic knowledge and basic algorithms to be used during the problem solving process, such as how to judge the positional relationship between a point and a segment, how to get the reflection point and how to determine the aesthetic reflection. On the basis of this, we put forward the using of convex chain storage technology, combining with the Rubber-band algorithm to give a solving idea to deal with the problem of disjoint ordered segments. That is to say, we will give an overall solution using the convex chain to store local optimal path, using the binary search tree to update the path points, to prevent the oscillation phenomenon, reduce the number of iterations, enhance the efficiency of the algorithm. To this end, this paper discusses the convex chain storage technology and path point updating technology based on binary search tree in detail, and the iterative process of the optimization algorithms getting by combinatorial optimization technology. Finally, we put forward an algorithm with O(n*logn*logn) timing complexity to deal with the problem of visiting a sequence of disjoint ordered segments in plane, solving the problem of oscillation phenomenon of Rubber-band algorithm and greatly improve the time performance. Finally, according to the proposed algorithm, we construct a large number of corresponding test data, design the corresponding data structure and realize the algorithm through programming, analysis visualization operation results of our algorithm, verify the correctness and effectiveness of the algorithm.