复杂多边形快速融合算法与实现

2016-12-26刘学军

地理空间信息 2016年3期

关键词：多边形交点顶点

杨洋，刘学军，肖斐

（1. 61175部队，江苏南京 210049；2. 南京师范大学，江苏南京 210046；3. 香港理工大学，香港 999077）

复杂多边形快速融合算法与实现

杨洋1，刘学军2，肖斐3

（1. 61175部队，江苏南京 210049；2. 南京师范大学，江苏南京 210046；3. 香港理工大学，香港 999077）

空间矢量数据结构复杂且信息丰富，复杂多边形作为矢量数据的重要组成部分，可由多个外环链和内环链组合而成，复杂的拓扑关系给相应算法的实现带来了极大困难。多边形快速融合作为GIS的基本功能，需要快速实现对任意、多个、复杂多边形的融合处理。根据多边形重心进行行列划分，利用排斥实验和多线程技术，实现了对任意多个复杂多边形的快速合并。算法已在生产实践中得到应用。

复杂多边形；快速融合；多线程；排斥实验

实现对任意多个复杂多边形的快速融合对计算机辅助制图、GIS矢量计算、计算机辅助设计等领域具有重要意义[1]。然而，现有软件和算法在解决该问题上仍不够全面，如传统多边形综合方法主要基于栅格图像，通过数学形态学方法来合并多边形[2]；大部分GIS软件只实现了对简单多边形的两两合并，或多边形合并必须满足一定条件（如ArcGIS、MapGIS）。文献[2]对多边形进行CDT剖分，通过聚类实现对相接和相邻多边形的融合来实现自动制图综合，但算法效率和准确度不高，且未考虑属性约束条件；文献[3]、[4]只实现了对包含重复边的左右多边形的融合，复杂的拓扑构建和限定的适用条件使得算法普适性较差；文献[5]只实现了对凸多边形的融合，提出对凹多边形的融合是将其分解为多个凸多边形，但当多边形极度破碎时仅分解凹多边形就会带来很大开销，且没有考虑更为复杂的情况；文献[6]提出基于扫描线技术的合并算法，可解决非简单多边形和病态多边形，但算法欠缺对内部多边形的合并且回路顶点维护复杂。

据此，本文以带有属性特征的复杂多边形作为研究对象，包括凹凸多边形和含岛嵌套多边形，提出了基于复杂多边形重心的网格划分法，并结合排斥实验、多线程处理来提高对多个复杂多边形的处理速率，结合计算几何[7]中的空间矢量求交算法实现了对任意相交或相接的复杂多边形的快速融合，并已在实际生产中得到大量数据的验证。

1 算法基础

1.1 问题描述

复杂多边形由多个互不相交且属性相同的外环链和内环链组成。环链根据顶点序列方向的不同进行划分：逆时针为外环链，顺时针为内环链。复杂多边形相互融合即各环链进行相交计算并重新组合的过程，融合过程中需要解决对顶点序列的维护、对点与环链空间关系的判断、对多边形进行拓扑重构等问题。

1.2 线段间求交

采用排斥实验减少求交次数，通过跨立实验准确判断相交。如果两条线段相交则必然相互跨立，则线段P1P2跨立Q1Q2（图1）的依据为：

两条线段相交分为8种情况（图2）：a中P1P2、Q1Q2交于A点；b中P1P2新增交点Q1；c中Q1Q2新增交点P2；d中P1P2新增交点Q1、Q2；e中Q1Q2新增交点P1、P2；f和h中无新增交点；g中P1P2新增交点Q1，Q1Q2新增交点。

图1 快速排斥实验与跨立实验[8]

图2 线段相交的8种情况

1.3 环链自相交检测

环链自相交检测的目的是维护环链几何特征的一致性，是数据预处理的关键部分。当组成环链的线段除了顶点外还存在其他相交点则认为环链自相交（或称病态多边形[6]），处理过程为：

1）对组成环链的线段进行线段间求交，判断是否存在新的相交点，若存在则向下执行（图3a、图4a、图5a）；不存在则停止处理。

2）按原线段方向对交点进行排序，并分割线段。

3）对分割后的线段集进行闭合环链搜索，生成新的环链集合（图3b、图4b、图5b）。

4）若新生成环链面积小于阈值则舍去。

