Research On The Touring Algorithms Of Partial-joint Segments In Order Based On Convex Chain Storage

This paper studies the optimal touring problem of the partial-joint ordered segments in the plane.It aims at finding the shortest path from the given starting point to the given end point,traversing the given partial-joint segments in order.Studying the efficient solution method about this problem is not only a theoretical problem,but also helps to solve the robot motion planning,UAV control and some other practical issues.So it has great theoretical significance and practical value.This paper analyzes the degradation in solving partial-joint ordered segments touring problem in Rubber-band algorithm,and double counting in the iterative process of calculating local optimal path.At the same time,the article points out that the Rubber-band improved algorithm(deduction algorithm)which is proposed to deal with the intersection of segments has inaccurate results.To solve these problems,we discuss the local optimal path shrinking technology such as crossing,perfect reflection and refraction at the segment endpoint on the basis of analyzing the positional relationship between segments and points in detail.And we propose a method for solving the sub-optimization and combination based on processing intersection across segments and local optimal path convex chain storage structure.Finally,we put forward an algorithm with O(n*log2n)complexity to deal with the problem of touring a sequence of partial-joint ordered segments in plane.The algorithm not only solves the problem of the degradation effectively,but also reduces the times of iterations in local optimal path.To verify the validity of the algorithm,we design the corresponding data structure,realize the algorithm through programming with Java language,construct a large number of test data randomly,and give visual results of the algorithm running.It shows that the proposed algorithm not only solves the degradation of Rubber-band algorithm effectively,but the calculated shortest path is more accurate than the deduction algorithm.It is the optimal algorithm in solving partial-joint ordered segments touring problem by far.