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

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

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

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

　　⊙唯一标识；

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

　　⊙环形指针；

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

　　⊙包络多边形的面积；

　　⊙范围（包围包络多边形的矩形的最大最小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以外，则可能有某种错误，操作员应进行必要的检查。
　　本文标题：矢量数据结构(4)
　　手机页面：http://m.dljs.net/dlsk/gis/4766.html
　　本文地址：http://www.dljs.net/dlsk/gis/4766.html