復(fù)雜多邊形快速融合算法與實(shí)現(xiàn)

楊 洋，劉學(xué)軍，肖 斐

（1. 61175部隊(duì)，江蘇 南京 210049；2. 南京師范大學(xué)，江蘇 南京 210046；3. 香港理工大學(xué)，香港 999077）

復(fù)雜多邊形快速融合算法與實(shí)現(xiàn)

楊 洋1，劉學(xué)軍2，肖 斐3

（1. 61175部隊(duì)，江蘇 南京 210049；2. 南京師范大學(xué)，江蘇 南京 210046；3. 香港理工大學(xué)，香港 999077）

空間矢量數(shù)據(jù)結(jié)構(gòu)復(fù)雜且信息豐富，復(fù)雜多邊形作為矢量數(shù)據(jù)的重要組成部分，可由多個(gè)外環(huán)鏈和內(nèi)環(huán)鏈組合而成，復(fù)雜的拓?fù)潢P(guān)系給相應(yīng)算法的實(shí)現(xiàn)帶來了極大困難。多邊形快速融合作為GIS的基本功能，需要快速實(shí)現(xiàn)對(duì)任意、多個(gè)、復(fù)雜多邊形的融合處理。根據(jù)多邊形重心進(jìn)行行列劃分，利用排斥實(shí)驗(yàn)和多線程技術(shù)，實(shí)現(xiàn)了對(duì)任意多個(gè)復(fù)雜多邊形的快速合并。算法已在生產(chǎn)實(shí)踐中得到應(yīng)用。

復(fù)雜多邊形；快速融合；多線程；排斥實(shí)驗(yàn)

實(shí)現(xiàn)對(duì)任意多個(gè)復(fù)雜多邊形的快速融合對(duì)計(jì)算機(jī)輔助制圖、GIS矢量計(jì)算、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域具有重要意義[1]。然而，現(xiàn)有軟件和算法在解決該問題上仍不夠全面，如傳統(tǒng)多邊形綜合方法主要基于柵格圖像，通過數(shù)學(xué)形態(tài)學(xué)方法來合并多邊形[2]；大部分GIS軟件只實(shí)現(xiàn)了對(duì)簡單多邊形的兩兩合并，或多邊形合并必須滿足一定條件（如ArcGIS、MapGIS）。文獻(xiàn)[2]對(duì)多邊形進(jìn)行CDT剖分，通過聚類實(shí)現(xiàn)對(duì)相接和相鄰多邊形的融合來實(shí)現(xiàn)自動(dòng)制圖綜合，但算法效率和準(zhǔn)確度不高，且未考慮屬性約束條件；文獻(xiàn)[3]、[4]只實(shí)現(xiàn)了對(duì)包含重復(fù)邊的左右多邊形的融合，復(fù)雜的拓?fù)錁?gòu)建和限定的適用條件使得算法普適性較差；文獻(xiàn)[5]只實(shí)現(xiàn)了對(duì)凸多邊形的融合，提出對(duì)凹多邊形的融合是將其分解為多個(gè)凸多邊形，但當(dāng)多邊形極度破碎時(shí)僅分解凹多邊形就會(huì)帶來很大開銷，且沒有考慮更為復(fù)雜的情況；文獻(xiàn)[6]提出基于掃描線技術(shù)的合并算法，可解決非簡單多邊形和病態(tài)多邊形，但算法欠缺對(duì)內(nèi)部多邊形的合并且回路頂點(diǎn)維護(hù)復(fù)雜。

據(jù)此，本文以帶有屬性特征的復(fù)雜多邊形作為研究對(duì)象，包括凹凸多邊形和含島嵌套多邊形，提出了基于復(fù)雜多邊形重心的網(wǎng)格劃分法，并結(jié)合排斥實(shí)驗(yàn)、多線程處理來提高對(duì)多個(gè)復(fù)雜多邊形的處理速率，結(jié)合計(jì)算幾何[7]中的空間矢量求交算法實(shí)現(xiàn)了對(duì)任意相交或相接的復(fù)雜多邊形的快速融合，并已在實(shí)際生產(chǎn)中得到大量數(shù)據(jù)的驗(yàn)證。

1 算法基礎(chǔ)

1.1 問題描述

