土地利用图斑自动检测算法研究

程建燕，康建荣，周 棒，胡宗楠

(江苏师范大学，江苏 徐州 221116)

0 引 言

土地利用现状图是指以地图的形式反映不同行政区内的土地利用类型、利用现状以及与社会、自然关系等的专题地图，土地利用图斑的自动综合需要考虑拓扑关系、空间关系和语义关系等多方面因素[1]。在土地利用现状图制图综合过程中，因多边形几何形状的化简会导致原有图斑拓扑关系的破坏，因小面积图斑聚集分布会导致原有图斑空间关系的破坏，因此图斑自动检测成为十分重要的部分。在图斑的自动检测过程中涉及到的空间冲突主要是任意相邻图斑多边形间间距过小导致产生“桥梁区域”无法分辨[2]，以及小面积图斑过多、局部图斑密集导致需要进行图斑合并的问题。针对此问题，众多国内外学者对图斑自动检测进行了相应的研究。比较有代表性的研究成果有如下几类：艾廷华等根据图斑合并算子进行图斑的聚合和融合[3]，刘耀林等提出了基于本体的土地利用数据综合研究[4]，郭庆胜等研究了图斑合并的渐进式方法研究[5]，杨志龙提出了基于蚁群算法的图斑合并方法[6]，但是这些研究大多是对符合合并规则的图斑进行合并 很少涉及邻近图斑间产生的间隙问题。还有一些学者从顾及邻域变化的角度提出图斑群合并的方法，如翁杰提出了顾及邻域变化下的图斑群合并方法[7]，李成名提出了邻域关系维持下的狭长图斑分解方法[8]，李英提出了语义与空间相结合下的图斑自动综合模型[9]。但是这些研究未能很好地维持同地类图斑间的拓扑邻近关系，保持图斑的自然形态结构。文中从计算几何的角度，基于公共边界提出一种解决图斑合并的算法。该算法能够分辨图斑间间隙，消除邻近图斑间的“桥梁区域”，较好地维持地类图斑间的拓扑关系，保持图斑的自然弯曲形态，并结合Weiler-Atherton算法，删除小面积图斑，优化图斑群自动合并效果。

1 图斑检测基础定义

土地利用现状图制图综合过程中图斑检测的对象主要有两类[6]：一是距离过近导致在图中不易分辨的图斑；二是面积过小导致在图中过于密集的图斑。针对这两类图斑，定义了两种操作即“桥梁区域”检测和图斑自动合并。“桥梁区域”是指具有邻近关系的图斑多边形间间距过小产生的狭窄缝隙，它会导致在图中无法分辨，引起重叠、缝隙等空间冲突，如图1所示。当两图斑多边形具有公共边界时，在拓扑关系上视为邻近；当两图斑多边形在拓扑关系上相离，但相互间的距离非常小且难以区分时，视为邻近[10-11]。“桥梁区域”检测融入距离关系、拓扑关系，检测并消除相邻图斑多边形间的间隙，保持图斑间的邻近关系。图斑自动合并主要是对小面积图斑进行处理，减少土地利用现状图中密集图斑的数量，使地类图斑变得简洁。图斑自动合并会导致图斑的消失，消失的图斑的拓扑包含关系和邻近关系全部由合并后的大图斑继承，因此图斑自动合并是在与消失的图斑具有拓扑包含关系和邻近关系的图斑中进行[12-14]。

2 图斑自动检测方法分析

2.1 图斑多边形“桥梁区域”检测

2.1.1 图斑多边形公共边界

在进行矢量化土地利用现状图的过程中，图斑多边形可能出现自相交区域。自相交是指图斑多边形所有边之间除了顶点外还存在相交的边的情况[15]。这需要对土地利用图斑进行自相交检测判断，检测算法按照文献[16]中的算法设计，对于自相交区域采用直接删除的方式来进行处理。

图斑多边形看作是封闭的多线段，以边界线段操作为核心求解多边形的交点。利用射线交点法[17-18]进行点与多边形的关系确定，即待判定点为起点作射线，根据射线与多边形边界交点的奇偶数，确定是否点在多边形内部。若交点数为奇数，则点在多边形内；若交点数为偶数，则在多边形外。通过点与多边形的关系，进而判断多边形间的相互关系。若没有交点，则为包含关系或相离关系；若有交点，则为交叉关系。包含和分离关系的判定实质是若顶点都在多边形内部，则是包含关系；若顶点都在多边形外部，则是分离关系。

