Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves

Abstract

We present an efficient algorithm for finding the shortest path joining two points in a sequence of triangles in three-dimensional space without planar unfolding. The concept of a funnel associated with a common edge along a sequence of triangles is introduced, that is similar to Lee and Preparata’s one in a simple polygon. The sequence of funnels associated with all common edges of the sequence is constructed and then the shortest path is determined by cusps of these funnels. Such funnels are determined iteratively to their associated edges by the Method of Orienting Curves, which was introduced by Phu [Ein konstruktives Lösungsverfahren für das Problem des Inpolygons kleinsten Umfangs von J. Steiner. Optimization. 1987;18:349–359]. The method consists of the concepts of final curves and orienting curves (the special cases of straightest geodesics). We then show that the shortest path from the cusp of a given funnel to the direct destination in the processed region of the funnel is determined by parts of orienting curves and a final curve. A numerical example for finding the shortest path joining two points in the sequence of triangles is presented and visualized by JavaView software.

Keywords:

• Method of orienting curves
• geometric shortest path
• straightest geodesic
• sequence of triangles

Acknowledgements

The author wishes to express his thanks to Prof. Konrad Polthier for the useful discussions and his gracious hospitality on his visits in 2014–2016 to his Mathematical Geometry Processing group at the FU Berlin where a part of this paper was written. The author gratefully acknowledges many helpful suggestions of Prof. Hoang Xuan Phu (Institute of Mathematics, Hanoi) and Dr. Dinh Thanh Giang (Vinh University) during the preparation of the paper and the author has a responsibility for any remaining errors. The author thanks the reviewers very much for their constructive comments, which helped the author to improve greatly the paper.

Notes

No potential conflict of interest was reported by the author.

Additional information

Funding

This work was supported by the IMU Berlin Einstein Foundation Program at the Berlin Mathematical School, National Foundation for Science and Technology Development (NAFOSTED), Vietnam [grant number 101.01-2014.28]; Vietnam Institute for Advanced Study in Mathematics (VIASM) and TWAS Research Grants Programme 16-544 in Basic Sciences.