復(fù)雜多邊形由多個(gè)互不相交且屬性相同的外環(huán)鏈和內(nèi)環(huán)鏈組成。環(huán)鏈根據(jù)頂點(diǎn)序列方向的不同進(jìn)行劃分：逆時(shí)針為外環(huán)鏈，順時(shí)針為內(nèi)環(huán)鏈。復(fù)雜多邊形相互融合即各環(huán)鏈進(jìn)行相交計(jì)算并重新組合的過程，融合過程中需要解決對(duì)頂點(diǎn)序列的維護(hù)、對(duì)點(diǎn)與環(huán)鏈空間關(guān)系的判斷、對(duì)多邊形進(jìn)行拓?fù)渲貥?gòu)等問題。

1.2 線段間求交

采用排斥實(shí)驗(yàn)減少求交次數(shù)，通過跨立實(shí)驗(yàn)準(zhǔn)確判斷相交。如果兩條線段相交則必然相互跨立，則線段P1P2跨立Q1Q2（圖1）的依據(jù)為：

兩條線段相交分為8種情況（圖2）：a中P1P2、Q1Q2交于A點(diǎn)；b中P1P2新增交點(diǎn)Q1；c中Q1Q2新增交點(diǎn)P2；d中P1P2新增交點(diǎn)Q1、Q2；e中Q1Q2新增交點(diǎn)P1、P2；f和h中無新增交點(diǎn)；g中P1P2新增交點(diǎn)Q1，Q1Q2新增交點(diǎn)。

圖1 快速排斥實(shí)驗(yàn)與跨立實(shí)驗(yàn)[8]

圖2 線段相交的8種情況

1.3 環(huán)鏈自相交檢測(cè)

環(huán)鏈自相交檢測(cè)的目的是維護(hù)環(huán)鏈幾何特征的一致性，是數(shù)據(jù)預(yù)處理的關(guān)鍵部分。當(dāng)組成環(huán)鏈的線段除了頂點(diǎn)外還存在其他相交點(diǎn)則認(rèn)為環(huán)鏈自相交（或稱病態(tài)多邊形[6]），處理過程為：

1）對(duì)組成環(huán)鏈的線段進(jìn)行線段間求交，判斷是否存在新的相交點(diǎn)，若存在則向下執(zhí)行（圖3a、圖4a、圖5a）；不存在則停止處理。

2）按原線段方向?qū)稽c(diǎn)進(jìn)行排序，并分割線段。

3）對(duì)分割后的線段集進(jìn)行閉合環(huán)鏈搜索，生成新的環(huán)鏈集合（圖3b、圖4b、圖5b）。

4）若新生成環(huán)鏈面積小于閾值則舍去。

5）檢測(cè)環(huán)鏈間的包含關(guān)系：當(dāng)環(huán)鏈相嵌套時(shí)，保留最外層的環(huán)鏈（圖3b舍去L2）；當(dāng)環(huán)鏈屬性相同但不嵌套時(shí)不進(jìn)行處理（圖4b保留L1、L2、L3）；剔除與原始環(huán)鏈屬性不同的新生成的環(huán)鏈（圖5b舍去L2、L4）。

1.4 點(diǎn)與環(huán)鏈位置關(guān)系的判斷

圖3 環(huán)鏈內(nèi)部的自相交

圖4 相連情況下的環(huán)鏈自相交

點(diǎn)與任意形狀環(huán)鏈的關(guān)系可分為外部點(diǎn)、內(nèi)部點(diǎn)、頂點(diǎn)和邊界點(diǎn)，圖6中描述了由頂點(diǎn)序列組成的外環(huán)鏈L與任意點(diǎn)Q的4種位置關(guān)系。鑒于射線法的缺陷[10]，本文采用角度累加判別法[11]，其原理為沿環(huán)鏈頂點(diǎn)順序求點(diǎn)Q與頂點(diǎn)構(gòu)成的方向線的夾角（如QP1到QP2的角度θ1），以逆時(shí)針為正，順時(shí)針為負(fù)，范圍為最后得到角度的和當(dāng)Q與P中任意一點(diǎn)相等時(shí)，Q為頂點(diǎn)；當(dāng)Q位于L的某一條邊上時(shí)加權(quán)，Q為邊界點(diǎn)；當(dāng)L為外環(huán)鏈，且ω=360°時(shí)，Q為內(nèi)部點(diǎn)，否則Q為外部點(diǎn)；當(dāng)L為內(nèi)環(huán)鏈，且ω=-360°時(shí)，Q為外部點(diǎn)，否則Q為內(nèi)部點(diǎn)。

