A New Algorithm for Euclidean Shortest Path of Visiting Segments in a Polygon

Abstract:

Let s and t be two points on the boundary of a simple polygon, how to compute the Euclidean shortest path between s and t which visits a sequence of segments given in the simple polygon is the problem to be discussed, especially, the situation of the adjacent segments intersect is the focus of our study. In this paper, we first analyze the degeneration applying rubber-band algorithm to solve the problem. Then based on rubber-band algorithm, we present an improved algorithm which can solve the degeneration by the method of crossing over two segments to deal with intersection and in our algorithm the adjacent segments order can be changed when they intersect. Particularly, we have implemented the algorithm and have applied a large of test data to test it. The experiments demonstrate that our algorithm is correct and efficient, and it has the same time complexity as the rubber-band algorithm.

• Periodical: Applied Mechanics and Materials (Volumes 644-650)
• Pages: 1891-1894
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.644-650.1891
• Online since: September 2014
• Authors: Li Juan Wang, An Sheng Deng, Bo Jiang, Qi Wei
• Keywords: Degeneration, Euclidean Shortest Path, Rubber-Band Algorithm, Simple Polygon

References

[1] Mark de Berg, Otfried Cheong, Marc van Kreveld, et al. Computational Geometry: Algoriths and Appli- cations (Third Edition), Springer-Verlag Publishers, Berlin(2009).

[2] D. T. Lee, F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers[J]. Networks, Vol. 3 (1984) , p.393–410.

DOI: 10.1002/net.3230140304

[3] Fajie Li, Reinhard Klette. Exact and approximate algorithms for the calculation of shortest paths[J]. IMA journal of management mathematics, Vol. 1 (2006) , p.134–138.

[4] LI Fa-jie, KLETTE Reinhard. Shortest path algorithms for sequences of polygons[J]. CAAI Transactions on Intelligent Systems, Vol. 1 (2008) , pp.23-30.

[5] Lijuan Wang, Li Huo, Dandan He. An Improved Algorithm for Euclidean Shortest Paths of Visiting Line Segments in the Plane[J]. Journal of Convergence Information Technology, Vol. 6 (2011) , pp.119-125.

DOI: 10.4156/jcit.vol6.issue6.13

[6] LI Fa-jie, KLETTE Reinhard. Shortest path algorithms for sequences of polygons[J]. CAAI Transactions on Intelligent Systems, Vol. 1 (2008) , pp.23-30.

[7] Hongfeng Hou and so on. The Application of Communication Management System Based on the Pattern of SOA[C]. Vehicle, Mechatronics and Information Technologies(2013).