边界约束的非相交球树实体对象多维统一索引
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(41171300); 国家科技支撑计划(2012BAH35B02); 江苏省自然科学基金(BK2012454)


Boundary Restricted Non-Overlapping Sphere Tree for Unified Multidimensional Solid Object Index
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对现有空间索引剖分结构复杂、节点重叠率高及对多维实体对象检索及运算支撑较弱等问题,构建了一种边界约束的非相交球实体对象多维统一空间索引;利用球的几何代数外积表达,提出了基于求交算子的直线-平面和直线-球面的相交判定与交点提取方法,建立了多维实体对象体元化剖分方法及包含边界约束的非相交离散球实体填充算法,实现了实体对象空间均匀、非重叠的分割,并在填充球的个数、重叠率以及对象逼近近似度等约束条件上获得了较好的平衡.定义了最小外包球生成与更新的迭代算法与包含球体积修正的批量 Neural Gas 层次聚类算法,在尽可能保证球树各分支平衡性的前提下,实现了索引层次体系的稳健构建.利用几何代数下球对象间几何关系计算的内蕴性与参数更新的动态性,实现了索引结构的动态生成与更新,进而设计了实体对象表面及其内部任意位置及区域的检索策略及基于实体索引的空间关系计算方法.基于不同实体对象的模拟实验显示,基于几何代数的实体对象索引可以有效实现多维实体对象表面及其内部任意位置及区域的快速检索,并能在有限时间内以较高的精度实现多维实体对象最近邻距离和动态实体对象相交状态的检索.相对于常用球树索引,所提出的索引方法在填充率、节点重叠率、填充误差、体元个数、层次球个数、体积百分比和时间占用等方面均具有明显优势,且不同分辨率剖分条件下的索引结构及空间关系计算精度具有更高的稳健性,可运用于具有较强时间约束下复杂多维动态场景中对象检索与空间关系计算.

    Abstract:

    To solve leakages as complex subdivision structures, high nodes overlap probability and poorsupporting on multi-dimensional entity object retrievals and the computation of existing spatial indexes. This paperpresents a boundary restricted non-overlapping sphere tree for a unified multidimensional solid object index. Byusing the outer product expression of a sphere in Geometric Algebra, an approach is explored for intersectionjudgments and point extractions between lines and planes and lines and spherical surfaces based on meet operators.The element subdivision of multi-dimensional object voxelization and the boundary restricted non-overlappingsphere-filling algorithm is developed to balance the conditions (e.g. granularity, non-overlapping subdivision ofobject voxelization), the duplication and approximate degrees of approaching objects. Furthermore, generating andupdating minimum boundary sphere and batch Neural Gas hierarchical clustering algorithm is also presented, andcontains a volume adjusted, index level system steady with the balance of each branch of a sphere tree. Next, withthe advantage of a clear geometric meaning, simple geometric relations calculation among spheres and dynamicalupdateable parameters, index structure can be dynamically generated and updated. Finally, the unifiedmultidimensional solid object index, a query mechanism of any location and range on and in the solid objects isproposed. The updated minimum boundary sphere construction, algorithm, and the volume adjusted adaptive batchNeural Gas hierarchical cluster algorithm are defined to quickly, robustly, relatively, and uniformly classify thefilling sphere. The simulation of different physical objects and performance comparison with a commonly usedsphere tree indexes suggest that the proposed index can effectively query any position or regions on and in the solidobjects, and support the nearest linkage distance and dynamical overlapping query under limited time restrictionswith high precision.

    参考文献
    相似文献
    引证文献
引用本文

俞肇元,袁林旺,罗文,胡勇,闾国年.边界约束的非相交球树实体对象多维统一索引.软件学报,2012,23(10):2746-2759

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2011-08-23
  • 最后修改日期:2012-03-27
  • 录用日期:
  • 在线发布日期: 2012-09-30
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号