三维空间索引结构—labb树的研究

《三维空间索引结构—labb树的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP391.72单位代码：10433密级：学号：Y0901013山东理工大学硕士学位论文三维空间索引结构—LABB树的研究ResearchofThree-DimensionalSpatialIndexStructureofLABBTree研究生：史阳指导教师：孙殿柱教授协助指导教师：申请学位门类级别：工学硕士学科专业名称：机械电子工程研究方向：CAD/CAM一体化技术论文完成日期：2012年4月24日万方数据万方数据山东理工大学硕士学位论文摘要摘要索引结构是逆向工程中的重要问题，索引结构的性能决定着空间数据的存储、管理和查

2、询效率。目前索引结构主要分为静态索引和动态索引，静态索引不具备数据动态管理能力而且运算效率低、系统消耗资源高；动态索引结构完善了数据动态存储和管理，但仍然存在空间利用率低、自适应性差等问题。本文基于R*-树在逆向工程中的应用进行研究和优化，针对上述问题提出一种基于遗传算法优化的最小包围盒算法及聚类分簇算法的三维LABB(LocalApproximateBoundingBox)树索引结构，有效减少结点的重叠度和死区的体积，提高结点的内聚性和索引结点分裂的自适应性，优化分裂结果，提高索引结构的查询效率，主要研究内容及成果如下：1)提出

3、一种遗传算法与O’Rourke的最小包围盒算法结合的近似最小包围盒优化求解算法，将包围盒体积函数作为目标函数，设定适应度函数和编码方案，通过各参数算子的设置使迭代过程快速收敛到最优解获得最小包围盒，解决了时间复杂度过大、求解效率过低等问题。2)针对k-均值容易陷入局部最优解和需要手动输入参数的问题，基于遗传算法的全局搜索能力弥补k-均值的缺陷，提出了基于遗传多目标优化的结点自适应聚类算法。基于遗传多目标优化的方法求解不同簇数下的全局最优分裂解，即得到节点分裂的Pareto最优解集，并以结点MBR(MinimumBoundingRe

4、ctangle)的重叠度与MBR的体积之和分别作为主要、次要评价标准从Pareto最优解集中选出偏好解，将其视为索引结构的最优结点分裂方案。3)通过最小包围盒确定局部坐标系，实现在局部坐标系下构建LABB树索引结构，并利用遗传多目标优化的结点自适应分裂算法对索引结构进行优化，该索引能够有效降低结点的重叠度，提高索引结构的查询效率。本文通过对R*-树的初始坐标系、结点分裂、全局优化等步骤进行优化研究，形成新的索引结构LABB树，基于该索引可有效提高索引的空间利用率和各类数据的空间查询效率，加强其在逆向工程领域的适用性。关键词：逆向工

5、程；R*-树；LABB树；最小包围盒；遗传算法；多目标优化I万方数据山东理工大学硕士学位论文ABSTRACTABSTRACTTheindexstructureisoneoftheimportantissuesinreverseengineering,whichcandecidethespacetostore,themanagementandqueryefficiencyofspatialdata.Theindexstructureincludesmainlystaticindex,whatcan’tbedynamicmanagem

6、entandlowefficiency,anddynamicindex.Thedynamicindexalsohasproblemwithlowutilizationofspaceandthepooradaptability.ThisissuepresentsanindexstructureLABB(LocalApproximateBoundingBox)treebasedontheR*-tree.TheLABB-treewiththeminimumboundingboxbasedongeneticalgorithmandclus

7、teringalgorithmcanreducetheoverlapofthenodesandthevolumeofdeadregion.Asthesametime,itcanimprovethecohesionofnodesandsearchingefficiencyofindexstructure.Themaincontentsandresultsasfollows:1)AnalgorithmaboutminimumboundingboxisproposedwithgeneticalgorithmandO’Rourke’sal

8、gorithm.TheobjectivefunctionisthevolumefunctioninO’Rourke’salgorithm.Settingwithfitnessfunctionandencodingscheme,thegenetica