f=(xn+1-xn)(y-yn)-(yn+1-yn)(x-xn),

n=j或k

(1)

f1=(xn+1-xn)(yj-yn)-(yn+1-yn)(xj-xn),

n=k

(2)

2.1.2 “桥梁区域”检测方法

图斑多边形求取公共边界后，相邻图斑多边形基于公共边界进行“桥梁区域”自动检测及消除。结合图斑多边形的数据结构，图斑多边形的顶点序列可分为顺时针或逆时针方向排列。因此，相邻图斑间的“桥梁区域”可分为多种情况，即由公共边界出发，邻近两图斑的顶点序列皆按同方向排列时产生的“桥梁区域”形态存在差别，并当相邻图斑多边形顶点序列按相反方向排列时产生的“桥梁区域”也大不相同，具体情况如图3所示。

设相邻图斑多边形间的顶点距离为length，两顶点间的距离阈值为λ。图斑多边形M，C进行求交后，基于公共边界分别以同方向遍历相邻图斑多边形顶点，在交点处结束遍历。当相邻图斑多边形间的顶点距离lengthλ时，则取对应两顶点的中点μ代替原图斑多边形顶点，形成新的共享边界，消除原图斑间的“桥梁区域”。图斑多边形仅仅在同一方向检查“桥梁区域”不满足所有图斑多边形的情况，在相邻图斑顶点排列方向存在差异时，会产生不同形态的“桥梁区域”。此算法基于公共边界改变图斑多边形顶点的排列顺序，能够进行多种情况的检查，对相邻图斑多边形进行全面的“桥梁区域”检测。运用此算法进行模拟实验，实验结果如图4所示。

图2 公共边界求取结果

图3 桥梁区域分类

图4 桥梁区域检测结果

2.2 图斑自动合并算法

相邻图斑多边形求交后，结合Weiler-Atherton算法[19-22]，采用链表的形式判断交点的“入出性”，进而实现图斑的自动合并。两多边形相交时，交点必然成对出现。根据图斑多边形之间的关系，判断交点的“入出性”：一个多边形进入另一多边形的交点，称为“入点”；一个多边形离开另一多边形的交点，称为“出点”。由多边形的某个“出点”进行遍历，碰到出点，则沿着此多边形顺时针方向记录顶点序列，并将“出点”的flag记号删除，以免重复。遇到“入点”时，则沿着另一多边形逆时针方向记录顶点序列。按照此规则，如此交替地沿着两个多边形的边界进行遍历，直到回到起始点为止，将所有的出点搜集完毕后则算法结束。由于图斑合并需要考虑到地类等因素的影响，此算法只对于同属于同一地类的图斑进行合并。

以Region_Line_3D链表结构来构建相邻图斑多边形M、C，相邻图斑多边形M、C的顶点序列按照顺时针方向排列。求取相邻图斑多边形M、C的交点，对交点相同的点进行统一命名，并将交点按位置顺序分别插入链表M、C中。根据多边形M、C的顶点与交点所形成的边界的中点，由Weiler-Atherton合并算法思想，进行判别多边形M、C中交点的“入出性”。若边界中点在另一图斑区域外，则此交点为“入点”；若边界中点在另一图斑区域内，则此交点为“出点”。初始化多边形链表line，寻找图斑多边形链表中的“出点”，将“出点”记录到line中，并将“出点”标记flag删除。沿着一图斑多边形M顺序取其顶点，如果顶点不是“入点”，则将其顶点记录到line中，否则沿着另一图斑多边形C行进。当多边形C中顶点不是“出点”时，将其顶点记录到line中，否则流程转至上一步多边形M中行进。判断找到的最后一点是否为起点，若为起点则形成合并图斑区域line，查找结束。当相邻图斑多边形没有交点且为包含关系时，直接删除小图斑，其拓扑关系和权属关系由包含的大图斑继承。具体流程如图5所示。

图5 图斑合并流程

3 应用实例

3.1 程序实现设计