5）检测环链间的包含关系：当环链相嵌套时，保留最外层的环链（图3b舍去L2）；当环链属性相同但不嵌套时不进行处理（图4b保留L1、L2、L3）；剔除与原始环链属性不同的新生成的环链（图5b舍去L2、L4）。

1.4 点与环链位置关系的判断

图3 环链内部的自相交

图4 相连情况下的环链自相交

点与任意形状环链的关系可分为外部点、内部点、顶点和边界点，图6中描述了由顶点序列组成的外环链L与任意点Q的4种位置关系。鉴于射线法的缺陷[10]，本文采用角度累加判别法[11]，其原理为沿环链顶点顺序求点Q与顶点构成的方向线的夹角（如QP1到QP2的角度θ1），以逆时针为正，顺时针为负，范围为最后得到角度的和当Q与P中任意一点相等时，Q为顶点；当Q位于L的某一条边上时加权，Q为边界点；当L为外环链，且ω=360°时，Q为内部点，否则Q为外部点；当L为内环链，且ω=-360°时，Q为外部点，否则Q为内部点。

图6 点与外环链的位置关系

1.5 环链间相交计算

复杂多边形的融合可分解成环链间的两两融合，因此判断环链间位置关系是关键。环链间位置关系的判断建立在点与环链位置关系判断的基础上，通过环链最小包围盒的排斥实验可以排除一部分相离的环链，表1中列出了两条环链可能的位置关系、判断条件和融合结果。

1.6 多边形间融合

表1 环链间位置关系的判断

多边形融合的步骤为：①对环链进行两两相交，新生成的相交点对原环链进行打断（图7a）；②判断环链A与环链B的位置关系，生成融合结果；③完成对两个多边形所有环链的融合；④对多边形自身环链进行相交处理，消除重叠部分的环链；⑤通过正面积法来确定环链间包含关系[12]，生成新的多边形，图7b为数据进行合并后的结果。

图7 多个环链的合并

2 算法设计

2.1 算法流程

复杂多边形的融合需要对输入的初始多边形进行预处理，如消除重复点、闭合环链、环链的自相交检测等，将多边形对象转化为本算法所定义的数据结构，再进行多边形的融合，具体流程如图8所示。

2.2 数据结构

图8 算法流程图

描述复杂多边形的数据结构包括点结构、线结构和环链结构，其数据结构定义如下：

//点结构

Class PointF{

Private:

float x, y;

}

//线结构

Class LineF{

Private:

PointF p1, p2;

float angle;

}

//环链结构

Class LinkAttri{

Private:

LinkStyle linkstyle; //内外属性值为OutLoop, InnerLoop

Vector

bool crossed; //是否与其他链相交

PlyDirection plydirect; //环链的走向值为Deasil, AntiClockwise, Exceptional

Corner4Points linkcorner4points; //环链包围盒4 个角点坐标

LinkAttri(){

crossed = false;

}

};

//复杂多边形结构

Class Polygon{

Private:

int linknum; //环链个数

Map

Corner4Points plycorner4points; //多边形包围盒4个角点坐标

Vector

PointF geocenter; //多边形的重心

}

2.3 基于重心的网格划分

当所需处理的复杂多边形数量多、结构复杂、分布散乱、破碎度高时，按存储顺序进行多边形的两两融合会导致空间与时间开销大、处理效率低。已有文献中采用队列[13]、建立四叉树索引[1]等方法来加快数据的处理速度。鉴于复杂多边形空间形态的多样性，规则的四叉树并不合适多边形的划分，本文将多边形的几何重心点作为划分对象，计算公式为：

图9 按多边形的重心进行行列划分

3 实验分析

本算法的实验平台为Qt 5.3.0，待处理数据通过文本进行读取。对比ArcGIS中的合并操作Dissolve和Eliminate，所处理的多边形都非复杂多边形，前者可将所选多边形全部合并成一个，但丢失多边形属性，后者在合并中保留属性，但不能一次合并很多，只能两两合并；而MapGIS中只能顺次选择合并2个相邻区域，且多边形也非复杂多边形。本算法在考虑属性的同时实现了对多个复杂多边形的快速融合，普适性强。

1）多个简单多边形的融合。图10a中不同颜色代表不同的多边形，合并后生成的复杂多边形由2个外环和2个内环构成，如图10b所示。