基于Voronoi区的GIS中方向关系的描述与计算

摘要

方向关系在地理信息系统（GIS）中占据着十分重要的地位，由于它的模糊性和依赖空间实体形状的特性，使得它的形式化描述和判断比较困难。本文在三角形模型（CDR）方法的基础上，利用最小矩形（MBR）四边的Voronoi多边形及其边界，形式化描述了方向关系，进而将方向关系分为主方向关系和次方向关系，并分别给出了两者利用MBR四边Voronoi多边形及其边界判断的算法。

正文

《1 前言》

1 前言

自然界中的方位概念对于空间分析和人们对空间的认知都十分重要，因而顺序关系中的方向关系是地理信息系统（GIS）中一类十分重要的定性关系。但由于它存在着模糊性，在数学上很难将其有效地形式化描述。例如，在图1a、图1b和图1c中，B 都是在A 的东方，然而它们却存在远近和方位上的差异。由此可以看出，两空间实体之间的方向关系不仅同空间实体的几何位置有关系，而且同空间实体的形状也密不可分。空间实体形状的纷繁复杂以及方向关系的模糊性给方向关系的形式化描述带来了一定的难度。然而，尽管如此，人们对此仍进行了许多有意义的研究，其中包括 Peuquet 和 Xiang^[1] 提出的三角形模型（CDR）和而后的扩展方法，这给本文利用 Voronoi 区描述方向关系提供了基础，笔者首先对该方法及其扩展方法作简单的回顾，然后论述如何利用扩展的基于 Voronoi 区的空间关系描述模型（NIV）^[2~4]有效描述方向关系。

两个空间实体之间的方向关系隶属局部操作。这是因为方向关系是相对的，参照不同的空间实体，可能得出不同的方向关系。笔者从两个空间实体构成的局部范围出发，探讨方向关系的描述和判断。

《图1》

图1 方向关系示例

Fig.1 The examples of directional relation

《2 方向关系的形式化描述》

2 方向关系的形式化描述

《2.1 研究回顾》

2.1 研究回顾

Peuquet和Xiang^[1]给出了不同形状空间物体之间方向关系语义解释，并且提出了能够描述它们的 CDR模型，如图2所示，空间实体的中心点和东北方向线（NE）、东南方向线（SE）构成了空间实体的东部区域 east（A），如 B 在 east（A）（B ⊂east（A）），则 B 位于空间实体A 的东部，记作east（A，B）。

在Peuquet和Xiang^[1]给出的CDR中，没有考虑空间物体的形状，因而就产生了CDR描述的不合理性。例如，在图2b中，B 显然在A 的东部，但由于没有考虑 A 的形状、大小，其中 A 的中心和 NE、SE 构成的east（A）并不包含B，east（A，B）关系不存在。但是，从图2b中直观解译A、B 的关系和该方法描述得到的结果不一致。

《图2》

图2 CDR模型

Fig.2 CDR model

Haar将上述CDR加以扩展，用包围空间物体的最小矩形（MBR）的4方向线NE、SE、NW、SW以及 MBR的4边构成了空间实体A 的4个区域east（A）、 west（A）、north（A）和 south（A）。通过 B 与 4 个区域的关系，确定 A、B 的方向关系。如在图 3a 中，A 的最小矩形面向B物体的两个顶点的SE、NE方向线与 A 的 east 边形成了 A 的东部区域。在图 3a中， B ⊄east（A），east（A，B）不存在。在图3b 中，B ⊂east （A），空间实体 A、B 的方向关系为 east（A，B）。扩展后的 CDR 描述模型，空间实体 A 的 east（A）、 west（A）、north（A）和south（A）区域随空间实体的形状、大小变化而变化。但是，不管CDR描述模型，还是扩展后的MBR描述模型仅能够从语义上解释方向关系，不能够形式化将其描述，有效地将其判断。

《图3》

图3 MBR不合理情况示例

Fig.3 The unreasonable example of MBR

《2.2 利用Voronoi区描述方向关系》

2.2 利用Voronoi区描述方向关系

CDR 及其后的扩展方法给基于 Voronoi 区的方向关系描述提供了一个思想基础。一个空间实体 A 的最小矩形有 4 条边分别表示为 de=eastedge（A）、dw=westedge（A）、dn=northedge（A）和ds=southedge（A）。若将 4 条边看作 4 个线（line）生成元，生成的 4 个 Voronoi 区分别为 Voronoi（de）、Voronoi（dw）、Voronoi（dn）和 Voronoi（ds）。NE、NW、 SW 和 SE 分别为边 de、dn、dw 和 ds 的 Voronoi 多边形的边界，空间物体A的东部east（A）定义为de、SE 和NE围成的区域，空间物体A 的西部west（A）定义为dw、SW 和 NW 围成的区域，空间物体 A 的北部 north（A）定义为dn、NE、NW围成的区域，空间物体 A 的南部 south（A）定义为 ds、SE、SW 围成的区域，如图4所示。

《图4》

图4 空间实体的4个Voronoi区

Fig.4 Four Voronoi regions of spatial entities

空间实体 A 和 B 之间的方向关系可以利用空间实体的最小矩形边和 Voronoi 区的边界线构成的 5×5 矩阵形式化描述表达，矩阵的形式见式（1）。

在式（1）中，NE_A表示空间物体 A 的北-东线， NE_B 表示空间物体B 的北-东线，B_A 表示空间物体A 的最小矩形的边，其余类似。

设 di*表示 di 的逆关系。例如 di =east，那么 di*＝west。对于空间物体 B 位于空间物体 A 的东部，那么 B 部分或全部在 east（A）内。在这种情形下，west（B）一定覆盖east（A），west（B）与east（A）的重叠区域可以由两者的方向线表示，尤其west（B）、 east（A）的边界线必然相交。由于区域的边界由两条方向线和最小矩形的一条边构成，区域边界的交就是这些交叉的组合。交产生3类情况：Voronoi边界线之间的交，例如NE_A∩NW_B；Voronoi边界线与最小矩形边的交，例如de_A∩NW_B；最小矩形边之间的交de_A∩de_B。假设X、Y 为两个空间实体，ij（X，Y）表示空间实体之间的关系，那么根据上述的分析，可以得出 3 条判断准则，它们分别是：如果两个 Voronoi 边界线相交 ijA ∩ij*B，那么空间实体之间方向关系为j（B，A）或j*（A，B）；同样，如果两个Voronoi边界线相交ijA ∩（ij）*B，那么空间实体之间方向关系为ij （B，A）或（ij）*（A，B）；如果空间物体 A 最小矩形边交空间物体B 的Voronoi边界线，即iA ∩ji*B，那么空间实体之间方向关系为i（B，A）或ji*（A，B）。

根据式（1）以及上述判断准则，表1给出了可能的获得的方向关系。例如从NW_A∩NE_B，可以获得方向关系east（A，B），从NE_A∩NE_B，不能获得任何方向关系，用“—”表示。

《表1》

表1 基于Voronoi区的方向关系描述

Table 1 Directional relation description based on Voronoi region

《3 方向关系的判断》

3 方向关系的判断

《3.1 MBR的Voronoi区的生成》

3.1 MBR的Voronoi区的生成

如果包围空间实体A 的最小矩形的边和X、Y 轴平行或垂直，那么该最小矩形被称为A 的MBR，它有4条边（东、西、南、北边，分别用符号E、W、S、N代替），每一条边看成一个线生成元。在局部空间内部，不在MBR内的每一点到4个线生成元的距离分别为De、Dw、Ds和Dn。点到生成元的距离定义如下。

设C 是线性元素，x 是一个点，那么，x 与C 之间的距离为 Distance(x,C )= Min{distance(x,y ),y ∈ C }

其中x、y是两个点，若其坐标分别为（x₁，x₂，…， x_n）和（y₁，y₂，…，y_n），那么，x 与y 之间的距离为

根据以上距离定义，可以有如下的结论：a. 如果有 Min{De，Dw，Ds，Dn}=De≠Dw 或 Ds 或 Dn，那么该点属于MBR的east区域；b. 如果有Min{De，Dw， Ds，Dn}=Dw≠De 或 Ds 或 Dn，那么该点属于 MBR 的 west 区域；c. 如果有 Min{De，Dw，Ds，Dn}=Ds≠ Dw 或 De 或 Dn，那么该点属于 MBR 的 south 区域； d. 如果有 Min{De，Dw，Ds，Dn} =Dn≠Dw 或 Ds 或 De，那么该点属于 MBR 的 north 区域；e. 如果有 Min{De，Dw，Ds，Dn}=De=Ds≠Dw或Dn，那么该点属于 MBR 的 east- south 边界；f. 如果有 Min{De， Dw，Ds，Dn} =De=Dn≠Dw 或 Ds，那么该点属于 MBR的east-north边界；g. 如果有Min{De，Dw，Ds， Dn} =Dw=Ds≠De 或 Dn，那么该点属于 MBR 的west-south 边界；h. 如果有 Min{De，Dw，Ds，Dn}= Dw=Dn≠De或Ds，那么该点属于MBR的west-north 边界。

《3.2 主方向的判断》

3.2 主方向的判断

两个空间实体之间的方向关系有东、西、南、北、东南、东北、西南和西北，其中东、西、南和北称为主方向关系，其余称为次方向关系。由3.1生成MBR 的Voronoi区之后，可以利用4个生成元的Voronoi区域判断主方向关系。假设空间实体为λ₁、λ₂，那么，判断两者之间主方向关系的过程分为4个步骤：a. 计算空间实体λ₁、λ₂的MBR；b. 构造λ₁的MBR 4边E、W、 S、N 的 Voronoi 区，构成了 4 区域 Voronoi（E）、 Voronoi（W）、Voronoi（S）、Voronoi（N）；c. 构造 λ₂的 MBR 4 边 E、W、S、N 的 Voronoi 区，构成了 4 区域 Voronoi（E）、Voronoi（W）、Voronoi（S）、Voronoi（N）； d. 如果λ₁⊂Voronoi（X），那么λ₁ ⋅ X ⋅ λ₂，如果λ₂⊂ Voronoi（X），那么λ₂⋅ X ⋅ λ₁。

《3.3 次方向的判断》

3.3 次方向的判断

次方向的判断要利用表1，设空间实体为λλ₁、λ₂，那么，判断的次方向的过程分为4个步骤：a. 计算空间实体λ₁、λ₂的MBR；b. 构造λ₁的MBR 4边E、W、S、 N的Voronoi区，计算4边E、W、S、N的Voronoi多边形的边界；c. 构造λ₂的 MBR 4 边 E、W、S、N 的 Voronoi区，计算4边E、W、S、N的Voronoi多边形的边界；d. 对照表1，得出两者的次方向关系。

《3.4 实例研究》

3.4 实例研究

图5是一幅简单的数字影像，其中“1”和“2”分别表示空间实体A 和B 占据的像素。图6是空间实体A 的MBR的Voronoi区，图中“S”表示A 的南部区域，“E”表示A 的东部区域，“SE”表示东南边界。图7 是空间实体B 的MBR的Voronoi区，“N”表示B 的北部区域，“E”表示 B 的东部区域，“NE”表示东北边界。当图6和图7叠加变为一幅数字影像后，B 所占据的像素（即值等于“2”的像元）全部落在A 的南部区域，A 所占据的像素（即值等于“2”的像元）全部落在B 的北部区域，根据主方向判断算法，得到B 在A 的南部，并且A 在B 的北部。同理，由于A 的SE和B 的NE交叉，根据表1利用次方向判断算法，也可以得出B 在A 的南部和A 在B 的北部的结论。

《图5》

图5 原始图像的1/4

Fig.5 Quarter of the original image

《图6》

图6 A 的MBR 的Voronoi区

Fig.6 The Voronoi region of MBR for A

《图7》

图7 B 的MBR 的Voronoi区

Fig.7 The Voronoi region of MBR for B

《4 结语》

4 结语

通过以上的分析和实例研究，可以得出如下结论：

1）将空间实体MBR的4边看成生成元，生成4边的Voronoi区，可以利用两空间实体的Voronoi区域和Voronoi边界形式化描述两者的方向关系；

2）生成了 MBR 4 边的 Voronoi 区以后，可以利用四边的Voronoi区域和另一个空间实体的相对位置，判断主方向关系；

3）生成了两个空间实体MBR 4边的Voronoi区以后，进而获取Voronoi区的边界，利用边界的相交性质参照形式化描述结果，可以判断两个空间实体的次方向关系。

展示更多