肖 怡，李佳田，张文靖，刘 鹏，王 瑜，张思佳

（昆明理工大学 国土资源工程学院，云南 昆明 650093）

0 引 言

空间目标与它生成的Voronoi区域距离最近，如果两个空间目标具有共同Voronoi边界，那么这两个空间目标之间存在着自然邻近空间关系[1]。自然邻近在自然地表内插[2-3]、空间邻近查询[4]、制图综合[5-6]以及模式分类[7-8]等领域是一个十分重要的研究内容。然而，现有的空间数据库并不支持自然邻近空间关系查询，制约着空间数据库技术在GIS中的应用。

Voronoi图将空间邻近关系隐含于其中。Long等基于Voronoi的空间关系-V9I的基础上进一步分析了A，B两个空间目标之间的空间关系，其中用3×3布尔矩阵表示了A，B自然邻近的情况[9-10]。Xie等提出了不确定的Voronoi图(或UV图)，它将数据空间分为不相交的“UV分区”。每个UV分区P与目标集合S相关联，使得位于P中的任何点q都有集合S作为它的最近邻居[11]。Trefftz 等用空间目标的k阶Voronoi图，进而进行邻近查询[12-13]。但是由于至今全要素的Voronoi图的生成方法并不成熟，研究学者纷纷将目光转向Voronoi的对偶Delaunay三角网，Gold等提出了将三角形中的三边根据邻近关系以及边的逆时针方向来分类进而形成二叉树序列来判断自然邻近空间关系[14-15]。但二叉树不是多路平衡树且更新不便。Jones等使用了规则格网索引对三角形做了预处理，通过三角形的邻近关系来确定影响三角形的集合，这种方法被称为简单格网索引方法(Simple Grid Index，SGI)[16]。但是这种方法会存储大量的三角形，占用较多的磁盘空间并且不支持更新。

本文的主要工作是……