一種附帶緩和曲線的多邊形構(gòu)建方法

黃烈星， 康俊鋒， 溫小軍， 張春艷

（江西理工大學(xué)建筑與測(cè)繪工程學(xué)院，江西 贛州341000）

0 引 言

多邊形的周長(zhǎng)計(jì)算、面積計(jì)算和布爾運(yùn)算在實(shí)際測(cè)量工作中都有著重要的應(yīng)用[1-3].測(cè)量工作中有時(shí)需要處理含有緩和曲線多邊形，這類(lèi)多邊形比普通多邊形更加難以處理而且情況復(fù)雜.目前，國(guó)內(nèi)外許多學(xué)者分別對(duì)緩和曲線和多邊形處理問(wèn)題進(jìn)行了深入研究，并提出了各自的算法.針對(duì)緩和曲線的計(jì)算與處理，馮曉等[4]針對(duì)不同類(lèi)型緩和曲線正算與反算的通用算法進(jìn)行了研究，提出了緩和曲線坐標(biāo)計(jì)算方法；殷海峰等[5]則提出了可以從任意一點(diǎn)開(kāi)始起算，并且計(jì)算項(xiàng)數(shù)可以進(jìn)行靈活擴(kuò)充的緩和曲線的正算與反算的通用算法.針對(duì)多邊形的面積處理，李亞玲[6]在多邊形面積的計(jì)算與面積法的應(yīng)用中，分析總結(jié)了多種多邊形面積計(jì)算方法；李凱等[7]提出了平面六邊形格網(wǎng)面積計(jì)算公式并進(jìn)行驗(yàn)證.針對(duì)多邊形的布爾運(yùn)算，Vatti B R[8]和Greiner Hoemann[9]在針對(duì)點(diǎn)數(shù)較大多邊形布爾運(yùn)算問(wèn)題，分別提出了Vatti算法和Greiner Hoemann算 法；Francisco Martínez 等[10]針 對(duì)含孔洞的凹多邊形的布爾運(yùn)算問(wèn)題，提出了一種簡(jiǎn)單易懂，便于實(shí)現(xiàn)的算法；彭杰等[11]針對(duì)多邊形布爾運(yùn)算問(wèn)題，提出了一種基于交點(diǎn)排序的算法；Francisco Martínez等[12]針對(duì)凹多邊形，帶孔的多邊形，多個(gè)輪廓和自相交邊的多邊形提出了高效的布爾運(yùn)算算法.趙軍等[13]提出了基于最小回路確定孔洞多邊形P和多邊形Q的交、并、差計(jì)算方法解決了孔洞多邊形的布爾運(yùn)算問(wèn)題；齊東洲等[14]針對(duì)多邊形的布爾計(jì)算提出了一種基于交點(diǎn)的多邊形并交差算法，該算法采用循環(huán)單鏈表數(shù)據(jù)結(jié)構(gòu)，能夠很好地處理一些包括重疊邊、交點(diǎn)為邊的頂點(diǎn)等邊界情形.劉思遠(yuǎn)[15]則通過(guò)交點(diǎn)處四個(gè)矢量邊的運(yùn)算決定交并差結(jié)果環(huán)的走向，避免了二維布爾運(yùn)算中的重點(diǎn)、重邊等奇異問(wèn)題；黃志等[16]針對(duì)多邊形集合的求交問(wèn)題，提出了基于多級(jí)格網(wǎng)的多邊形集合求并算法；S a^m Landier[17]則提出浮點(diǎn)算術(shù)算法用于解決上任意多邊形和多面體網(wǎng)格的布爾運(yùn)算問(wèn)題.這些研究成果為緩和曲線及多邊形處理問(wèn)題提供了理論基礎(chǔ)，但是針對(duì)復(fù)雜嵌套且附帶緩和曲線的多邊形處理問(wèn)題鮮有研究.本文主要從緩和曲線，多邊形的幾何特點(diǎn)對(duì)緩和曲線和多邊形進(jìn)行建模，構(gòu)建出附帶緩和曲線的多邊形模型，實(shí)現(xiàn)了附帶緩和曲線多邊形的周長(zhǎng)計(jì)算、面積計(jì)算和布爾運(yùn)算.

