A fast algorithm for touring the disjoint convex polygons in the given order

摘要

Given a start point s, a target point t, and k disjoint convex polygons in the given order in the plane, finding the shortest path of visiting the convex polygons sequence from s to t is the goal. In this paper, we present a fast algorithm to compute the shortest path based on the last step shortest path maps. Firstly, we locate the dividing-points quickly in the two adjacent polygons, which can reduce amounts of iteratively computation. Then, we convert this problem to solving the shortest path of visiting the disjoint line segments sequence which makes the solution much simpler. Furthermore, we analyze the complexity of new algorithm and obtain that it is superior to the previous solution. Finally, we implement this algorithm and show that it is correct.