空间拓扑关系是GIS的重要基础, 也是GIS不可缺少的重要组成部分^[5]。在多边形的边界排序处理中, 线-多边形拓扑关系尤为重要。在GIS中, 多边形是由多条首尾相连的矢量线构成的, 每条矢量线具有方向和起始节点信息。定义每条矢量线的开始节点为起点(BeginPoint), 结束节点为终点(EndPoint), 基线(BaseLine)为当前正在处理的边界矢量线^[6]。下文中所提到的“ 默认线” 就是这种边界矢量线。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 简单多边形Fig.2 Simple polygon

以图2中与图斑697(图中数字为图斑编号和边界线编号, 下同)对应的多边形为例, 简单多边形的边界排序算法的实现步骤如下:

(1)获取多边形的边界线的原始集合C。集合C中的元素是无序的, 图2中多边形697的对应边界线集合为C={104256, 103837, 104457, 104269}。

(2)随机获取集合C中的任意一条线, 作为排序结果集合R的首条线, 并利用该线对BaseLine赋值, 同时在集合C中剔除该元素。假设首先获取的矢量线是104269, 则R={104269}, C={104256, 103837, 104457}。

(3)通过拓扑运算来判断多边形与边界线的左右位置关系。当多边形位于边界线的右侧, 则令P(x, y)等于BaseLine的终点P_end; 当多边形位于边界线的左侧, 则令P(x, y)等于BaseLine的起点P_begin。

(4)遍历集合C中的所有元素, 查找其起点值或者终点值等于P(x, y)的线元素。如果没有找到, 则执行步骤(7); 如果找到, 则把该元素插入到集合R中, 同时在集合C中剔除该元素, 并利用该元素对BaseLine进行重新赋值。

(5)对P(x, y)进行重新赋值。当P(x, y)等于BaseLine的起点值时, 则P(x, y)=P_end; 否则P(x, y)=P_begin。

(6)重复步骤(4)、(5)。

(7)结束。获取排序结果集合R, 此时集合R={104269, 104256, 103837, 104457}。

对于类似的简单多边形, 通过上述算法, 根据线-多边形的拓扑特性, 即可以实现其边界的排序处理。

但是上述算法对图3所示的复杂多边形就不适用。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 复杂多边形Fig.3 Complex polygon

图3中的图斑2940对应的多边形存在着多条边共用一个节点情况, 即边界线3853、3862、3859和3857共4条边相交于点O(共用O这个节点)。2.1节中所述的算法遇到这种情况就不适用, 因此需要对上述算法进行调整, 即需作切线处理(图4)。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 切线处理示意图Fig.4 Tangent process

切线处理时, 首先以O为起点, 分别获取4条边的切线(图4中①②③④共4条线), 并按逆时针方向计算其他切线与BaseLine切线的夹角; 然后取对应夹角最小的边作为BaseLine的下一条边界, 如此循环下去, 直到所有的边都处理结束为止。

复杂多边形的边界排序算法实现步骤如下:

(1)通过拓扑运算来获取多边形边界的矢量线的原始集合C, 集合C中的元素是无序的。

(2)随机获取集合C中的任意一条线, 作为排序结果集合R中的首条线, 并利用该线对BaseLine进行赋值, 同时在集合R中剔除该线。

(3)通过拓扑运算, 判断多边形与线的左右位置关系。当多边形位于线的右侧, 则令P(x, y)=P_end; 当多边形位于线的左侧, 则令P(x, y)=P_begin。

(4)遍历集合C中的所有元素, 查找其起点P_begin值或者终点P_end值等于P(x, y)的线。如果没有找到, 则执行步骤(8); 如果找到一个元素, 则把该线插入到结果集合R中, 同时在集合C中剔除该条线, 并利用该线对BaseLine进行重新赋值, 执行步骤(7); 如果找到多个元素, 则把找到的多条线存放到临时映射IMap< ID号, 夹角> 中, 其中ID号是每条线的唯一标识值, 夹角的初始值全设为0, 执行步骤(5)。

(5)计算临时映射(IMap< ID号, 夹角> )中的每条线与BaseLine的最小逆时针夹角值。在实际应用中, 由于多边形的边界不一定是直线, 可能是曲线, 因此需要进行特殊处理。可以借用P(x, y)为起点, 沿着各边界线的切线所在的射线来进行夹角计算。处理方式如图4所示。点O是当前的点P(x, y), 共搜索到3条共用该节点的边界线(不包含BaseLine), 并分别获取每条边界线的对应边界切线所在的射线①、②和③, 同时计算BaseLine逆时针旋转到每条射线的最小夹角, 并存放在临时映射IMap< ID号, 夹角> 中。

(6)获取临时映射IMap< ID号, 夹角> 中夹角值最小的那条边界线。并把该线插入到结果集合R中, 同时在集合C中剔除该线, 再利用该条线对BaseLine进行重新赋值。

(7)对P(x, y)进行重新赋值。当P(x, y)等于线BaseLine的起点P_begin值时, 则P(x, y)=P_end; 否则P(x, y)=P_begin。

(8)重复步骤(4)~(7)。

(9)结束。集合R就是最后的排序结果。

在土地利用调查中, 经常会遇到一些其他类型的复杂多边形, 通过适当处理也可以很好地使用上述算法来完成排序。

如图5(a)所示, 图斑128是包含“ 孔” 或者“ 岛” 的复杂多边形, 可以将其拆分成两个简单多边形, 即与图斑24对应的多边形和由图斑128的外边界所形成的多边形, 以便可以很好地适应上述算法。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 其他复杂多边形Fig.5 Other complicate polygons

在实际应用中, 经常会遇到如图5(b)所示的与行政区261对应的多边形, 由两个空间位置并不相邻的孤立多边形组成。可以对其进行打散处理, 先形成两个简单的多边形, 再分别进行处理, 以便也可以适应上述算法。

在图5(c)中, 与图斑19087对应的情况是前几种情况的综合, 它包含两个“ 岛” (19046和19055, 两者相接于一个节点)。因此, 与图斑19087的内边界对应的多边形是由岛19046和19055的边界线共同组成的。有一点需要注意, 对图斑19087的内边界进行排序的方法和2.2节中描述的算法存在细微差别, 只需要把步骤(5)中计算的最小夹角由逆时针方向改成顺时针方向即可。