Node Splitting Algorithm of R<sup>*-</sup>Tree Based on Minimum Spanning Tree

您当前的位置：

首页 >

文章列表页 >

Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree

更新时间：2025-05-08

- Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree
- Vol. 45, Issue 5, Pages: 127-130(2011)
- 作者机构：
  
  山东理工大学机械工程学院,山东,淄博,255049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP391.72
- Online First：10 May 2011，
  
  Published：2011
- 稿件说明：
移动端阅览
Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree[J]. 2011, 45(5): 127-130.
DOI：

Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree[J]. 2011, 45(5): 127-130. DOI：

摘要

针对R

树应用到逆向工程领域时遇到的适用性差等问题

提出了一种新的R

树结点分裂算法.该算法将R

树索引结点表示为轴向包围盒

依据轴向包围盒外接球间的重叠度计算结点相似度

并将其作为权值构建结点无向连通图

用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树

并基于结点外接球体积对R

树结构进行优化

从而实现了R

树结点分裂.实例表明

树结点分裂算法可处理各种复杂数据的结点分裂问题

能够有效地提高R

树的构建效率及空间数据的查询效率.

Abstract

Aiming at the problems of R

tree for reverse engineering of weak application

a new node splitting algorithm of R

tree is proposed. The nodes of R

tree are all expressed as their minimum bounding boxes. Then

the node comparability value is weighed with circum-sphere of the minimum bounding boxes. The minimum spanning tree is constructed based on the connected undirected graph of node comparability value

and the minimum spanning tree is divided into two sub-trees on the edge of the maximum weight

which gets effective for optimizing the structure of R

tree and improving the efficiency of node splitting.

关键词

Keywords

references

卫炜,张丽艳,周来水.一种快速搜索海量数据集k-近邻空间球算法 [J].航空学报,2006,27(5):944-948.

WEI Wei,ZHANG Liyan,ZHOU Laishui.A spatial sphere algorithm for searching k-nearest neighbors of massive scattered points [J].Acta Aeronautica Astronautica Sinica,2006,27(5):944-948.

史桂蓉.反向工程几何建模关键技术 [D].上海:上海交通大学,2000.

孙肖霞,孙殿柱,李延瑞,等.散乱数据点的快速三角剖分算法 [J].中国机械工程,2006,17(S2):245-248.

SUN Xiaoxia,SUN Dianzhu,LI Yanrui,et al.A fast mesh generation algorithm for unorganized points [J].China Mechanical Engineering,2006,17(S2):245-248.

BECKMASN N,KRIEGEL H P,SCHNEIDER R,et al.The R/sup*-tree: an efficient and robust access method for points and rectangles[C]∥Proceedings of SIGMOD. New York,USA: ACM, 1990:322-331.

ZHU Qing,GONG Jun,ZHANG Yeting.An efficient 3D R/sup*-tree spatial index method for virtual geographic environments [J].ISPRS Journal of Photogrammetry and Remote Sensing,2007,62(3):217-224.

张明波,陆锋,申排伟,等.R树家族的演变和发展 [J].计算机学报,2005,28(3):289-300.

ZHANG Mingbo,LU Feng,SHEN Paiwei,et al.The evolvement and progress of R-tree family [J].Chinese Journal of Computers,2005,28(3):289-300.

黄继先,鲍光淑,夏斌.基于混合聚类算法的动态R-树[J].中南大学学报:自然科学版,2006,37(2):366-370.

HUANG Jixian,BAO Guangshu,XIA Bin.A dynamic R-tree index based on hybrid clustering algorithm [J].Journal of Central South University:Science and Technology,2006,37(2):366-370.

孙殿柱,范志先,李延瑞,等.散乱数据点云型面特征分析算法的研究与应用 [J].机械工程学报,2007,43(6):133-136.

SUN Dianzhu,FAN Zhixian,LI Yanrui,et al.Research and application of surface feature analysis scatter data points [J].Chinese Journal of Mechanical Engineering,2007,43(6):133-136.

孙殿柱,田中朝,李延瑞,等.基于四维聚类的R/sup*-树结点分裂算法[J].机械工程学报,2009,45(10):180-184.

SUN Dianzhu,TIAN Zhongchao,LI Yanrui,et al.Node splitting algorithm of R/sup*-tree based on four-dimensional [J].Chinese Journal of Mechanical Engineering,2009,45(10):180-184.

孙殿柱,李延瑞,朱昌志,等.各类几何对象统一表示的R/sup*-tree结点分裂算法 [J].华中科技大学学报:自然科学版,2010,38(2):55-58.

SUN Dianzhu, LI Yanrui, ZHU Changzhi,et al.Node splitting algorithm for R/sup*-tree based on united expression of all geometry objects [J].Journal of Huazhong University of Science and Technology:Nature Science Edition,2010,38(2):55-58.

RAJASEKARAN S. On the Euclidean minimum spanning tree problem, Technical Report BECAT/CSE [R]. Storrs, CT, USA: Univ. of Connecticut,2004.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Robust Algorithm for Translation Symmetry Extraction in Reverse Engineering

Energy Efficiency Optimization of the Cryogenic Air Separation Process for Electronic-Grade Ultra Pure Nitrogen

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Diffusion Characteristics and Influencing Factors in Case of Hydrogen Leakage from Fuel Cell Vehicles Running in Tunnels

A Fast Calculation Method for Thermal Flow Fields in Transformer Windings Based on PI-DeepONet

Related Author

贺强

张树生

白晓亮

Related Institution

MOE Key Laboratory of Contemporary Design and Integrated Manufacturing Technology, Northwestern Polytechnical University

⁰

Node Splitting Algorithm of R*-Tree Based on Minimum Spanning Tree

DOI：

摘要

Abstract

关键词

Keywords

references

Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree