A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree
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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline">&...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/11/20/9581 |
| _version_ | 1797515345640030208 |
|---|---|
| author | Wei Wang Yi Zhang Genyu Ge Qin Jiang Yang Wang Lihe Hu |
| author_facet | Wei Wang Yi Zhang Genyu Ge Qin Jiang Yang Wang Lihe Hu |
| author_sort | Wei Wang |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>,</mo><mi>z</mi><mo>)</mo></mrow></semantics></math></inline-formula>, 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. |
| first_indexed | 2024-03-10T06:44:11Z |
| format | Article |
| id | doaj.art-43208b5db91b4364ba12b0c138eaff27 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T06:44:11Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-43208b5db91b4364ba12b0c138eaff272023-11-22T17:21:14ZengMDPI AGApplied Sciences2076-34172021-10-011120958110.3390/app11209581A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-TreeWei Wang0Yi Zhang1Genyu Ge2Qin Jiang3Yang Wang4Lihe Hu5College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaSchool of Advanced Manufacturing Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaCollege of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaCollege of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaCollege of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaCollege of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, ChinaThe 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>,</mo><mi>z</mi><mo>)</mo></mrow></semantics></math></inline-formula>, 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.https://www.mdpi.com/2076-3417/11/20/9581hybrid spatial indexingoctreeR-tree3D R*-treePoint Cloud |
| spellingShingle | Wei Wang Yi Zhang Genyu Ge Qin Jiang Yang Wang Lihe Hu A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree Applied Sciences hybrid spatial indexing octree R-tree 3D R*-tree Point Cloud |
| title | A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree |
| title_full | A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree |
| title_fullStr | A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree |
| title_full_unstemmed | A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree |
| title_short | A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree |
| title_sort | hybrid spatial indexing structure of massive point cloud based on octree and 3d r tree |
| topic | hybrid spatial indexing octree R-tree 3D R*-tree Point Cloud |
| url | https://www.mdpi.com/2076-3417/11/20/9581 |
| work_keys_str_mv | AT weiwang ahybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT yizhang ahybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT genyuge ahybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT qinjiang ahybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT yangwang ahybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT lihehu ahybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT weiwang hybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT yizhang hybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT genyuge hybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT qinjiang hybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT yangwang hybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree AT lihehu hybridspatialindexingstructureofmassivepointcloudbasedonoctreeand3drtree |