1 附帶緩和曲線多邊形模型

本節(jié)將介紹附帶緩和曲線多邊形模型中涉及的一些概念和基本原理.

1.1 附帶緩和曲線多邊形定義

多邊形是由三條或三條以上的線段首尾順次連接所組成的平面圖形.在普通多邊形中線段主要為直線段與圓弧段，而測(cè)量多邊形中可能會(huì)含有緩和曲線段.為了便于描述，稱含有緩和曲線段的多邊形為附帶緩和曲線多邊形.附帶緩和曲線多邊形可以含有一條或多條完整緩和曲線(部分緩和曲線段).測(cè)量工作中，可能會(huì)遇到多個(gè)多邊形嵌套構(gòu)成的圖形.為了結(jié)合測(cè)量實(shí)際工作，文中所指附帶緩和曲線多邊形模型為一個(gè)或多個(gè)相互嵌套但不相交的含緩和曲線段多邊形的集合.如圖1所示為一個(gè)復(fù)雜嵌套附帶緩和曲線多邊形，圖1中的23段與45段為緩和曲線段，該多邊形由4個(gè)多邊形嵌套組成.

圖1 附帶緩和曲線多邊形

1.2 附帶緩和曲線多邊形模型構(gòu)建

在對(duì)多邊形模型構(gòu)建前，需要先構(gòu)建線段模型.附帶緩和曲線多邊形模型中包含的線段有：直線段、圓弧線段、緩和曲線段.

1.2.1 線段模型構(gòu)建

在線段模型中，直線段構(gòu)建較簡(jiǎn)單.構(gòu)建的內(nèi)容主要有直線的起點(diǎn)，直線的終點(diǎn)以及直線交點(diǎn)計(jì)算[18].圓曲線段用圓弧線段表示，圓弧線段的主要內(nèi)容有圓弧的圓心、半徑、圓弧起始角度、圓弧終止角度.在多邊形中，圓弧主要涉及圓弧與圓弧交點(diǎn)計(jì)算，圓弧與直線交點(diǎn)計(jì)算[18].

緩和曲線段內(nèi)容主要包括緩和曲線數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)[19]，緩和曲線段算法設(shè)計(jì).緩和曲線段的處理主要包括坐標(biāo)轉(zhuǎn)換和交點(diǎn)計(jì)算.坐標(biāo)轉(zhuǎn)換指的是將測(cè)量坐標(biāo)系坐標(biāo)轉(zhuǎn)換為緩和曲線坐標(biāo)系坐標(biāo)；交點(diǎn)計(jì)算包括緩和曲線段與直線段交點(diǎn)計(jì)算，緩和曲線段與圓弧段交點(diǎn)計(jì)算，緩和曲線段與緩和曲線段交點(diǎn)計(jì)算.

1）緩和曲線段數(shù)據(jù)結(jié)構(gòu)

緩和曲線：緩和曲線的起點(diǎn)，緩和曲線的終點(diǎn)，緩和曲線的長(zhǎng)度，緩和曲線的方向角，半徑，是否右轉(zhuǎn)以及緩和曲線方向是否與線前進(jìn)方向一致等屬性，具體如表1所示.

2）緩和曲線段的交點(diǎn)計(jì)算

緩和曲線段計(jì)算中最重要的是坐標(biāo)計(jì)算，根據(jù)緩和曲線的長(zhǎng)度，半徑等關(guān)系得出緩和曲線段任意點(diǎn)的坐標(biāo).關(guān)于緩和曲線坐標(biāo)計(jì)算，李偉等[20]和殷海峰等[5]提出了切實(shí)可用的算法.其次是緩和曲線段與直線段，圓弧段，緩和曲線段的交點(diǎn)計(jì)算.對(duì)于交點(diǎn)計(jì)算，采取思路為：將緩和曲線按一定間距分段成a段直線段 （為了保證計(jì)算精度定義a＞20，a可以根據(jù)實(shí)際情況進(jìn)行修改），將每個(gè)直線段分別與直線段或者圓弧段進(jìn)行交點(diǎn)計(jì)算，交點(diǎn)計(jì)算的結(jié)果為緩和曲線與直線的交點(diǎn)結(jié)果.緩和曲線段與圓弧段以及緩和曲線段與緩和曲線段算法思路類(lèi)似.

