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

被引：5

作者：

俞肇元 ^{[1
]}

袁林旺 ^{[1
,2
]}

罗文 ^{[1
]}

胡勇 ^{[3
]}

闾国年 ^{[1
]}

机构：

[1] 虚拟地理环境教育部重点实验室(南京师范大学)

[2] 江苏省大规模复杂系统数值模拟重点实验室(南京师范大学)

[3] 不详

来源：

软件学报 | 2012年 / 23卷 / 10期

关键词：

多维统一空间索引; 非相交球树; 空间剖分; 空间聚类; 实体对象索引;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

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

引用

页码：2746 / 2759

页数：14

共 20 条

[1] A 3D GIS spatial data model based on conformal geometric algebra[J]. YUAN LinWang, YU ZhaoYuan, LUO Wen, ZHOU LiangChen & Lü GuoNian Key Laboratory of VGE, Ministry of Education, Nanjing Normal University, Nanjing 210046, China.Science China(Earth Sciences). 2011(01)
[2] Z树:一个高维度的数据索引结构
张强
赵政
[J]. 计算机工程, 2007, (15) : 49 - 51
[3] 面向真三维地学建模的海量虚拟八叉树模型研究
吕广宪
潘懋
吴焕萍
丛威青
吴自兴
[J]. 北京大学学报(自然科学版), 2007, (04) : 496 - 501
[4] 3D GIS空间索引技术研究
郑坤
朱良峰
吴信才
刘修国
李菁
[J]. 地理与地理信息科学, 2006, (04) : 35 - 39
[5] 一种加快WebGIS服务器响应速度的空间索引
叶常春
罗金平
周兴铭
[J]. 软件学报, 2005, (05) : 819 - 826
[6] GIS空间索引方法述评
阎超德
赵学胜
[J]. 地理与地理信息科学, 2004, (04) : 23 - 26+39
[7] 多比例尺下细节层次可视化的实现机制
李军
景宁
孙茂印
[J]. 软件学报, 2002, (10) : 2037 - 2043
[8] 一种支持快速相似检索的多维索引结构
冯玉才
曹奎
曹忠升
[J]. 软件学报, 2002, (08) : 1678 - 1685
[9] Geometric algebra method for multidimensionally-unified GIS computation[J] . LinWang Yuan,GuoNian Lü,Wen Luo,ZhaoYuan Yu,Lin Yi,YeHua Sheng.Chinese Science Bulletin . 2012 (7)
[10] 3D geo-database research: Retrospective and future directions[J] . Martin Breunig,Sisi Zlatanova.Computers and Geosciences . 2011 (7)

← 1 2 →