ComputingComputer ScienceComputational GeometryData StructuresSpatial Data AnalysisGeometric Data StructuresNearest Neighbor SearchPoint Cloud ProcessingSpatial Data StructuresSpatial Database SystemsSpatial DatabasesIndex StructuresNearest Neighbor Data StructuresNearest Neighbor RetrievalOctreesR* TreesR-tree IndexingR-treesSpatial Indexing
The spatial index structure is one of the most important research topics for organizing and managing massive 3D Point Cloud. As a point in Point Cloud consists of Cartesian coordinates (x,y,z), the common method to explore geometric information and features is nearest neighbor searching. An efficient spatial indexing structure directly affects the speed of the nearest neighbor search. Octree and kd-tree are the most used for Point Cloud data. However, octree or KD-tree do not perform best in nearest neighbor searching. A highly balanced tree, 3D R*-tree is considered the most effective method so far. So, a hybrid spatial indexing structure is proposed based on octree and 3D R*-tree. In this paper, we discussed how thresholds influence the performance of nearest neighbor searching and constructing the tree. Finally, an adaptive way method adopted to set thresholds. Furthermore, we obtained a better performance in tree construction and nearest neighbor searching than octree and 3D R*-tree.
25
PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation
Raffaelli Charles, Hao Su, Kaichun Mo et al. · 2017 · 9.8K citations
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text
The R*-tree: an efficient and robust access method for points and rectangles
Norbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider et al. · 1990 · 4.2K citations · Full text
PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation
Charles R. Qi, Hao Su, Kaichun Mo et al. · arXiv (Cornell University) · 2016 · 2.9K citations · Full text