表1 緩和曲線的屬性

1.2.2 多邊形模型構(gòu)建

1）判斷點(diǎn)與多邊形關(guān)系

在進(jìn)行附帶緩和曲線多邊形構(gòu)建與布爾運(yùn)算時(shí)需要多次判斷某個(gè)點(diǎn)是否在多邊形內(nèi)部.判斷一個(gè)點(diǎn)是否在多邊形內(nèi)部有多種方法[21]，文中算法采用引射線法判斷點(diǎn)是否在多邊形內(nèi)部，基本原理如下：以測(cè)試點(diǎn)為基點(diǎn)，分別以向左和向右做射線.射線分別與多邊形所有線段求交點(diǎn)，去除奇異情況后，統(tǒng)計(jì)交點(diǎn)個(gè)數(shù).如果測(cè)試點(diǎn)兩邊的左右兩邊交點(diǎn)個(gè)數(shù)都是奇數(shù)則該測(cè)試點(diǎn)在多邊形內(nèi)，否則在多邊形外，示意圖如圖2所示.

圖2 判斷點(diǎn)在多邊形內(nèi)部

2）判斷多邊形與多邊形關(guān)系

在構(gòu)建多邊形模型時(shí)，需要判斷多邊形之間關(guān)系.對(duì)于多邊形A和多邊形B，將A中所有圓弧線段頂點(diǎn)進(jìn)行是否在B中判斷，如果A中有部分點(diǎn)在B的內(nèi)部也有部分點(diǎn)在B的外部則認(rèn)為多邊形A和多邊形B相交.如果A所有的點(diǎn)均在B的內(nèi)部，則認(rèn)為B包含A.如果A的點(diǎn)均在B的外部則A與B相離.

3）多邊形模型

直線段、圓弧線段、緩和曲線段有序組合成一個(gè)閉合環(huán)；一個(gè)或多個(gè)不相交的環(huán)嵌套組成多邊形，這里將組成多邊形的環(huán)主要分為：外部環(huán)（沒(méi)有被任何多邊形包含）、內(nèi)部環(huán) （被奇數(shù)個(gè)多邊形包含）和島環(huán) （被偶數(shù)個(gè)多邊形包含）.構(gòu)建多邊形時(shí)，首先判斷多邊形之間是否相交，若相交，則不能構(gòu)成多邊形.算法中，采用層狀結(jié)構(gòu)存儲(chǔ)多邊形，較常規(guī)樹(shù)狀模型存儲(chǔ)多邊形而言不僅能夠降低運(yùn)算難度，而且能夠提高運(yùn)算效率.

如圖3所示的多邊形示意圖中，1為外部環(huán)，2、3、4 為內(nèi)部環(huán)，5、7 為島環(huán)，6 為內(nèi)部環(huán).按層存儲(chǔ)多邊形時(shí)，1 為第一層，2、3、4 為第二層，5、7 為第三層，6為第四層；按環(huán)類(lèi)型存儲(chǔ)時(shí)分為外部環(huán)集、內(nèi)部環(huán)集和島環(huán)集.

圖3 多邊形示意

2 附帶緩和曲線多邊形處理算法

多邊形的布爾運(yùn)算，即多邊形的交、并、差，是計(jì)算機(jī)幾何和計(jì)算機(jī)圖形學(xué)領(lǐng)域的基本問(wèn)題.布爾運(yùn)算在圖形處理過(guò)程常用于基本圖形組合以產(chǎn)生新的形體.多邊形的面積與周長(zhǎng)計(jì)算也是多邊形的處理必不可少的算法.本節(jié)重點(diǎn)介紹附帶緩和曲線多邊形布爾運(yùn)算、面積計(jì)算與周長(zhǎng)計(jì)算的算法思路.

2.1 數(shù)據(jù)預(yù)處理

