Article
A Hybrid Spatial Indexing Structure of Massive Point Cloud
Based on Octree and 3D R*-Tree
Wei Wang
1
, Yi Zhang
2,3,
*, Genyu Ge
1
, Qin Jiang
1
, Yang Wang
1
and Lihe Hu
1
Citation: Wang, W.; Zhang, Y.; Ge, G.;
Jiang, Q.; Wang, Y.; Hu, L. A Hybrid
Spatial Indexing Structure of Massive
Point Cloud Based on Octree and 3D
R*-Tree. Appl. Sci. 2021, 11, 9581.
https://doi.org/10.3390/app11209581
Academic Editor: Adel Razek, Zimi
Sawacha, Alessandro Di Nuovo and
Dario Richiedei
Received: 6 May 2021
Accepted: 6 September 2021
Published: 14 October 2021
Publisher’s Note: MDPI stays neutral
with regard to jurisdictional claims in
published maps and institutional affil-
iations.
Copyright: © 2021 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).
1
College of Computer Science and Technology, Chongqing University of Posts and Telecommunications,
Chongqing 400065, China; d190201021@stu.cqupt.edu.cn (W.W.); d190201004@stu.cqupt.edu.cn (G.G.);
d180201007@stu.cqupt.edu.cn (Q.J.); d200201021@stu.cqupt.edu.cn (Y.W.);
d200201006@stu.cqupt.edu.cn (L.H.)
2
School of Advanced Manufacturing Engineering, Chongqing University of Posts and Telecommunications,
Chongqing 400065, China
3
Advanced Manufacturing and Automatization Engineering Laboratory, Chongqing University of Posts and
Telecommunications, Chongqing 400065, China
* Correspondence: zhangyi@cqupt.edu.cn; Tel.: +86-023-6248-0054
Abstract:
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.
Keywords: hybrid spatial indexing; octree; R-tree; 3D R*-tree; Point Cloud
1. Introduction
Currently, the study of autonomous vehicles and robots is a research hotspot. With
the development of computer technology and the increasing demand for digitalization, the
3-dimension (3D) model has captured increasing research attention for decades [
1
]. For
example, the 2D map which is widely used in robots cannot support robots to complete
complex tasks, such as scene understanding. The 3D map becomes more and more signifi-
cant for a robot. The 3D data is collected by 3D LiDAR, RGB-D camera, etc., which run at
very high frequency. It is inevitable that huge amounts of data will be generated. So, it is
urgent to choose an effective organizing and management method for 3D data.
The 3D coordinates
(x
,
y
,
z)
of each point correspond to the geometry component of
the Point Cloud, which may contain one or more additional components (attributes), such
as color, reflectance, and normal vectors, etc. Point Cloud data is a typical structure of 3D
data, which is the set of points with 3D coordinates. The 3D sensors are widely used in
various applications, and the technology is relatively mature, while the data processing
technology lags behind to some extent. Due to the massive data, disorder, irregularity,
sparsity, high resolution, and lack of topological relations or texture information [
2
], the
Point Cloud data processing is complex and challenging. Most feature analyses are based
on the relationship between point and neighbors; therefore, Nearest Neighbor (
NN
) search
is frequently conducted. The efficiency of query operation directly affects processing Point
Cloud data [
3
]. Furthermore, the 3D coordinate is the primary form of 3D vector data, the
Appl. Sci. 2021, 11, 9581. https://doi.org/10.3390/app11209581 https://www.mdpi.com/journal/applsci
