Shortest path-planning on polygonal surfaces with O (nlog n) time

摘要

This paper proposes an O(nlog n) time algorithm capable of finding near-shortest path on polygonal surfaces. Shortest-path planning in 3-dimensional space is an NP-hard problem. Theoretically, if the number of Steiner points in Kanai and Suzuki's algorithm is allowed to approach infinity, the path obtained will be optimal. In practice, the results generated by the KS's algorithm with 29 Steiner points are very close to the optimal solutions. We thus compared the experimental results of our algorithm to the results of the KS's algorithm using 29 Steiner points. Under such configuration, the average path length obtained by our method is slightly longer than the KS's, but our computing time is much shorter. The comparisons indicate that the proposed method is highly efficient for path-planning on polygonal surfaces. The method can be potentially applied to many important research and industrial fields such as 3D route planning, GIS, CNC tooling, etc.