RT Journal Article
T1 A fast and optimal pathfinder using airborne LiDAR data
A1 Yermo, Miguel
A1 Fernández Rivera, Francisco
A1 Cabaleiro Domínguez, José Carlos
A1 López Vilariño, David
A1 Fernández Pena, Anselmo Tomás
K1 DTM
K1 Airborne point cloud
K1 Pathfinding
K1 Parallel computing
AB Determining the optimal path between two points in a 3D point cloud is a problem that have been addressed in many different situations: from road planning and escape routes determination, to network routing and facility layout. This problem is addressed using different input information, being 3D point clouds one of the most valuables. Its main utility is to save costs, whatever the field of application is. In this paper, we present a fast algorithm to determine the least cost path in an Airborne Laser Scanning point cloud. In some situations, like finding escape routes for instance, computing the solution in a very short time is crucial, and there are not many works developed in this theme. State of the art methods are mainly based on a digital terrain model (DTM) for calculating these routes, and these methods do not reflect well the topography along the edges of the graph. Also, the use of a DTM leads to a significant loss of both information and precision when calculating the characteristics of possible routes between two points. In this paper, a new method that does not require the use of a DTM and is suitable for airborne point clouds, whether they are classified or not, is proposed. The problem is modeled by defining a graph using the information given by a segmentation and a Voronoi Tessellation of the point cloud. The performance tests show that the algorithm is able to compute the optimal path between two points by processing up to 678,820 points per second in a point cloud of 40,000,000 points and 16 km² of extension
PB Elsevier
YR 2022
FD 2022
LK http://hdl.handle.net/10347/27904
UL http://hdl.handle.net/10347/27904
LA eng
NO ISPRS Journal of Photogrammetry and Remote Sensing 183 (2022) 482-495. https://doi.org/10.1016/j.isprsjprs.2021.11.014
NO This work has received financial support from the Consellería de Cultura, Educación e Ordenación Universitaria (accreditation 2019-2022 ED431G-2019/04, reference competitive group 2019-2021, ED431C 2018/19) and the European Regional Development Fund (ERDF), which acknowledges the CiTIUS-Research Center in Intelligent Technologies of the University of Santiago de Compostela as a Research Center of the Galician University System. This work was also supported by the Ministry of Economy and Competitiveness, Government of Spain (Grant No. PID2019-104834 GB-I00). We also acknowledge the Centro de Supercomputación de Galicia (CESGA) for the use of their computers
DS Minerva
RD 24 abr 2026