5.2. 多边形自动生成

如第二章所介绍，网结构元素的拓扑关系是GIS中非常重要的一个内容。利用它我们可以建立区域和弧段、结点之间的数据结构；可以对数据库信息进行各种空间分析和拓扑检索，以帮助用户做出正确的决策。

到目前，人们已经研究和使用了多种拓扑关系的表示方法，其目的就是想能有效的表示区域和弧段的关联关系、区域和区域的包含关系、弧段与弧段的邻接关系以及弧段与结点的关联关系等。

一般建立拓扑关系有两种方法：手工建立和自动建立。前者是以人机交互操作的方式，用户通过操作输入设备（鼠标器或键盘），在屏幕上依次指出构成一个区域的各个弧段、一个区域包含了另外哪几个区域、组成一条线路的各个线段等等；而后者则是利用系统提供的拓扑关系自动建立的功能，对手扶跟踪数字化或栅格数据矢量化得到的数据进行分析判断，从而得出网结构元素的拓扑关系。

自动建立面域、弧段以及结点之间的拓扑关系多采用弧段跟踪法（徐庆荣，1993）：

图5-8 弧段邻接关系及其表示法

（1）弧段邻接关系建立

由原始线段数据建立弧段的邻接关系，同时也确定了弧段与结点的关联关系。

如果两条弧段具有相同的端点，则定义这两条弧段具有邻接关系。图5-8表示了弧段邻接关系及其记录方式。邻接于弧段同一端点的各邻接弧段按顺时针方向顺序记录，按数字化方向，若邻接弧段是首点邻接，则在其关键字前冠以正号，否则冠以负号。

（2）环的生成

按一定规则（顺时针或逆时针）沿弧段跟踪形成闭合环（区域），同时记下每个区域的编号。

环的生成是对弧段邻接关系表（如图5-8所示）的一个跟踪搜索过程。由一条弧段出发，在邻接关系表中查出其前端最左的一条邻接弧段，根据此邻接弧段关键字前正负号，向前找到其它另一端最左的邻接弧段。按上述过程重复向前搜索跟踪，直至回到最初的出发弧段。

由于每条弧段同时关联于两个相邻的多边形，所以它应被跟踪两次，两次的方向相反。

跟踪结果形成的各个环，都应记录环经过的各弧段关键字，并用正负号标志弧段走向，若弧段走向与跟踪方向一致则标志正号，反之为负号。如图5-8中，若从弧段2开始跟踪，则圈定多边形A的环的记录为：（+2，+1，-4，+3）。

（3）确定多边形之间的包含关系

根据点是否在多边形内的判断法则，依次找出区域与区域之间的嵌套关系。

按环记录中关键字，可将该环上各弧段坐标数据读出，对所有内点匹配，便能确定环与内点的包含关系，即得环与内点包含关系得对照表，如图5-9。

图5-9 环与内点的包含关系

一个多边形可能有一个或多个环，而一个多边形只给出一个内点，因而环与内点的拓扑关系可能是一对一或多对一的关系。图5-9中建立的环与内点的包含关系是纯几何上的，一个环可能包含多个内点，一个内点可能可能同时包含在不同的环内，这是一种多对多的几何包含关系。因此，必须从环与内点的包含关系转化为按多边形拓扑结构的环与内点的圈定关系，即找出哪些环是属于某一内点所代表的多边形的，这就是我们所需要的多边形面域与轮廓边的关联关系；以及某多边形和哪些多边形是包含关系。

手工建立或自动建立拓扑关系的方法各有其优势和不足。手工建立拓扑关系的方法：操作复杂，工作量大，但对原始数据要求不严，修改时不必重复计算；自动建立拓扑关系的方法：生成速度快，但对原始数据要求严，即要求弧段端点（结点）匹配好。因此，通常在自动生成多边形操作之前，都要进行结点匹配的操作，以保证多边形的顺利生成。