中文摘要：

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

英文摘要：

To solve leakages as complex subdivision structures,high nodes overlap probability and poor supporting on multi-dimensional entity object retrievals and the computation of existing spatial indexes.This paper presents a boundary restricted non-overlapping sphere tree for a unified multidimensional solid object index.By using the outer product expression of a sphere in Geometric Algebra,an approach is explored for intersection judgments 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-overlapping sphere-filling algorithm is developed to balance the conditions（e.g.granularity,non-overlapping subdivision of object voxelization）,the duplication and approximate degrees of approaching objects.Furthermore,generating and updating minimum boundary sphere and batch Neural Gas hierarchical clustering algorithm is also presented,and contains a volume adjusted,index level system steady with the balance of each branch of a sphere tree.Next,with the advantage of a clear geometric meaning,simple geometric relations calculation among spheres and dynamical updateable parameters,index structure can be dynamically generated and updated.Finally,the unified multidimensional solid object index,a query mechanism of any location and range on and in the solid objects is proposed.The updated minimum boundary sphere construction,algorithm,and the volume adjusted adaptive batch Neural Gas hierarchical cluster algorithm are defined to quickly,robustly,relatively,and uniformly classify the filling sphere.The simulation of different physical objects and performance comparison with a commonly used sphere tree indexes suggest that the proposed index can effectively query any position or regions on and in the solid objects,and support the nearest linkage distance and dynamical overlapping query under limited time restrictions with high precision.