文中将整个程序应用于整幅土地利用图中，{Polygon}={P1,P2,…,Pn}为土地利用图中所有的图斑集合,对于{Polygon}中的任一图斑Pi都获取其x，y坐标的最大值maxx,maxy和最小值minx,miny，形成一个包围此图斑的扩展矩形区域。检测{Polygon}中其余图斑Pj的矩形区域与Pi矩形区域是否有交集Ψ，若Ψ>0,则记录Pj的所属地类名称Name(Pj)和图斑数据集合PD{Pj}。对Pi和PD{Pj}进行“桥梁区域”检测和图斑自动合并，合并时将Name(Pj)中与Pi不属于同一地类的图斑剔除，遍历完整个图斑集合{Polygon}，实现整幅土地利用图的图斑自动合并。

整个程序以存储在*.txt文件中的图斑坐标数据为研究对象，按照图斑数据准备、图斑数据检测合并和土地利用结果图输出的流程设计，在考虑不同地类间图斑不进行合并的情况下，对土地利用现状图上的大批量图斑进行“桥梁区域”的检测和图斑合并，主要实现土地利用现状图中图斑间的无缝隙、无重叠和小图斑的删除与合并。整个程序借助C++语言和MFC控制平台进行操作，并将输出结果在Auto CAD软件中进行可视化显示，使得整个程序方便、快捷，便于数据的重复性操作。程序的实现流程如图6所示。

图6 程序实现流程

3.2 实例验证

文中采用的实验数据为山西省第三次全国国土调查中的土地资源业务数据，如图7所示。该图中因图斑多边形叠置时图斑边界不一致，产生大量缝隙和重叠，导致邻近图斑间产生“桥梁区域”无法识别，破坏了土地利用现状图的全覆盖、无缝隙特点。并且图中小面积图斑过多，局部图斑密集，不利于图斑的自动综合。利用文中算法，并根据第三次全国国土调查实施方案的要求[23]，采用最小上图面积需大于200 m2的规范对此土地利用现状图进行“桥梁区域”检测和图斑的自动合并，经此算法处理后的结果如图8所示。

图7 数据原图

图8 处理结果

3.3 结果分析

土地利用现状图的图斑检测算法中对于小面积图斑的处理，其处理后的结果需要通过各类用地面积的相对平衡进行评价[24-26]。由表1可以看出，土地利用图斑检测前后总的图斑面积保持相对平衡，总的图斑数量相比检测前明显减少。其中农用地、建设用地和未利用地的图斑数量相比较于检测前均减少一半，检测后的农用地图斑面积相对于之前有明显增加，建设用地和未利用地的图斑面积相比较于之前明显减少。土地利用现状图经图斑检测算法后不仅“桥梁区域”问题得到解决，而且图中的小图斑密集区域也明显减少。由图8可以看出，此土地利用现状图中图斑间的“桥梁区域”能够被自动检测且修复，从而消除了此图中图斑间的缝隙和重叠区域，保证了土地利用现状图中全覆盖、无重叠、无缝隙的特点，并且从图中也能明显看出面积过小的图斑能够自动合并到同地类的大图斑之中，将原始的小图斑从图斑数据中删除，减少了密集区域的图斑数量。结果表明，此算法能够完全自动化地实现小图斑的自动合并，保持地类的继承性，弥补了ArcGIS软件中需要人工主观判断的缺陷，并能够对邻近图斑间的“桥梁区域”实现快速的检测和消除，维持土地利用图斑原有的自然弯曲形态，提高制图综合的效率。

表1 土地利用现状图检测前后对比

4 结束语

文中采用自相交区域直接删除的算法对土地利用图斑多边形进行自相交预处理后，通过定义求交规则的方式求取土地利用图斑多边形之间的公共边界。基于邻近图斑间的公共边界以多边形链表的结构并按照一定方向遍历土地利用图斑，在维持图斑拓扑一致性的基础上，检测并消除图斑间间距过小的“桥梁区域”。

该算法依据交点所在边界的中点，实现图斑多边形间关系判断。同时利用Weiler-Atherton算法，判定边界中点是否在另一图斑区域的内部，进行交点的入出性判断。并根据最小上图面积的原则，在图斑群中进行小面积图斑的搜索，在保持地类图斑间的继承关系的基础上批量消除小面积图斑，实现图斑的自动合并。

对于第三次国土调查中的批量图斑数据，整个制图综合过程只需要一幅土地利用现状图的图斑坐标数据，简化了计算过程，快速有效地实现了邻近图斑间的“桥梁区域”检测改正和小图斑群的自动合并，解决了ArcGIS软件中存在的制图工具功能简单、自动化程度不高等问题，提高了土地利用现状图的制图效率。