袁程阳
上海南康科技有限公司 上海市徐汇区 200030
摘 要：自动构建封闭区域多边形是CAD平台中的重要功能。CAD中的边界命令在复杂图形情况下会忽略细小拐角。基于方位角变化趋势的多边形搜索算法可以有效避免该问题，结合图形拓扑关系可以处理 “岛”图形以及断头路径造成的图形自相交。算法逻辑清晰，易于代码实现。
关键词：方位角；拓扑关系；多边形
1.引言
CAD应用中面积量算是一个常用功能，一般使用对象类型为多段线，因此快速生成多段线是一个重要功能。封闭区域较大时，通过CAD的BOUNDARY命令生成多段线，会忽略部分细节。如下图（图1，图2）所示：
.png)
蓝线为底图，黑线为boundary结果，在需要精确面积量算时这个多段线会产生面积误差。因此需要一个方法，能够精确构建封闭区域的多边形。
2.方位角计算
坐标方位角是测量学中的一个基本概念，从直角坐标北方向起，顺时针旋转到某一射线间的角度；这里我们引用测量坐标方位角概念，定义方位角为从平面直角坐标系X轴正半轴开始，逆时针旋转到某一射线的角度，其值为 0~2π[1]。CAD内坐标系角度也是按照这个规则定义。如线段AB，起始点A(x1，y1)，结束点B(x2,y2)，则AB方位角θ为：
D x = x2 - x1; D y = y2 - y1;
(1) 如果 D x = 0, D y > 0, 则 θ = π/ 2
(2) 如果 D x = 0, D y < 0, 则 θ = 3π/ 2
(3) 如果 D x > 0, D y≥0, 则 θ = arctan ( Dy / Dx )
(4) 如果 D x > 0, D y < 0, 则 θ = arctan ( Dy / Dx ) + 2π
(5) 如果 D x < 0, 则 θ = arctan ( Dy / Dx ) + π/ 2
（注: D x = 0，D y = 0 时方位角不存在，这种情况不参与计算）
拓扑邻接的两弧段间的夹角是指从它们的公共端点出发的两条射线所夹的有向角，夹角的取值范围为 0~2π[2]。
3.拓扑邻接关系
对于凡具有网状结构特征的地理要素，例如，自然与行政的分区、各种资源类型的空间分布以及交通网等，都存在节点、弧段和多边形之间的拓扑关系[3]。在这里定义封闭区域边界弧段存在公共端点的认为是拓扑邻接。
如存在弧段C1(P1 , P2)，C2 (P2 , P3)，则认为C1，C2邻接（图3）。
如存在弧段C1(P1 , P2)，C2 (P3 , P4)，C1与C2相交于点P5，则以点P5为分隔点，建立新弧段C1-1(P1 , P5) ，C1-2(P5 , P2) ，C2-1(P3 , P5) ，C2-2(P5 , P4)，四条弧段都属于邻接（图4）。
.png)
（图3 – 一般邻接） （图4 – 相交邻接）
4.最小夹角搜索法
多边形的搜索按照方位角夹角角度最小原则进行。从拓扑邻接表的第一个弧段的起始点出发 , 查找拓扑邻接表中与该弧段结束点关联的弧段 , 按照最小夹角可以搜索出至多两个多边形（顺时针，逆时针搜索各一个）。依照上述方法, 依次把其它弧段作为开始弧段，共可找出 2 N（N为总弧段数）个多边形。
推导过程见图5：
.png)
（图5 – 推导过程）
4.1 按逆时针方向旋转夹角计算
（1）从弧段C1开始搜索，设定P1为起始点，P2为结束点。通过P2找到邻接弧段C2，C9。因P2为C1结束点，设定C2起始点为P2结束点为P3，设定C9起始点为P2结束点为P3。记C1方位角∠P2 P1，C2方位角∠P2 P3，C9方位角∠P2P9。既以P2作为夹角原点。
C1C2夹角 =∠P2P3 - ∠P2P1 = 90° - 270°= -180°+ 360°= 180°；
（注：如角度相减得负数，直接加360°，下略）
C1C9夹角 =∠P2P9 - ∠P2P1 = 350°- 270°= 60°；
（2）C1C9夹角最小，因此选取C9为下一个边，通过P9找到邻接弧段C10，C11，C12。同理计算弧段夹角。
C9C10夹角 = ∠P9P4 -∠P9P2 = 78°- 172°= -94°+ 360°= 266°；
C9C11夹角 = ∠P9P6 -∠P9P2 = 352°- 172°= 180°；
C9C12夹角 = ∠P9P8 -∠P9P2 = 258°- 172°= 86°；
（3）C9C12夹角最小，选取C12作为下一个边，通过P8得到邻接弧段C7，C8。
C12C7夹角 = ∠P8P7 -∠P8P9 = 0°-78°= -78°+360°= 282°；
C12C8夹角 = ∠P8P1 -∠P8P9 = 180°-78°= 102°；
（4）C12C8夹角最小，选取C8作为下一个边，此时C8结束点回归到初始点P1，完成搜索。得到多边形 C1-C9 -C12-C8。
4.2 按顺时针方向旋转夹角计算
（1）从弧段C1开始搜索，设定P1为起始点，P2为结束点。通过P2找到邻接弧段C2，C9。因P2为C1结束点，设定C2起始点为P2结束点为P3，设定C9起始点为P2结束点为P3。记C1方位角∠P2 P1，C2方位角∠P2 P3，C9方位角∠P2P9。既以P2作为夹角原点。
C1C2夹角 =∠P2P1 - ∠P2P3 = 270°- 90°= 180°；
（注：如角度相减得负数，直接加360°，下略）
C1C9夹角 =∠P2P1 - ∠P2P9 = 270°- 350°= -60° + 360°= 300°；
（2）C1C2夹角最小，因此选取C2为下一个弧段，通过P3找到邻接弧段C3。此时只有C3可选，通过C3结束点P4继续搜索，得到相邻弧段C4，C10。
C3C4夹角=∠P4P3 – P4P5 = 180°- 0°= 180°；
C3C10夹角=∠P4P3 – P4P9 = 180°- 258°= -78°+360°= 282°；
（3）C3C4夹角最小, 因此选取C4作为下一个弧段，通过P5找到邻接弧段C5，此时只有C5可选，通过C5结束点P5继续搜索，得到相邻弧段C6，C11。
C5C6夹角=∠P6P5 – P6P7 = 90°- 270°= -180°+ 360° = 180°；
C5C11夹角=∠P6P5 – P6P7 = 90°- 172°= -82°+ 360°=278°；
（4）C5C6夹角最小，因此选取C6作为下一个弧段，通过P7找到邻接弧段C7。此时只有C7可选，通过C7结束点P8继续搜索，得到相邻弧段C8，C12。
C7C8夹角=∠P8P7 – P8P1 = 0°- 180°=-180°+ 360° = 180°；
C7C12夹角=∠P8P7 – P8P9 = 0°- 78°= -78°+ 360° = 282°；
（5）C7C8夹角最小，取C8作为下一个边，此时C8结束点回归到初始点P1，完成搜索。得到多边形 C1-C2 -C3-C4-C5-C6-C7-C8；
按照最小角法则搜索出的多边形，会产生重复图形和外包图形，这两种图形都需要去除。如图5中所示，以C1作为起始弧段搜索与C8作为起始弧段搜索，其返回的搜索结果相同，均返回多边形C1-C9-C12-C8与C1-C2 -C3-C4-C5-C6-C7-C8。
对于重复多边形可以按照边界弧段个数相同，边界弧段序号一致原则来做去重。
对于外包图形则在去重结束后，找出面积最大的多边形，通过包含关系去除。
对于“岛”图形，则在建立拓扑邻接关系时，按照弧段邻接关系分组，直接将“岛”所在的组单独列出搜索，避免重复搜索。
5.CAD二次开发实现逻辑
5.1 建立端点表、弧段表、弧段邻接表
定义端点表{端点编号，端点坐标}。
定义弧段表{弧段编号，弧段类型，起点端点（编号，坐标），中点坐标, 终点端点（编号，坐标），搜索次数}。一般CAD内作为封闭区域边界的弧段有直线和圆弧两种类型，圆弧段需要获取中点用来参与计算弧段方位角。
定义弧段邻接表{弧段编号，与弧段起点连接的弧段编号，与弧段终点连接的弧段编号}。
获取弧段选择集，遍历选择集内弧段实体对象。对每一个弧段做缓冲区，获取缓冲区内的其他弧段，判断是否存在相交。如存在相交，通过交点建立新的弧段如（图4）。建立端点表、弧段表需要遵守两个原则，相邻弧段的共用端点在端点表内只添加一次；重复弧段在弧段表内只添加一次。
完成弧段遍历后，通过递归弧段表得到弧段邻接表及其邻接分组，判断弧段邻接关系时应比较端点编号而不是端点坐标，可以简化计算量。建立弧段表后，对弧段表再做一次遍历，找到只出现过一次的端点编号及其所在的弧段。该弧段为断头弧段需要从弧段表中去除。
5.2 通过弧段邻接表，按照最小夹角原则执行搜索
前一步做完后，弧段邻接表已分组。每个分组都内都是相互连通的弧段，分组之间没有连通关系，即“岛”情况已经区分出来。
遍历弧段邻接表，设置当前遍历到的弧段作为初始弧段。从初始弧段的结束端点开始搜索后续弧段，通过邻接表获取与结束端点的相邻弧段，计算方位角夹角。Cad内可以使用二维向量得到方位角。选取夹角最小的弧段作为下一步搜索基础，找到该弧段的另一个端点编号，再从邻接表中找到与该端点相邻的弧段并计算夹角。重复以上过程直到邻接表遍历完成或回归到初始路径完成一次搜索过程。
被选定的初始弧段需要搜索两次，分别按顺时针夹角及逆时针夹角搜索，记录搜索路径经过的弧段编号，存储为多边形结果表。
对于一个弧段，最多只能成为两个多边形的边界。在搜索时对弧段标记成功搜索次数，如果遍历到一个弧段时，该弧段在之前的搜索过程中已经被成功搜索过两次，则不再计算，直接执行后一个弧段搜索。
5.3 去除重复和外包
遍历弧段邻接表并按最小夹角原则搜索完成后得到一组存储多边形边界弧段编号的结果表。结果表中按弧段个数相同，边界弧段序号相同的原则判断重复多边形，并从结果表中去除。
对去重后的结果表，按照弧段编号从弧段表内取出对应的端点坐标，构建多边形对象并进行面积排序，取出面积最大的多边形，再取出面积最小的多边形，判断是否有包含关系，如存在包含关系，则面积最大的多边形为外包图形。
5.4 创建多边形实体
去重和去外包后，将剩余的多边形对象实体化，添加到CAD图纸上。
成果与结论：
CAD内置的Boundary命令，每次需要指定一个内部点生成一个包含该点的多边形。在批量处理时，假设搜索区域弧段有N个，内部点有M个，则需要进行M*N次搜索。自定义最小角搜索方法，至多只需要2N次搜索，运算效率高于Boundary命令，并且自定义搜索时可以设定端点精度，避免较小拐角被忽略。以下图（图6）为测试数据，约4200条弧段构建多段线耗时4.8秒。
.png)
(图6 – 测试样例)
扩展思路，按最小角搜索法可以获取到最小封闭区域。反过来按照最大角搜索，是否可以获取外围线？经实践，最大角搜索法可以得到一组弧段的外围线，与最小角搜索的区别在于只需要确定一条初始弧段，该弧段一定要处于这组弧段的最外侧，则在顺时针夹角逆时针夹角搜索两次后，得到面积大的多边形是外围线。
参考文献：
[1] 梁晓文、刘宗岐、陈宜金，基于夹角变化趋势的多边形自动搜索和生成算法， 中国图形图像学报第5卷A版第7期.
[2] 闫浩文、杨维芳、陈全功、梁天刚，基于方位角计算的拓扑多边形自动构建快 速算法，中国图形图像学报 第10卷 第6期.
[3] 黄杏元、马劲松，地理信息系统概论（第三版），高等教育出版社.