在對(duì)多邊形處理前先對(duì)多邊形進(jìn)行預(yù)處理.如圖4所示，為一種典型的附帶緩和曲線多邊形，M1與M2均為嵌套多邊形，其中M2為附帶緩和曲線段多邊形，9號(hào)點(diǎn)為直緩點(diǎn)，10號(hào)點(diǎn)為緩圓點(diǎn)，23號(hào)點(diǎn)為圓緩點(diǎn)，11號(hào)點(diǎn)為緩直點(diǎn).M1的內(nèi)部與M2的內(nèi)部有相交部分.將M1中的外部環(huán)和島環(huán)按順時(shí)針存儲(chǔ)，內(nèi)部環(huán)按逆時(shí)針存儲(chǔ)；將M2中所有環(huán)層中的外部環(huán)和島環(huán)按逆時(shí)針存儲(chǔ)，內(nèi)部環(huán)按順時(shí)針存儲(chǔ).其中M1、M2均由一個(gè)外部環(huán)和一個(gè)內(nèi)部環(huán)構(gòu)成，M1的外部環(huán)結(jié)構(gòu)為：19-20-21-22-2-3-23-24-4-1-19，內(nèi)部環(huán)結(jié)構(gòu)為：9-25-5-26-12-7-6-9；M2的外部環(huán)結(jié)構(gòu)為：19-15-24-14-23-13-12-11-10-9-22-8-19，內(nèi)部環(huán)結(jié)構(gòu)為：20-16-21-25-17-26-18-20.

圖4 多邊形預(yù)處理

2.2 多邊形布爾計(jì)算

2.2.1 多邊形中的線處理

對(duì)兩個(gè)多邊形進(jìn)行布爾運(yùn)算時(shí)，需要判斷多邊形的線是否在另一多邊形內(nèi)部，并對(duì)線做標(biāo)記.類(lèi)比于多邊形環(huán)的分類(lèi)，將線分為外部環(huán)線L1、內(nèi)部環(huán)線L2和島環(huán)線L3.線標(biāo)記準(zhǔn)則如下：線默認(rèn)標(biāo)記為0；L1和L3在外部環(huán)或島環(huán)的內(nèi)部標(biāo)記1；L1和L3在內(nèi)部環(huán)的內(nèi)部標(biāo)記2；L2在外部環(huán)或島環(huán)的內(nèi)部標(biāo)記3；L2在內(nèi)部環(huán)的內(nèi)部標(biāo)記4.算法步驟：對(duì)于線L，按照環(huán)層順序（0-n）處理，對(duì)環(huán)層中每個(gè)環(huán)都進(jìn)行線L是否在內(nèi)部的判斷，若線在內(nèi)部，則根據(jù)標(biāo)記準(zhǔn)則對(duì)線進(jìn)行標(biāo)記，否則不做處理；對(duì)多邊形預(yù)處理后，分別對(duì)M1、M2的線進(jìn)行標(biāo)記處理，結(jié)果如圖5所示.

圖5 線在多邊形中標(biāo)記示意

2.2.2 多邊形差集運(yùn)算

多邊形線處理后，將M1中標(biāo)記為1、3的線和M2中標(biāo)記為0、2、4的線添加到線集合中，并對(duì)線集合進(jìn)行搜索，得到環(huán)集合，將環(huán)集合構(gòu)成多邊域進(jìn)行結(jié)果輸出.根據(jù)圖4的線標(biāo)記結(jié)果，結(jié)合差集的選線方法得出被保留的線.M1中外部環(huán)保留的線：19-20、21-22 和 23-24，內(nèi)部環(huán)保留的線：9-25和 26-12；M2中外部環(huán)保留的線：22-8、8-19、24-14、14-23、12-11、11-10 和 10-9，內(nèi)部環(huán)保留的線：20-16、16-21、25-17 和 17-26.將這些線組成集合，根據(jù)線集合搜尋環(huán)，最終得到三個(gè)環(huán)：①22-8-19-20-16-21-22；②24-14-23-24；③26-12-11-10-9-25-17-26.差集結(jié)果如圖6所示.

