GIS多边形生成算法改进
摘要：本文对GIS系统进行简要介绍，列举了GIS多边形生成的传统算法，分析其优缺点，对拓扑映射进行了简要的介绍，进而提出了一种基于拓扑映射法的多边形生成算法，改进了传统算法。该算法避免了多边形的反复搜索和角度的计算，减少了多边形生成的计算量，提升了GIS多边形生成的计算速度。
关键词：GIS；多边形；传统算法；拓扑映射
1引言
GIS即地理信息系统（Geographic Information System或 Geo－Information system）有时又称为“地学信息系统”。它是一种特定的十分重要的空间信息系统。它是在计算机硬、软件系统支持下，对整个或部分地球表层（包括大气层）空间中的有关地理分布数据进行采集、储存、管理、运算、分析、显示和描述的技术系统。GIS属于信息系统的一类，不同在于它能运作和处理地理参照数据[1]。地理参照数据描述地球表面(包括大气层和较浅的地表下空间)空间要素的位置和属性，在GIS中的两种地理数据成分：空间数据，与空间要素几何特性有关；属性数据，提供空间要素的信息。
在GIS 中，空间对象用几何位置及对象间的空间关系来描述。其中，空间关系常采用拓扑几何的方法来表示，它描述了点、线和面之间的邻接、关联和包含关系，是实施空间分析的基础和前提。拓扑几何关系的生成算法，尤其是多边形拓扑关系的生成算法是GIS 中的关键算法之一。
2传统算法
传统的建立空间图形点、线、面拓扑关系的算法，需要结合几何信息和拓扑信息，对可能生成的多边形进行内角的计算与比较以及坐标的比较，而且必须反复搜索，不仅费时而且有一些特殊情况需要处理；如果在建立拓扑关系之前，已经获得了相关多边形的标识点，则可以根据事先建好的结点弧段的拓扑关系，结合标识点，采用“跌落法”（或称为“垂线法”）进行搜索，自动建立多边形的拓扑关系。“跌落法”避免了多边形内角的计算和多边形的反复搜索，减少了搜索的工作量而且没有特殊情况需要处理，在一定程度上提高了建立多边形拓扑关系的效率但也有其局限性。因为在实际应用中，多边形的标识点往往需要在多边形拓扑关系建立之后才能确定。
东华理工学院测量系李大军等人提出了拓扑多边形自动构建的一种改进算法，该算法提出了一种基于方位角定义的多边形自动构建方案[2]，其基本思路是：(1)弧段邻接关系确定；
1
(2)弧段方位角计算； (3)多边形搜索； (4)拓扑关系确定.该算法较之其它算法的特点是：(1)只进行2N(N为弧段数)次方位角计算，籍此就可以搜索出所有的多边形；(2)多边形拓扑关系的确定摈弃了面积的计算，而借助于点与多边形的包含关系进行判定；(3)内点生成简便易行。
东南大学的张秀霞等人提出了基于有向弧的改进多边形拓扑关系生成算法，该算法提出了一种寻找多边形拓扑关系的算法，在建立多边形拓扑关系之前，一般可以通过数字化或半数字化的方式直接获得弧段- 结点邻接关系，然后可以由此计算出结点- 弧段邻接表，算法比较简单，在此不作讨论。计算得出的结点- 弧段邻接表中，每个结点的关联弧段按其方位角大小排序（方位角的计算以结点与它相邻的下一个顶点为方向），约定该序列中最后一条弧与第一条弧在空间位置上也是相邻的。
该算法建立多边形拓扑关系的具体过程如下图所示：
[3]
图1 算法结构图
注：一条弧段的“后序弧段”即指在一个结点的弧段序列中排在该弧段后面的弧段，按照前面对弧段序列排队的补充约定，弧段序列中最后一条弧段的后序弧段是第一条弧段，所
2
以图2 中* 处对M［］中的第一条弧段（M[0]）做了相关判断。
根据前面对弧段方向的规定，一条起始点为A 终止点为B 的弧段，在A、B 结点的关联弧段序列中表现出不同的方向，即dir 字段的值不同。遍历搜索这些弧段序列时，将遍历过的相应弧段（有向弧，即dir 字段不同）的flag 字段记为false，在后序的遍历搜索中将“越过”这些flag 为false 的有向弧。
3传统算法的优缺点
“跌落法”避免了多边形内角的计算和多边形的反复搜索，减少了搜索的工作量而且没有特殊情况需要处理，在一定程度上提高了建立多边形拓扑关系的效率但也有其局限性。因为在实际应用中[4]，多边形的标识点往往需要在多边形拓扑关系建立之后才能确定。这样减少了算法的自动化，人工干预过多。
基于“跌落法”需要人工输入内点位置，东华理工学院测量系李大军等人提出了基于方位角计算的拓扑多边形自动构建快速算法，该算法可以简便快速生成内点，但是它的思路还是和传统的算法类似，没有在速度上提出创新。基于算法计算速度的创新，东南大学的张秀霞等人提出了基于有向弧的改进多边形拓扑关系生成算法，该算法在比较内角的基础上，在算法中加入了“dir”和“flag”字段，减少了算法的无效洄游，同时也加快了算法的计算效率，但是引入了“dir”和“flag”字段，加快了算法的运算速度，同时也增加了算法所占据的内存。该算法的主要计算量是计算每个结点关联弧段的方位角并按方位角大小对弧段排序。如果结点数目为N，结点的平均度数为m，则方位角的计算量为N*m/2，在一个结点处需要进行m（m- 1）/2 次角度比较。角度的计算在计算机中处理起来是相当影响工作效率的，如果能找到一种避免角度计算也能准确选择路径的方法，则可以大大提高计算效率。
4分支处多路径的拓扑映射
设当路径边为AB，过分支处B有m条路径，这m条路径由直线或圆弧构成。由于圆弧路径走向是通过分支处圆弧切线来确定的，因此在判别路径走向时这m条路径均可视为直线
[6]
。
以B为圆心，如图2所示，该圆周与m条路径存在m个交点。显然，过B的下一路径走向
与交点在圆周上的分布有关。实际上，判别下一路径时，当前路径AB及外侧点O均为已知，则交点沿圆周的位置分布决定这分支处B的下一路径走向。
3
图2 多路径分支点
5 多边形拓扑映射路径判别
外侧点O（X0，Y0）在射影直线上的映射点为XX0，该点将所在的射影直线分开，如图6所示。除左右无穷远点，各路径映射点可大致分成三个集。
a={与XXO同一射影直线其X坐标大于XX0的映射点} b={另一射影直线的映射点}
c={与XXO同一射影直线其X坐标小于XXO的映射点}
图3路径走向判别
根据当前路径及外侧点O，映射点走向优先级别从高到低的排序为： 当路径AB倾斜时
（a）外侧点的映射点在A的右侧（XX0>XA）
a集坐标从小到大右无穷远点b集坐标从大到小左无穷远点c集坐标从小到大 （b）外侧点的映射点在A的左侧（XX0 4 c集坐标从大到小左无穷远点b集坐标从小到大右无穷远点a集坐标从大到小 当路径AB水平时 （a）外侧点在A的右侧（X0>XA） 映射点走向排序筒倾斜时的情况（a） （b）外侧点在A的左侧（XX0 映射点走向的优先级代表着相同路径走向的优先级，在判别过分支处下一路径走向时，只要优先级高的映射点集非空，则可从该点集中求得走向最优的点即可，后续映射点无需进行一一排序。 6 传统算法与拓扑映射路径对比 设当前路径AB，外侧点o，过分支点B的候选路径有m条，分别为BT1、BT2，??，BTm。 以一个分支点求取下一路径为例，角度法和拓扑映法的计算量比较为： 表1 角度法和拓扑映法的计算量比较表 路径走向求取法 计算内容 1）求每条候选路径与X轴的夹角 2）当前路径AB与X轴的夹角及BO与X轴的夹角 角度法 3）求每条路径与AB间的夹角，要求每一夹角均包含外侧点O 4）角度大小排序（m个值排序） 1）取水平射影直线 拓扑映射法 2）由Y坐标求映射点的X坐标 3）映射点X坐标排序 角度法19（m?2）??9.5倍 拓扑映射法2(m?1)计算量比较 通过以上计算可以看出，拓扑映射法的计算速度明显比角度法要快，一次拓扑映射法可以作为一种避免角度计算也能准确选择路径的方法，可以大大提高计算效率。 参考文献 5 [1]闾国年,袁林旺,俞肇元. GIS技术发展与社会化的困境与挑战[J]. 地球信息科学学报, 2013,04:483-490. [2]李大军,刘波,赵宝贵,肖根如. 拓扑多边形自动构建的一种改进算法[J]. 计算机工程与应 用,2005,16:80-82. [3]张秀霞,蔡先华. 基于有向弧的改进多边形拓扑关系生成算法[J]. 电脑与信息技术, 2008,05:46-49. [4]闫浩文,杨维芳,陈全功,梁天刚. 基于方位角计算的拓扑多边形自动构建快速算法[J]. 中国 图象图形学报,2000,07:27-31. [5]徐立,孙群,杨帅,徐振. 地图矢量数据拓扑关系生成算法[J]. 地理与地理信息科学, 2012,04:18-21. [6]张树有,谭建荣等.产品虚拟设计与装配技术基础.[Online].浙江大学工程及计算机图学研 究所.http://vdisk.weibo.com/s/zUDaeguhD5tJv?sudaref=www.http://www.diyifanwen.net/(2016/12/7) 6
GIS多边形生成算法改进