圖6 點(diǎn)與外環(huán)鏈的位置關(guān)系

1.5 環(huán)鏈間相交計(jì)算

復(fù)雜多邊形的融合可分解成環(huán)鏈間的兩兩融合，因此判斷環(huán)鏈間位置關(guān)系是關(guān)鍵。環(huán)鏈間位置關(guān)系的判斷建立在點(diǎn)與環(huán)鏈位置關(guān)系判斷的基礎(chǔ)上，通過環(huán)鏈最小包圍盒的排斥實(shí)驗(yàn)可以排除一部分相離的環(huán)鏈，表1中列出了兩條環(huán)鏈可能的位置關(guān)系、判斷條件和融合結(jié)果。

1.6 多邊形間融合

表1 環(huán)鏈間位置關(guān)系的判斷

多邊形融合的步驟為：①對(duì)環(huán)鏈進(jìn)行兩兩相交，新生成的相交點(diǎn)對(duì)原環(huán)鏈進(jìn)行打斷（圖7a）；②判斷環(huán)鏈A與環(huán)鏈B的位置關(guān)系，生成融合結(jié)果；③完成對(duì)兩個(gè)多邊形所有環(huán)鏈的融合；④對(duì)多邊形自身環(huán)鏈進(jìn)行相交處理，消除重疊部分的環(huán)鏈；⑤通過正面積法來確定環(huán)鏈間包含關(guān)系[12]，生成新的多邊形，圖7b為數(shù)據(jù)進(jìn)行合并后的結(jié)果。

圖7 多個(gè)環(huán)鏈的合并

2 算法設(shè)計(jì)

2.1 算法流程

復(fù)雜多邊形的融合需要對(duì)輸入的初始多邊形進(jìn)行預(yù)處理，如消除重復(fù)點(diǎn)、閉合環(huán)鏈、環(huán)鏈的自相交檢測(cè)等，將多邊形對(duì)象轉(zhuǎn)化為本算法所定義的數(shù)據(jù)結(jié)構(gòu)，再進(jìn)行多邊形的融合，具體流程如圖8所示。

2.2 數(shù)據(jù)結(jié)構(gòu)

圖8 算法流程圖

描述復(fù)雜多邊形的數(shù)據(jù)結(jié)構(gòu)包括點(diǎn)結(jié)構(gòu)、線結(jié)構(gòu)和環(huán)鏈結(jié)構(gòu)，其數(shù)據(jù)結(jié)構(gòu)定義如下：

//點(diǎn)結(jié)構(gòu)

Class PointF{

Private:

float x, y;

}

//線結(jié)構(gòu)

Class LineF{

Private:

PointF p1, p2;

float angle;

}

//環(huán)鏈結(jié)構(gòu)

Class LinkAttri{

Private:

LinkStyle linkstyle; //內(nèi)外屬性 值為OutLoop, InnerLoop

Vector

bool crossed; //是否與其他鏈相交

PlyDirection plydirect; //環(huán)鏈的走向值為Deasil, AntiClockwise, Exceptional

Corner4Points linkcorner4points; //環(huán)鏈包圍盒4 個(gè)角點(diǎn)坐標(biāo)

LinkAttri(){

crossed = false;

}

};

//復(fù)雜多邊形結(jié)構(gòu)

Class Polygon{

Private:

int linknum; //環(huán)鏈個(gè)數(shù)

Map

Corner4Points plycorner4points; //多邊形包圍盒4個(gè)角點(diǎn)坐標(biāo)

Vector

PointF geocenter; //多邊形的重心

}

2.3 基于重心的網(wǎng)格劃分

當(dāng)所需處理的復(fù)雜多邊形數(shù)量多、結(jié)構(gòu)復(fù)雜、分布散亂、破碎度高時(shí)，按存儲(chǔ)順序進(jìn)行多邊形的兩兩融合會(huì)導(dǎo)致空間與時(shí)間開銷大、處理效率低。已有文獻(xiàn)中采用隊(duì)列[13]、建立四叉樹索引[1]等方法來加快數(shù)據(jù)的處理速度。鑒于復(fù)雜多邊形空間形態(tài)的多樣性，規(guī)則的四叉樹并不合適多邊形的劃分，本文將多邊形的幾何重心點(diǎn)作為劃分對(duì)象，計(jì)算公式為：

圖9 按多邊形的重心進(jìn)行行列劃分

3 實(shí)驗(yàn)分析

