{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T18:41:02Z","timestamp":1766428862635,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T00:00:00Z","timestamp":1726790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>An algorithm is described to find the shortest route through a field of obstacles of arbitrary shapes and positions. It has the appreciable advantage of not having to find mathematical formulas to represent the obstacles: it works directly with a digital image of the terrain and is implemented solely with standard graphical functions. Key to this algorithm is the definition of digraphs, the edges of which are built with obstacle bitangents and border enveloping convex arcs that incorporate the fundamental features of shortest paths. These graphs have a remarkably lower cardinality than those that have been proposed before to solve this problem; their edges are a concatenation of sequences of what individual edges and nodes are in formerly defined graphs. Furthermore, a thorough analysis of the topology of the terrain yields a procedure to eliminate the edges that have no possibility of being part of the shortest path. The A* graph optimization algorithm is adapted to deal with this type of graph. A new quite general theorem is proved, which applies to all graphs in which the triangle inequality holds, which allows the discarding of one of the normal steps of the A* algorithm. The effectiveness of the algorithm is demonstrated by calculating the shortest path for real complex terrains of areas between 25 km2 and 900 km2. In all cases, the required calculation time is less than 0.6 s on a Core i7-10750H CPU @ 2.60 GHz laptop computer.<\/jats:p>","DOI":"10.3390\/a17090420","type":"journal-article","created":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T10:49:48Z","timestamp":1726829388000},"page":"420","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Algorithm to Find the Shortest Path through Obstacles of Arbitrary Shapes and Positions in 2D"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4176-1135","authenticated-orcid":false,"given":"Gilles","family":"Labont\u00e9","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Royal Military College of Canada, Kingston, ON K7K 7B4, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2024,9,20]]},"reference":[{"key":"ref_1","first-page":"68","article-title":"Massively parallel hybrid algorithm on embedded graphics processing unit for unmanned aerial vehicle path planning","volume":"2","author":"Roberge","year":"2018","journal-title":"Int. J. Digit. Signals Smart Syst."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1139\/juvs-2017-0004","article-title":"Recent advances in unmanned aerial vehicles real-time trajectory planning","volume":"7","author":"Allaire","year":"2019","journal-title":"J. Unmanned Veh. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Zhang, H., Lin, W., and Chen, A. (2018). Path planning for the mobile robot: A review. Symmetry, 10.","DOI":"10.3390\/sym10100450"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.knosys.2018.05.033","article-title":"Survey on computational-intelligence-based UAV path planning","volume":"158","author":"Zhao","year":"2018","journal-title":"Knowl.-Based Syst."},{"key":"ref_5","first-page":"551","article-title":"On determining the flyability of airplane rectilinear trajectories at constant velocity","volume":"5","year":"2018","journal-title":"Adv. Aircr. Spacecr. Sci."},{"key":"ref_6","first-page":"53","article-title":"How airplanes fly at power-off and full-power on rectilinear trajectories","volume":"7","year":"2020","journal-title":"Adv. Aircr. Spacecr. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Huang, J., Junginger, S., Liu, H., and Thurow, K. (2023). Indoor Positioning Systems of Mobile Robots: A Review. Robotics, 12.","DOI":"10.3390\/robotics12020047"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Nilsson, N.J. (1969, January 7\u20139). A mobile automaton: An application of artificial intelligence techniques. Proceedings of the 1st International Joint Conference on Artificial Intelligence, Washington DC, USA.","DOI":"10.21236\/ADA459660"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"LaValle, S.M. (2006). Planning Algorithms, Cambridge University Press. Available online: http:\/\/lavalle.pl\/planning\/.","DOI":"10.1017\/CBO9780511546877"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"493","DOI":"10.2478\/amcs-2018-0038","article-title":"An exact geometry-based algorithm for path planning","volume":"28","author":"Jafarzadeh","year":"2018","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Wang, H. (2021, January 10\u201313). Shortest Paths Among Obstacles in the Plane Revisited. Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, Virtual.","DOI":"10.1137\/1.9781611976465.51"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1109\/TC.1983.1676196","article-title":"Spatial planning: A configuration approach","volume":"C-32","year":"1983","journal-title":"IEEE Trans. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1109\/70.88035","article-title":"Motion planning in a plane using generalized Voronoi diagram","volume":"5","author":"Osama","year":"1989","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","article-title":"An algorithm for planning collision-free paths among polyhedral obstacles","volume":"22","author":"Wesley","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Asano, T., Guibas, T.L., Hershberger, J., and Imai, H. (1985, January 21\u201323). Visibility-polygon search and Euclidean shortest paths. Proceedings of the 26th Annual Symposium on Foundations of Computer Science (SFCS 1985), Portland, OR, USA.","DOI":"10.1109\/SFCS.1985.65"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_18","unstructured":"Goodman, J.E., O\u2019Rourke, J., and T\u00f3th, C.D. (2017). Shortest paths and networks, Chapter 31. Handbook of Discrete and Computational Geometry, CRC Press LLC. Available online: https:\/\/www.csun.edu\/~ctoth\/Handbook\/HDCG3.html."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2215","DOI":"10.1137\/S0097539795289604","article-title":"An optimal algorithm for Euclidean shortest paths in the plane","volume":"28","author":"Hershberger","year":"1999","journal-title":"SIAM J. Comp."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/2660771","article-title":"Computing shortest paths among curved obstacles in the plane","volume":"11","author":"Chen","year":"2015","journal-title":"ACM Trans. Algorithms"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0925-7721(91)90012-4","article-title":"A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons","volume":"1","author":"Seidel","year":"1991","journal-title":"Comput. Geom."},{"key":"ref_22","unstructured":"Moravec, H. (1980). Chapter 8: Path Planning. In Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover. [Ph.D. Thesis, Computer Science Department, Stanford University]. Available online: https:\/\/www.ri.cmu.edu\/pub_files\/pub4\/moravec_hans_1980_1\/moravec_hans_1980_1.pdf."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Chang, E.-C., Sung, W.C., Kwon, D.Y., Park, H., and Yap, C.-K. (2006, January 6\u20138). Shortest Path amidst Disc Obstacles Is Computable. Proceedings of the Twenty-First Annual Symposium on Computational Geometry, Pisa, Italy.","DOI":"10.1145\/1064092.1064112"},{"key":"ref_24","unstructured":"Liu, Y.H., and Arimoto, S. (1991, January 9\u201311). Proposal of tangent graph and extended tangent graph for path planning of mobile robots. Proceedings of the 1991 IEEE International Conference on Robotics and Automation, Sacramento, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1177\/027836499201100409","article-title":"Path planning using a tangent graph for mobile robots among polygonal and curved obstacles","volume":"11","author":"Liu","year":"1992","journal-title":"Int. J. Robot. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1109\/TII.2019.2918589","article-title":"ReinforcedRimJump: Tangent-Based Shortest-Path Planning for Two-Dimensional Maps","volume":"16","author":"Yao","year":"2020","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/BF01840369","article-title":"A Path-planning strategies for a point mobile automaton moving amidst obstacles of arbitrary shape","volume":"2","author":"Lumelsky","year":"1987","journal-title":"Algoritmica"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Shah, B.C., and Gupta, S.K. (2016, January 12\u201317). Speeding up search on visibility graphs defined over quadtrees to enable long distance path planning for unmanned surface vehicles. Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling, London, UK.","DOI":"10.1609\/icaps.v26i1.13793"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"4129","DOI":"10.1109\/TKDE.2024.3363147","article-title":"On Efficient Shortest Path Computation on Terrain Surface: A Direction-Oriented Approach","volume":"36","author":"Wei","year":"2024","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_30","unstructured":"Benton, A., and O\u2019Rourke, J. (2007, January 20\u201322). Unfolding Polyhedra via Cut-Tree Truncation. Proceedings of the Canadian Conference on Computational Geometry CCCG 2007, Ottawa, ON, Canada."},{"key":"ref_31","first-page":"119","article-title":"Scalable parallel simulator for vehicular collision detection","volume":"8","author":"Grinberg","year":"2013","journal-title":"Int. J. Veh. Syst. Model. Test."},{"key":"ref_32","unstructured":"Kamon, I., Rivlin, E., and Rimon, E. (1996, January 22\u201328). A new range-sensor based globally convergent navigation algorithm for mobile robots. Proceedings of the 1996 IEEE International Conference on Robotics and Automation, Minneapolis, MN, USA."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.tcs.2008.07.025","article-title":"The supercover of an m-flat is a discrete analytical object","volume":"406","author":"Andres","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_34","unstructured":"Dedu, E. (2024, August 09). Bresenham-Based Supercover Line Algorithm. Available online: http:\/\/eugen.dedu.free.fr\/projects\/bresenham\/."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1147\/sj.41.0025","article-title":"Algorithm for computer control of a digital plotter (PDF)","volume":"4","author":"Bresenham","year":"1965","journal-title":"IBM Syst. J."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"012061","DOI":"10.1088\/1742-6596\/1566\/1\/012061","article-title":"Analysis of Dijkstra\u2019s Algorithm and A* Algorithm in Shortest Path Problem","volume":"1566","author":"Rachmawati","year":"2020","journal-title":"J. Phys. Conf. Ser."},{"key":"ref_37","unstructured":"(2024, September 07). Intel Core i7-10750H CPU. Available online: https:\/\/www.intel.com\/content\/www\/us\/en\/products\/sku\/201837\/intel-core-i710750h-processor-12m-cache-up-to-5-00-ghz\/specifications.html."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/9\/420\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:01:05Z","timestamp":1760112065000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/9\/420"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,20]]},"references-count":37,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2024,9]]}},"alternative-id":["a17090420"],"URL":"https:\/\/doi.org\/10.3390\/a17090420","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,9,20]]}}}