（三）拓扑结构编码方法

多边形内嵌套多边形即“洞”和邻域关系问题的唯一解决办法是拓扑关系直接应用到数据结构中。建立拓扑结构的方法有两种：①输入数据的同时输入拓扑连结关系；②由计算机软件从一系列相互关联的链建立拓扑结构。前者会增加操作员的工作量，后者则取决于计算机的处理能力。二者都增加存储量。首先在地理数据结构中建立拓扑关系是美国人口调查局建立的双重独立地图编码系统。又可简称 DIME（Dual Independent Map Encoding）。DIME 建立城市街道网和统计单位如街区、人口统计区等的数据库，并实现自动和半自动的编辑和分析。也可以用于土地利用等多种信息系统的编辑和分析。DIME 数据文件的基本元素是由始末点定义的简单线元素，复杂的曲线则有许多这种线元素组成。每条线元素有两个指向结点指针和线元素两边多边形的编码。由于这种数据结构中没有链反向结点及链指向邻近链的指针，因此要花很多时间去查找组织多边形的各条边界线。

此外，简单线元素结构法使复杂曲线的处理十分不便，因为有大量的多余数据同时存储于数据库中。

荷兰土地调查研究院发展了另一种简单而有效的多边形数据结构，并能在小型计算机上处理多边形数据组的分配问题。基本方法是：地图上的多边形以线段或链文件的形式存储，该文件中每条链又以组成该链的各坐标对来列表存储，而且每条链还包括两个指向邻接多边形的指针（图 3－19）。多边形的名称存储在另一个独立文件中，该文件实际上是一个表格，也包括一些指针。这种数据结构不能进行更为复杂的邻城关系的搜索，也不能检查奇异多边形和“死点”等差错。只有完整的拓扑结构数据库才能处理这类问题。

为了建立恰当的拓扑多边形数据结构，使“岛屿多边形”、面积计算、邻城关系处理、奇异多边形和“死点”检查等都能顺利处理，必须建立图 3

－20 所示的数据结构。许多实验性和生产性的制图系统都要求在数字化的同时在数据库中建立拓扑联结关系，而且常常要求用户按顺时针方向或逆时针方向数字化所有的多边形，以便把线元素与其左右两边的多形组合起来。另外还要求用户用数字化图中的虚线把“岛屿”和它们周围的“湖泊”连接起来。

下面讨论如何从一系列按任意顺序和任意方向数字化的链，组成完整拓扑多边形网络结构的数据组织方法（图 3－20）。这种数据结构能够处理湖和岛屿在任何一级多边形网络中的嵌套问题，能检查奇异多边形和“死点”，

能自动或半自动地将非空间属性数据与多边形连接起来，并全面支持邻域关系的搜索等。

前面讨论过的简单多边形数据结构经常要求数据输入方法必须满足数据结构要求，从而给数据输入和数据结构优化处理带来一些问题。因此，把数据输入和数据结构分成两个单独的处理过程是更加有效的方法。为了建立这样的数据结构，只需对数据输入作两种假设：①多边形边界已按链或弧编码；

②用以连接图形数据与属性数据的多边形名称则以每个多边形内某处可识别的点实体的形式数字化。在这种假设条件下，组成完整拓扑多边形数据结构的步骤如下：

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

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

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

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

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

⊙唯一标识；

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

⊙环形指针；

⊙指向边界链的指针列表；

⊙包络多边形的面积；

⊙范围（包围包络多边形的矩形的最大最小 x，y 坐标值）。

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

包络多边形按如下方法建立：在多边形网的最外沿选择一个点作为起始点，按顺时针方向沿着边界查找下一个节点。原则是选取每一个节点处的最左边一条链，并以这条链的另一端作为起点查找最左边的链，以此类推。选出的链的识别符和其它有关数据需记录和存储，同时还要建立特殊标记来表明该链已被查找一次。

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

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

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

⊙唯一的标识符；

⊙多边形编码；

⊙包围多边形到该多边形的环形指针，同时，该多边形的识别符应写入包络多边形的环形指针记录中去；

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

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

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

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

“岛”的查找过程与上述基本一样。但“岛”必须按适当的拓扑等级进行编排，而且把“岛”的水域线围成的多边形也指定为包络多边形，编排岛的拓扑等级可以按包络多边形的面积分类排列，然后检查小包络多边形（即岛）是否落入较大的包络多边形内。较为快速的查找方法是比较它们的范围即包络矩形（最大，最小 x，y 坐标）的大小。如果发现多边形落入较大多边形内，则用“点在多边形内”程序检查岛多边形是否完全在大多边形内（图3－21 和图 3－22）。图 3－21 中点 a 在多边形的范围内（最大、最小坐标）以外，很容易判断 a 点不在多边形内；b 点和 c 点则需用图 3－22 所示的方法进一步检查。即从所查点开始向一个方向作水平线，如果该水平线与多边形边界相交的次数为奇数则表明该点在多边形内，否则在外。图 3－22 中多边形 P'边界上的各点，经检查都在大多边形 P 内，则说明 P'完全在 P 内，P' 可能是岛；如果有些点落在大多边形 P 以外，则可能有某种错误，操作员应进行必要的检查。

（三）拓扑结构编码方法 - 图1 （三）拓扑结构编码方法 - 图2

计算多边形面积：按梯形法则计算每个多边形的面积，并把所计算的面积作为多边形的属性数据存储。由于地理数据中，多边形可能具有几百个边界坐标点，而且多边形网络中常包括多个岛屿。计算机计算面积的有效方法是尽可能只算一次，因此湖泊水域面积最好是从湖的外沿多边形面积中减去岛的面积（如果湖中有岛的话）。
属性数据与多边形的连接：建立完整拓扑多边形数据结构的最后一步是把多边形图形数据与对应的属性数据连接在一起。属性数据即描述多边形特性的一切自然、社会经济数据。这两类数据的连接具有唯一性。

多边形识别符的建立有两种方法：

在每个多边形内数字化一个文本实体作为数据输入的一部分，或者在多边形形成后交互地输入。文本实体可以是文字、号码、名称等，但整个多边形网必须统一，而且每个多边形的识别符不能相同，即需在各自的记录中加入唯一的识别符或称关键字，并将二者的识别符再存储在另一文件—— 关系表中，以便参照查找。
由程序自动寻找多边形的中央点，并在该点写上多边形的识别符（大多数程序都是顺序号），并打印出这些识别符列表，用户按表再把对应的识别符写入属性数据文件中去，或建立关系表，以供图形和属性相互参照查找使用。

虽然建立这类复杂的拓扑多边形网数据结构需要有相当的计算机能力和复杂的软件，但这类数据结构有如下优点：

多边形网络完全综合成一个整体，没有重叠和漏洞，也没有过多的冗余数据；
全部多边形、链、属性数据均为内部连接在一起的整体单元的一部分，可以进行任何类型的邻域分析。而且能将属性数据与链连接后再进行分析；
多边形中嵌套多边形没有限制，可以无限地嵌套。例如，湖→岛→ 小湖→小岛，等等。
数据库的位置精度只受数字化的精度和计算机字长的限制
数据结构与数据收集和输入的牵连不多。