圖6 M2與M1差集結(jié)果示意

2.2.3 多邊形交集運(yùn)算

多邊形線處理后，對(duì)于M1中標(biāo)記為1、3的線進(jìn)行反向處理，添加到線集合.將M2中標(biāo)記為1、3的線添加到線集合中，對(duì)線集合進(jìn)行搜索得到環(huán)集合，將環(huán)集合構(gòu)成多邊域并進(jìn)行結(jié)果輸出，如圖7所示，結(jié)果環(huán)有：①19-15-24-23-13-12-26-18-20-19；②9-22-20-25-9.

圖7 多邊形交集計(jì)算示意

2.2.4 多邊形并集運(yùn)算

多邊形線處理后，將M1中標(biāo)記為0、2、4的線添加到線集合中，對(duì)于M2中標(biāo)記為0、2、4的線進(jìn)行反向處理，再添加到線集合，對(duì)線集合進(jìn)行搜索得到環(huán)集合，將環(huán)集合構(gòu)成多邊域并進(jìn)行結(jié)果輸出.從線集合中搜尋環(huán)，最終得到環(huán)：①22-8-19-1-4-24-14-23-3-2-22； ②12-11-10-9-6-7-12；③22-14-23-5-22；④20-16-21-20.將4個(gè)環(huán)組成多邊形返回結(jié)果，如圖8所示，結(jié)果多邊形中：①為外部環(huán)，②、③、④為內(nèi)部環(huán).

圖8 多邊形并集計(jì)算示意

2.3 多邊形周長(zhǎng)計(jì)算和面積計(jì)算

多邊形的周長(zhǎng)為外部環(huán)總周長(zhǎng)與島環(huán)總周長(zhǎng)的和減去內(nèi)部環(huán)的總周長(zhǎng).多邊形的面積為外部環(huán)總面積與島環(huán)總面積的和減去內(nèi)部環(huán)總面積.環(huán)的面積采用計(jì)算機(jī)幾何學(xué)中的矢量叉乘法計(jì)算[18].計(jì)算公式如公式（1）所示.

由于環(huán)P中可能含有圓弧線段、緩和曲線段，但公式（1）僅適用于由直線組成的按順時(shí)針或逆時(shí)針存儲(chǔ)的閉合圖形的面積.故在計(jì)算環(huán)P的面積時(shí)，需將環(huán)中的全部曲線由直線替代，構(gòu)成無(wú)曲線環(huán) P1，利用公式（1）計(jì)算 P1的面積 S1.同時(shí)判斷每條曲線是否在P1內(nèi)部，并求解由曲線和兩點(diǎn)連線組成的閉合圖形面積.對(duì)于圓弧段部分面積，根據(jù)計(jì)算機(jī)幾何學(xué)中求解弓形面積方法進(jìn)行計(jì)算；對(duì)于緩和曲線段部分面積，根據(jù)緩和曲線邊界的面積計(jì)算方法[22-23].計(jì)算.根據(jù)曲線是否在P1內(nèi)部，對(duì)面積S1進(jìn)行修改：若曲線在P1內(nèi)部，則減去曲線部分面積；若曲線在P1外部，需加上曲線部分面積.當(dāng)所有曲線面積處理完畢，求得面積S1為環(huán)面積.

3 實(shí)例應(yīng)用

實(shí)驗(yàn)采用C#語(yǔ)言結(jié)合AutoCAD二次開(kāi)發(fā)技術(shù)[23]開(kāi)發(fā)CAD插件，并在主頻為2.8 GHz的PC上進(jìn)行實(shí)驗(yàn).

3.1 運(yùn)行效率測(cè)試

實(shí)驗(yàn)采用20組隨機(jī)生成的附帶緩和曲線多邊形進(jìn)行布爾運(yùn)算同時(shí)統(tǒng)計(jì)運(yùn)行耗時(shí)，其中20組數(shù)據(jù)根據(jù)多邊形頂點(diǎn)數(shù)、緩和曲線線段數(shù)和嵌套層數(shù)分為5類(lèi).實(shí)驗(yàn)結(jié)果如表2～表4所示.

