论文部分内容阅读
空间数据库中的自然邻近关系(natural adjacencyrelationship)计算必须克服的问题是Voronoi图与欧氏距离的不一致,它对空间索引结构提出了新要求.针对二维空间中离散面目标的点自然邻居查询,提出了一种基于Delaunay三角剖分的空间索引构建方法。首先,在三角网分类的基础上将代表相同目标自然邻近关系的三角形合并形成区域(unit):然后用最小外接矩形近似这个区域;最后,考虑到索引结构的更新,设计了Quad Gridfile索引结构,即先用四叉树对空间进行剖分,再对其叶子结点所代表的子面片采用Gridfile,用叶子结点的重构来代替索引结构的更新.对比实验结果表明,该索引方法能够有效地支持点自然邻居查询,且在构建索引的时空复杂与更新方面表现出较强的性质。