完整多边形拓扑结构

下面讨论如何从一系列按任意顺序和任意方向数字化的链，组成完整拓扑多边形网络结构的数据组织方法(上图)。这种数据结构能够处理湖和岛屿在任何一级多边形网络中的嵌套。

问题，能检查奇异多边形和“死点”，能自动或半自动地将非空间属性数据与多边形连接起来，并全面支持邻域关系的搜索等。前面讨论过的简单多边形数据结构经常要求数据输入方法必须满足数据结构要求，从而给数据输入和数据结构优化处理带来一些问题。因此，把数据输入和数据结构分成两个单独的处理过程是更加有效的方法。

为了建立这样的数据结构，只需对数据输入作两种假设：①多边形边界已按链或弧编码；⑦用以连接图形数据与属性数据的多边形名称则以每个多边形内某处可识别的点实体的形式数字化。在这种假设条件下，组成完整拓扑多边形数据结构的步骤如下：

1．将链连接成边界网络：首先按链的尺度(最大最小x,y坐标)存储多边形的链，使各条能按拓扑关系彼此集中在一起，同时在数据文件中存储在一起，从而节省查找相邻链的时间。然后对这些链进行检查，看哪些其它链与它们相交，把各交点存储在组成这些点的所有链的后面．并把链的数据记录延长以包括指针和角度。

如果链不是在端点相接而是在中间相交，就会自动切成新链和形成新节点．同时建立新的指针。有些地理信息系统不能自动形成节点，需用手工输入。虽然手工输入节点及指针可以减少计算处理时间，但会产生非标准的数据格式和数据库中的多余数据．同时输入工作量也大。

2．检查多边形是否闭合：检查多边形闭合与否的方法很简单，即扫描修改过的链记录，看每条镀是否有指向其它链和从其它链指向它。如果每条链都至少有一个指针指向其它链和一个从其它链指向它的指针，则说明多边形网络中的各多边形是闭合的。

如果组成岛的链只有一条，它的指针就指向它本身。某链经检查不合要求时，系统会以特殊的方法显示出来．让操作员知道某些链有问题，并决定是否去除或修改。

3．连接各链组成多边形：组成多边形的第一步是建立多边形网员外沿线组成的包络多边形(实体)，这个包络实体由以下记录内容组成：

①唯一标识；

①唯一的编码，这个编码说明该多边形是包络多边形；

①环形指针；

①指向边界链的指针列表。

①包络多边形的面积；

①范围(包围包络多边形的矩形的最大最小x，y坐标值)。

此包络多边形用户是看不见的，它的唯一作用是建立多边形网络的拓扑结构。

包络多边形按如下方法建立：在多边形网的最外沿选择一个点作为起始点，按顺时针方向沿着边界查找下一个节点。原则是选取每一个节点处的最左边一条链，并以这条链的另一端作为起点查找最左边的链，以此类推。

选出的链的识别符和其它有关数据需记录和存储，同时还要建立特殊标记来表明该链已被查找一次。

第二步是一旦外沿线(包络多边形)建立起来以后，就建立其它多边形。重新从建立包络多边形的起点开始，仍按顺时针方向查找，但不是找最左边的链而是最有右边的链。查找的同时还要记录各条链被查找的次数，如某条链已被查找两次就不再查找，回到起点就表明一个多边形查找结束。

查找和记录链的同时还要检查角度的累积值，如果总和不等于360度，则说明该节点处数字化有错误，而且会形成奇异多边形。虽然奇异多边形在第一阶段中已检查并滤除。但如果一条锭必须连接到手工输入的节点上时，这一检查还是必要的。

与包络多边形一样，每个多边形实体也包括如下信息：

①唯一的标识符；

①多边形编码；

①包络多边形到该多边形的环形指针针记录中去；

①所有边界链列表(同时，多边形的识别符应写入链的记录中去)；

①指向多边形网中邻接多边形的指针；

①包络多边形的矩形的最大最小坐标值。

这些工作都完成后，用同样的过程查找下一个多边形，但下一个多边形必须位于同一多边形网中，且属分级结构中的同一级。直到每个多边形都生成后才结束查找工作。当最后一个多边形查找完毕时，就将它的指针指回到包络多边形。

这样就能保证每一条链都与两个多边形有关。