表2 差集運(yùn)算運(yùn)行效率實(shí)驗(yàn)

表3 交集運(yùn)算運(yùn)行效率實(shí)驗(yàn)

表4 并集運(yùn)算運(yùn)行效率實(shí)驗(yàn)

從理論上講，多邊形差集的處理過(guò)程比交集和并集的更簡(jiǎn)單，差集只需要將符合標(biāo)記規(guī)則的線提取組合成環(huán)，并集和交集算法則需要對(duì)符合標(biāo)記規(guī)則的線進(jìn)行反向處理.類(lèi)別1實(shí)驗(yàn)結(jié)果也反映了差集算法較交集和并集算法更高效.根據(jù)以上實(shí)驗(yàn)，隨著點(diǎn)數(shù)增多，緩和曲線段的增加以及嵌套層的增多算法的運(yùn)行效率降低.

3.2 工程實(shí)例

3.2.1 數(shù)據(jù)的來(lái)源與處理

附帶緩和曲線多邊形的構(gòu)建與處理算法在測(cè)量工作中的許多方面都有應(yīng)用，算法在江西吉安農(nóng)村道路規(guī)劃測(cè)量中得到了應(yīng)用.數(shù)據(jù)為吉安農(nóng)村道路規(guī)劃測(cè)量工程圖，在一段規(guī)劃路中，道路緩和曲線部分經(jīng)過(guò)一塊含有鄰村飛地(指隸屬于某一行政區(qū)管轄但不與本區(qū)毗連的土地)的土地.土地實(shí)際情況如圖9所示，A為該村土地，B為鄰村土地，規(guī)劃路經(jīng)過(guò)了A與B的區(qū)域.

圖9 道路規(guī)劃

3.2.2 結(jié)果分析

測(cè)量工作中，要求對(duì)規(guī)劃道路所占土地類(lèi)型，面積等進(jìn)行準(zhǔn)確高效的統(tǒng)計(jì).利用算法實(shí)現(xiàn)的CAD插件，選擇含緩和曲線部分多邊形和AB區(qū)域多邊形，通過(guò)附帶緩和曲線多邊形交集運(yùn)算，面積計(jì)算和周長(zhǎng)計(jì)算后結(jié)果如圖10所示.

圖10 交集結(jié)果

通過(guò)查詢多邊形屬性表明算法能正確構(gòu)建符合要求的多邊形.交集結(jié)果圖形符合邏輯和實(shí)際情況，查詢交點(diǎn)的坐標(biāo)與預(yù)期交點(diǎn)坐標(biāo)一致，表明算法能夠正確進(jìn)行多邊形的交集運(yùn)算.對(duì)多邊形交集結(jié)果的圖形進(jìn)行人工面積計(jì)算和周長(zhǎng)計(jì)算.算法計(jì)算面積為617.20 m2，周長(zhǎng)為145.74 m.與人工計(jì)算結(jié)果對(duì)比，面積誤差為0.30 m2，周長(zhǎng)誤差為0.026 m，誤差滿足測(cè)量要求.實(shí)驗(yàn)表明算法能正確計(jì)算附帶緩和曲線多邊形面積與周長(zhǎng).

4 結(jié) 論

針對(duì)附帶緩和曲線的多邊形構(gòu)建與處理，本算法根據(jù)直線段，圓弧段，緩和曲線段，多邊形的幾何特點(diǎn)進(jìn)行建模，實(shí)現(xiàn)了附帶緩和曲線多邊形的模型構(gòu)建，周長(zhǎng)，面積計(jì)算和布爾運(yùn)算.經(jīng)過(guò)大量實(shí)驗(yàn)表明，該算法能正確生成附帶緩和曲線多邊形，能準(zhǔn)確計(jì)算附帶緩和曲線多邊形的面積和周長(zhǎng)，能實(shí)現(xiàn)附帶緩和曲線多邊形的布爾運(yùn)算.該算法不僅能應(yīng)用于計(jì)算機(jī)地圖制圖、地理信息系統(tǒng)、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域，也可以為一些幾何圖形處理提供借鑒和啟發(fā).