ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci., IV-2/W1, 249-255, 2016
http://www.isprs-ann-photogramm-remote-sens-spatial-inf-sci.net/IV-2-W1/249/2016/
doi:10.5194/isprs-annals-IV-2-W1-249-2016
 
05 Oct 2016
INDOOR A* PATHFINDING THROUGH AN OCTREE REPRESENTATION OF A POINT CLOUD
O. B. P. M. Rodenberg1, E. Verbree2, and S. Zlatanova3 1Delft University of Technology, Faculty of Architecture and the Built Environment, MSc Geomatics, Julianalaan 134, 2628 BL, Delft, the Netherlands
2Delft University of Technology, Faculty of Architecture and the Built Environment, OTB - Research Institute for the Built Environment, GIS Technology, Julianalaan 134, 2628 BL, Delft, the Netherlands
3Delft University of Technology, Faculty of Architecture and the Built Environment, Department of Urbanism, 3D Geoinformation, Julianalaan 134, 2628 BL, Delft, the Netherlands
Keywords: Indoor pathfinding, octree, network graph, connectivity, point cloud, collision avoidance Abstract. There is a growing demand of 3D indoor pathfinding applications. Researched in the field of robotics during the last decades of the 20th century, these methods focussed on 2D navigation. Nowadays we would like to have the ability to help people navigate inside buildings or send a drone inside a building when this is too dangerous for people. What these examples have in common is that an object with a certain geometry needs to find an optimal collision free path between a start and goal point.

This paper presents a new workflow for pathfinding through an octree representation of a point cloud. We applied the following steps: 1) the point cloud is processed so it fits best in an octree; 2) during the octree generation the interior empty nodes are filtered and further processed; 3) for each interior empty node the distance to the closest occupied node directly under it is computed; 4) a network graph is computed for all empty nodes; 5) the A* pathfinding algorithm is conducted.

This workflow takes into account the connectivity for each node to all possible neighbours (face, edge and vertex and all sizes). Besides, a collision avoidance system is pre-processed in two steps: first, the clearance of each empty node is computed, and then the maximal crossing value between two empty neighbouring nodes is computed. The clearance is used to select interior empty nodes of appropriate size and the maximal crossing value is used to filter the network graph. Finally, both these datasets are used in A* pathfinding.

Conference paper (PDF, 1264 KB)


Citation: Rodenberg, O. B. P. M., Verbree, E., and Zlatanova, S.: INDOOR A* PATHFINDING THROUGH AN OCTREE REPRESENTATION OF A POINT CLOUD, ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci., IV-2/W1, 249-255, doi:10.5194/isprs-annals-IV-2-W1-249-2016, 2016.

BibTeX EndNote Reference Manager XML