Algorithm for finding geodesic path based on rotation tree
Hui Sun, Haisheng Li · 2010
Visibility graph method is a main method for finding a geodesic path within a polygonal domain. Rotation tree method is a simple and efficient approach to construct visible edges. However, this approach is unable to distinguish whether a visible edge is inside a polygonal domain or not. This paper presents an inside / outside determination algorithm within O(1) time. Based on this algorithm and rotation tree method, we introduce a new approach to find a geodesic path. Our approach isn't optimal in time, but it is easy to implement and do run efficiently.