本算法的實(shí)驗(yàn)平臺(tái)為Qt 5.3.0，待處理數(shù)據(jù)通過文本進(jìn)行讀取。對(duì)比ArcGIS中的合并操作Dissolve和Eliminate，所處理的多邊形都非復(fù)雜多邊形，前者可將所選多邊形全部合并成一個(gè)，但丟失多邊形屬性，后者在合并中保留屬性，但不能一次合并很多，只能兩兩合并；而MapGIS中只能順次選擇合并2個(gè)相鄰區(qū)域，且多邊形也非復(fù)雜多邊形。本算法在考慮屬性的同時(shí)實(shí)現(xiàn)了對(duì)多個(gè)復(fù)雜多邊形的快速融合，普適性強(qiáng)。

1）多個(gè)簡單多邊形的融合。圖10a中不同顏色代表不同的多邊形，合并后生成的復(fù)雜多邊形由2個(gè)外環(huán)和2個(gè)內(nèi)環(huán)構(gòu)成，如圖10b所示。

圖10 簡單多邊形融合

圖11 多個(gè)復(fù)雜多邊形融合

4 結(jié) 語

本文對(duì)多邊形融合算法進(jìn)行了全面擴(kuò)展，通過基于重心的網(wǎng)格劃分，實(shí)現(xiàn)了對(duì)任意多個(gè)簡單多邊形、非簡單多邊形、復(fù)雜多邊形的快速融合處理，并通過數(shù)據(jù)預(yù)處理解決了環(huán)鏈自相交問題。對(duì)于多邊形拓?fù)浣Y(jié)構(gòu)的嚴(yán)格定義與維護(hù)，保證了其計(jì)算結(jié)果的正確性與穩(wěn)定性。

[1] 唐立文,王榮峰,廖學(xué)軍.基于四叉樹的海量空間矢量多邊形處理技術(shù)[J].裝備指揮技術(shù)學(xué)院學(xué)報(bào),2007,18(3):104-108

[2] 何宇兵.地學(xué)制圖綜合中多邊形對(duì)象的合并算法研究與應(yīng)用[D].杭州:浙江大學(xué),2007

[3] 郭仁忠,艾廷華.制圖綜合中建筑物多邊形的合并與化簡[J].武漢測(cè)繪科技大學(xué)學(xué)報(bào),2000,25(1):25-30

[4] 馬麗娜.面向大規(guī)?？臻g數(shù)據(jù)的空間計(jì)算模式研究與實(shí)現(xiàn)[D].武漢:中國地質(zhì)大學(xué),2011

[5] 黃俊華,閆遂軍,朱小龍,等.一種凸多邊形的交、并求解算法[J].桂林工學(xué)院學(xué)報(bào),2007,27(4):589-592

[6] 葉琳,邱龍輝.多邊形合并的算法研究[J].計(jì)算機(jī)應(yīng)用與軟件,2002(8):57-59

[7] 周培德.計(jì)算幾何——算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,2011

[8] Schneider P J, Eberl Y D H.計(jì)算機(jī)圖形學(xué)集合工具算法詳解[M].北京:電子工業(yè)出版社,2005

[9] 鮑其勝,王慶,何立恒.基于線段操作的多邊形求交算法研究[J].測(cè)繪通報(bào),2013(5):35-37

[10] 劉曉婧,趙俊三.判定點(diǎn)與多邊形及簡單多邊形之間的空間關(guān)系[J].科技情報(bào)開發(fā)與經(jīng)濟(jì),2008,18(28):223-224

[11] 鄒有建,肖龍?chǎng)?陳鼎.判斷某點(diǎn)是否在任意多邊形內(nèi)兩種算法的比較[J].地礦測(cè)繪,2009,25(3):28-30

[12] 彭認(rèn)燦,陳子澎,劉國輝.快速確定多邊形與多邊形包含關(guān)系的一種新方法[J].測(cè)繪通報(bào),2006(5):50-52

[13] 姚路,莫國明.地形圖房屋接邊合并算法與實(shí)現(xiàn)[J].城市勘測(cè),2005(4):28-31

P208

B

1672-4623（2016）03-0052-04

10.3969/j.issn.1672-4623.2016.03.017

楊洋，碩士，主要研究方向?yàn)槿SGIS、空間分析算法和地理空間情報(bào)。

2015-03-17。

項(xiàng)目來源：國家自然科學(xué)基金資助項(xiàng)目（41371421）。