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

（江西理工大學建筑與測繪工程學院，江西 贛州341000）

0 引 言

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

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

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

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

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

圖1 附帶緩和曲線多邊形

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

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

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

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

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

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

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

2）緩和曲線段的交點計算

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

表1 緩和曲線的屬性

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

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

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

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

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

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

3）多邊形模型

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

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

圖3 多邊形示意

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

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

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

在對多邊形處理前先對多邊形進行預處理.如圖4所示，為一種典型的附帶緩和曲線多邊形，M1與M2均為嵌套多邊形，其中M2為附帶緩和曲線段多邊形，9號點為直緩點，10號點為緩圓點，23號點為圓緩點，11號點為緩直點.M1的內(nèi)部與M2的內(nèi)部有相交部分.將M1中的外部環(huán)和島環(huán)按順時針存儲，內(nèi)部環(huán)按逆時針存儲；將M2中所有環(huán)層中的外部環(huán)和島環(huán)按逆時針存儲，內(nèi)部環(huán)按順時針存儲.其中M1、M2均由一個外部環(huán)和一個內(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 多邊形預處理

2.2 多邊形布爾計算

2.2.1 多邊形中的線處理

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

圖5 線在多邊形中標記示意

2.2.2 多邊形差集運算

多邊形線處理后，將M1中標記為1、3的線和M2中標記為0、2、4的線添加到線集合中，并對線集合進行搜索，得到環(huán)集合，將環(huán)集合構(gòu)成多邊域進行結(jié)果輸出.根據(jù)圖4的線標記結(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)，最終得到三個環(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 多邊形交集運算

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

圖7 多邊形交集計算示意

2.2.4 多邊形并集運算

多邊形線處理后，將M1中標記為0、2、4的線添加到線集合中，對于M2中標記為0、2、4的線進行反向處理，再添加到線集合，對線集合進行搜索得到環(huán)集合，將環(huán)集合構(gòu)成多邊域并進行結(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個環(huán)組成多邊形返回結(jié)果，如圖8所示，結(jié)果多邊形中：①為外部環(huán)，②、③、④為內(nèi)部環(huán).

圖8 多邊形并集計算示意

2.3 多邊形周長計算和面積計算

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

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

3 實例應用

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

3.1 運行效率測試

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

表2 差集運算運行效率實驗

表3 交集運算運行效率實驗

表4 并集運算運行效率實驗

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

3.2 工程實例

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

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

圖9 道路規(guī)劃

3.2.2 結(jié)果分析

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

圖10 交集結(jié)果

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

4 結(jié) 論

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