主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2019-2020年专刊出版计划 微信服务介绍 最新一期:2019年第2期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
俞肇元,袁林旺,罗文,胡勇,闾国年.边界约束的非相交球树实体对象多维统一索引.软件学报,2012,23(10):2746-2759
边界约束的非相交球树实体对象多维统一索引
Boundary Restricted Non-Overlapping Sphere Tree for Unified Multidimensional Solid Object Index
投稿时间:2011-08-23  修订日期:2012-03-27
DOI:10.3724/SP.J.1001.2012.04214
中文关键词:  多维统一空间索引  非相交球树  空间剖分  空间聚类  实体对象索引
英文关键词:multi-dimension unified spatial index  non-overlapping sphere tree  space partition  spatial cluster  solid object index
基金项目:国家自然科学基金(41171300); 国家科技支撑计划(2012BAH35B02); 江苏省自然科学基金(BK2012454)
作者单位E-mail
俞肇元 虚拟地理环境教育部重点实验室(南京师范大学), 江苏南京 210046  
袁林旺 虚拟地理环境教育部重点实验室(南京师范大学), 江苏南京 210046
江苏省大规模复杂系统数值模拟重点实验室(南京师范大学), 江苏南京 210046 
yuanlinwang@njnu.edu.cn 
罗文 虚拟地理环境教育部重点实验室(南京师范大学), 江苏南京 210046  
胡勇 南京师范大学计算机科学与技术学院, 江苏南京 210046  
闾国年 虚拟地理环境教育部重点实验室(南京师范大学), 江苏南京 210046  
摘要点击次数: 2153
全文下载次数: 2749
中文摘要:
      针对现有空间索引剖分结构复杂、节点重叠率高及对多维实体对象检索及运算支撑较弱等问题,构建了一种边界约束的非相交球实体对象多维统一空间索引;利用球的几何代数外积表达,提出了基于求交算子的直线-平面和直线-球面的相交判定与交点提取方法,建立了多维实体对象体元化剖分方法及包含边界约束的非相交离散球实体填充算法,实现了实体对象空间均匀、非重叠的分割,并在填充球的个数、重叠率以及对象逼近近似度等约束条件上获得了较好的平衡.定义了最小外包球生成与更新的迭代算法与包含球体积修正的批量 Neural Gas 层次聚类算法,在尽可能保证球树各分支平衡性的前提下,实现了索引层次体系的稳健构建.利用几何代数下球对象间几何关系计算的内蕴性与参数更新的动态性,实现了索引结构的动态生成与更新,进而设计了实体对象表面及其内部任意位置及区域的检索策略及基于实体索引的空间关系计算方法.基于不同实体对象的模拟实验显示,基于几何代数的实体对象索引可以有效实现多维实体对象表面及其内部任意位置及区域的快速检索,并能在有限时间内以较高的精度实现多维实体对象最近邻距离和动态实体对象相交状态的检索.相对于常用球树索引,所提出的索引方法在填充率、节点重叠率、填充误差、体元个数、层次球个数、体积百分比和时间占用等方面均具有明显优势,且不同分辨率剖分条件下的索引结构及空间关系计算精度具有更高的稳健性,可运用于具有较强时间约束下复杂多维动态场景中对象检索与空间关系计算.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利