楊靜靜 馬駿

摘 ?要： 為了有效地解決遙感應(yīng)用中感興趣區(qū)域內(nèi)有效遙感影像面積統(tǒng)計效率的問題，提出一種基于MPI（Message Passing Interface）的并行計算環(huán)境，采用經(jīng)典數(shù)學(xué)定理鞋帶公式（Shoelace Formula）及計算機(jī)圖形學(xué)中向量積法計算多邊形面積。使用三角分割法對多邊形進(jìn)行切割并行，判斷多邊形之間拓?fù)潢P(guān)系，獲取交集頂點(diǎn)表，使用鞋帶公式并行計算交多邊形面積。以1.96407的加速比有效提高遙感影像有效面積統(tǒng)計效率，加快網(wǎng)頁加載速度，提高用戶體驗(yàn)度。

關(guān)鍵詞： 遙感影像; 交多邊形面積; MPI; 并行計算; 鞋帶公式; 向量積

中圖分類號：TP312 ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A ? ? 文章編號：1006-8228（2020）06-08-05

Abstract： In order to effectively solve the problem of statistical efficiency of effective remote sensing image area in the region of interest in remote sensing applications， this paper proposes a parallel computing environment based on MPI （Message Passing Interface）， which uses the classic mathematical theorem Shoelace Formula and Cross Product Algorithm in computer graphics to calculate the polygon area. Triangular segmentation is used to cut the polygons in parallel， determine the topological relationship between the polygons， obtain the intersection vertex data， and Shoelace Formula is used to calculate the area of the intersection polygons in parallel. With an acceleration ratio of 1.96407， it effectively improves the statistical efficiency of the effective area of remote sensing images， speeds up the loading of web pages， and improves user experience.

Key words： remote sensing image; intersection polygon area; MPI; parallel computing; Shoelace Formula; Cross Product

0 引言

隨著衛(wèi)星遙感技術(shù)的迅速發(fā)展，采集的衛(wèi)星遙感影像爆炸式冪指數(shù)增加。面對巨量的遙感影像，滿足大范圍檢索條件要求的數(shù)據(jù)趨于上萬條，對判斷遙感影像間拓?fù)潢P(guān)系及計算遙感影像交并面積的計算效率提出挑戰(zhàn)。

每一個遙感影像都有專屬的坐標(biāo)位置屬性信息，故將計算多個遙感影像交并面積問題轉(zhuǎn)換為計算多個簡單多邊形交并面積問題。計算多邊形交并面積，首先需要獲取多邊形交并集頂點(diǎn)。判斷任意多邊形間拓?fù)潢P(guān)系不僅是計算幾何與計算機(jī)圖形學(xué)中的基本問題，也是GIS疊加分析的理論基礎(chǔ)。因此，對這一問題的研究無論是在理論上，還是在實(shí)踐上都有重要意義[4]。國內(nèi)外針對多邊形交并判斷及交并面積計算問題，分別提出各類針對不同應(yīng)用環(huán)境的多個多邊形拓?fù)潢P(guān)系判斷算法。如Shamos算法[5]、O' Rourke算法[6]用于處理凸多邊形，Weiler-Atherton算法[7]、Vatti算法[8]、Greiner-Hormann算法[9]、Sutherland-Hodgman算法[10]和M.Rivero提出的算法[11]能處理任意簡單多邊形的情況。針對這些經(jīng)典算法在不同生活領(lǐng)域的應(yīng)用，分別存在不同角度及不同層面的不足。對此，許多相關(guān)領(lǐng)域?qū)＜曳謩e提出的不同的改進(jìn)方法。

齊東洲等提出優(yōu)化數(shù)據(jù)結(jié)構(gòu)提高算法執(zhí)行效率的計算交點(diǎn)、將交點(diǎn)插入多邊形頂點(diǎn)序列、遍歷三個步驟的高效多邊形布爾計算方法[12]。陳濤提出了適用于凹多邊形裁剪的Cyrus-Beck改進(jìn)算法[13]。劉勇奎等[14]、侯寶明等[15]和魏許青[16]等分別在Weiler算法的基礎(chǔ)上改進(jìn)算法;劉勇奎等提出的算法采用單鏈表數(shù)據(jù)結(jié)構(gòu)，減少了計算交點(diǎn)的時間;魏許青利用算法中的多邊形鏈表求出交/并集頂點(diǎn)表，求出交/并多邊形面積;侯寶明等采用接縫技術(shù)的算法大大簡化了運(yùn)算過程。王結(jié)臣等提出基于掃描線和梯形分割思想的復(fù)雜多邊形裁剪算法[17];彭杰等提出基于交點(diǎn)排序思想的多邊形裁剪算法[18]等。結(jié)合以上多邊形裁切算法計算多邊形交/并面積的研究已經(jīng)逐漸擴(kuò)展。陳占龍等實(shí)現(xiàn)多核環(huán)境下基于Hilbert曲線空間劃分的多邊形并行合并[19];范俊甫等基于OGC簡單要素模型和Vatti算法，在集群MPI環(huán)境下對圖層級多邊形疊加合并[20];趙斯思等實(shí)現(xiàn)基于GPU加速的多邊形裁剪[21];高藝等提出基于GPU的柵格化多邊形相交面積算法GPURAS，并結(jié)合蒙特卡洛方法和遮擋查詢技術(shù)算法優(yōu)勢互補(bǔ)，提高計算效率[22]。上述研究學(xué)者主要在改進(jìn)經(jīng)典算法、經(jīng)典算法結(jié)合優(yōu)勢互補(bǔ)方向深入研究，而在基于計算幾何中數(shù)學(xué)定理的MPI并行環(huán)境下計算多邊形交/并面積的研究較少。

本文提出了一種基于MPI并行計算環(huán)境，鞋帶公式及向量積法計算多邊形面積。用三角分割法對多邊形進(jìn)行切割并行，判斷多邊形之間拓?fù)潢P(guān)系，獲取交集頂點(diǎn)表，使用鞋帶公式并行計算交多邊形面積的并行算法研究。本文算法在實(shí)際應(yīng)用中有效提高數(shù)據(jù)執(zhí)行效率，縮短程序執(zhí)行時間，提高用戶體驗(yàn)度。在遙感影像有效區(qū)域面積統(tǒng)計研究方面具有一定的參考價值。

1 多邊形交集面積計算算法

1.1 多邊形相交判斷及交點(diǎn)坐標(biāo)獲取

為了計算方便借坐標(biāo)原點(diǎn)為輔助點(diǎn)，視多邊形A為實(shí)體多邊形，則多邊形B為切割多邊形（首先要判斷多邊形A、B點(diǎn)排列方向順時針輸入，保證多邊形面積為正）。坐標(biāo)原點(diǎn)與多邊形任意相鄰的兩個頂點(diǎn)構(gòu)成一個三角形（如圖1多邊形三角分割），而三角形的面積可由三個頂點(diǎn)構(gòu)成的兩個平面向量的外積求得。多邊形面積的計算和原點(diǎn)的選取沒有關(guān)系，通常選取原點(diǎn)坐標(biāo)點(diǎn)o（0，0）或者多邊形的第一個點(diǎn)，這里選取原點(diǎn)坐標(biāo)點(diǎn)。以切割多邊形B任意兩點(diǎn)與原點(diǎn)o（0，0）組成的三角形ocd，每條邊為直線向量切割實(shí)體多邊形A任意兩點(diǎn)與原點(diǎn)組成的三角形oab，用向量積法判斷多邊形A、B每條邊之間拓?fù)潢P(guān)系，獲取交點(diǎn)坐標(biāo)集。向量積求三角形面積如圖2所示。

1.2 多邊形面積計算

1.2.1 鞋帶公式

鞋帶公式[1-3]，又稱“鞋帶算法”（Shoelace Formula，也稱為高斯面積公式），是一種數(shù)學(xué)算法，其用于計算簡單多邊形的面積，這些多邊形的頂點(diǎn)由平面中的笛卡爾坐標(biāo)表示。對這些坐標(biāo)進(jìn)行叉乘計算，找到包圍多邊形的區(qū)域，并從周圍的多邊形中找到其中的多邊形區(qū)域。根據(jù)其交叉乘的過程像系鞋帶一樣，故稱為鞋帶公式。

1.2.2 多邊形面積計算

本文用鞋帶公式計算多邊形面積。 依據(jù)1.1節(jié)中獲取的交點(diǎn)坐標(biāo)Pi，循環(huán)遍歷鞋帶算法計算兩三角形有向交面積之和Sum。

傳統(tǒng)經(jīng)典算法通過循環(huán)遍歷切割多邊形，向量積法多次循環(huán)判斷切割三角形兩兩之間拓?fù)潢P(guān)系判斷及獲取多邊形交點(diǎn)坐標(biāo)，調(diào)用鞋帶算法計算交多邊形面積，即計算三角形之間有向交面積并統(tǒng)計所有切割三角形交面積之和作為多邊形有效交面積。傳統(tǒng)多邊形交面積計算程序數(shù)據(jù)計算串行執(zhí)行耗時較長，在遇到多邊形頂多較多的情況時會降低算法的執(zhí)行效率，影響算法應(yīng)用效果。

2 基于MPI并行計算交多邊形面積

本文針對上述算法存在的缺陷，提出基于MPI信息傳遞接口并行環(huán)境計算多邊形面積，對數(shù)據(jù)分塊進(jìn)行多線程并行計算，減少數(shù)據(jù)計算執(zhí)行等待時間，提高算法的執(zhí)行效率。

2.1 MPI消息傳遞接口

消息傳遞接口（Message Passing Interface，簡稱MPI），是一種跨語言的通訊協(xié)議，用于編寫并行計算機(jī)，支持點(diǎn)對點(diǎn)和廣播通信[24]。目前用于編寫并行計算機(jī)較為流行。MPI是一個并行計算消息傳遞接口標(biāo)準(zhǔn)，由MPI論壇（MPI Forum）推出，制定該標(biāo)準(zhǔn)的目的是提高并行程序的可移植性和開發(fā)效率[25]。MPI現(xiàn)在已經(jīng)成為產(chǎn)業(yè)界廣泛支持的并行計算標(biāo)準(zhǔn)[26]。MPI主要消息傳遞接口如下。

⑴ Mpi_Init（）; 初始化MPI環(huán)境，建立多個MPI進(jìn)程之間的聯(lián)系，為后續(xù)通信做準(zhǔn)備。

⑵ Mpi_Finalize（）; 退出MPI環(huán)境。

⑶ Mpi_Comm_rank（MPI_COMM_WORLD，&rank）;獲取當(dāng)前進(jìn)程在指定通信域中的編號，返回整型的錯誤值，將自身與其他程序區(qū)分。MPI_COMM_WORLD類型的通信域，標(biāo)識參與計算的MPI進(jìn)程組;&rank返回調(diào)用進(jìn)程中的標(biāo)識號。

⑷ Mpi_Comm_size（MPI_COMM_WORLD，&size）;獲取指定通信域的進(jìn)程個數(shù)，確定自身完成任務(wù)比例。

⑸ MPI_Bcast（&n1，1，MPI_INT，0， MPI_COMM_WORLD）;廣播數(shù)據(jù)集。

⑹ MPI_Reduce（&myResult，&result，1，MPI_DOUBLE， MPI_SUM，0，MPI_COMM_WORLD）; 數(shù)據(jù)歸約，由進(jìn)程0進(jìn)行歸約，把每個進(jìn)程計算出來的myResult進(jìn)行相加（MPI_SUM），賦給result。

⑺ Mpi_send（buf，counter，datatype，dest，tag，comm）：buf發(fā)送緩沖區(qū)的起始地址，可以是數(shù)組或結(jié)構(gòu)指針;count：非負(fù)整數(shù)，發(fā)送的數(shù)據(jù)個數(shù);datatype：發(fā)送數(shù)據(jù)的數(shù)據(jù)類型;dest：整型，目的的進(jìn)程號;tag：整型，消息標(biāo)志;comm：MPI進(jìn)程組所在的通信域。

⑻ Mpi_recv（buf，count，datatype，source，tag，comm，status）：source：整型，接收數(shù)據(jù)的來源，即發(fā)送數(shù)據(jù)進(jìn)程的進(jìn)程號; status：MPI_Status結(jié)構(gòu)指針，返回狀態(tài)信息。

2.2 基于MPI并行計算多邊形面積

據(jù)算法使用背景本文使用組通信并行編程模型，利用消息傳遞方法實(shí)現(xiàn)任務(wù)間的并行。通過指定通信因子和組來對進(jìn)程進(jìn)行一種邏輯上劃分，通訊因子定義了進(jìn)程組內(nèi)或組間通訊的上下文。Foster方法下并行化設(shè)計步驟。

⑴ 劃分：數(shù)據(jù)分發(fā)，0號進(jìn)程讀入整個坐標(biāo)數(shù)據(jù)向量，將獲取的數(shù)據(jù)分為comm_size塊（comm_size個核），并將數(shù)據(jù)發(fā)送給需要分量的其他進(jìn)程。不同進(jìn)程對收到的數(shù)據(jù)塊進(jìn)行計算順序相鄰的兩個頂點(diǎn)與原點(diǎn)組成的三角形面積。

⑵ 通信：各線程內(nèi)坐標(biāo)數(shù)據(jù)塊的臨界坐標(biāo)需要相互間通信，并發(fā)地執(zhí)行對數(shù)據(jù)的相交判斷及面積計算，期間多機(jī)有相互間的網(wǎng)絡(luò)通信開銷。

⑶ 聚集：多任務(wù)運(yùn)行時，0號進(jìn)程收集向量的所有分量，然后由0號進(jìn)程聚集降低原始任務(wù)之間本需要的相互通信開銷。

⑷ 映射：聚合過的任務(wù)主要通過for循環(huán)部分通過調(diào)度對任務(wù)進(jìn)行并行化計算，循環(huán)中的迭代需要按照迭代次數(shù)及核數(shù)進(jìn)行輪播分配。

如圖3組通信任務(wù)分配所示。源數(shù)據(jù)指定特定通信組，通信組內(nèi)由多個處理機(jī)組成，通信組內(nèi)通過MPI_Bcast廣播數(shù)據(jù)組，根據(jù)組內(nèi)處理機(jī)數(shù)量對源數(shù)據(jù)進(jìn)行任務(wù)分塊，組內(nèi)處理機(jī)之間通過網(wǎng)絡(luò)傳送消息實(shí)現(xiàn)相互通信，實(shí)現(xiàn)任務(wù)間并行。MPI_Reduce規(guī)約各個進(jìn)程任務(wù)塊計算結(jié)果。

本文主要用到上一節(jié)中前6個消息傳遞接口。

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

在Windows7 64位系統(tǒng)環(huán)境，8G運(yùn)行內(nèi)存，同樣機(jī)型4臺，一臺作為主進(jìn)程（0號進(jìn)程，負(fù)責(zé)數(shù)據(jù)讀入、分發(fā)、聚合），其他3臺機(jī)作為并行節(jié)點(diǎn)。

實(shí)驗(yàn)主要采用梯度驗(yàn)證法設(shè)置一些測試梯度，以提高測試準(zhǔn)確性。通常采用加速比S和效率E來測量并行計算效率，如等式⑸和等式⑹。

其中，Ts為串行算法執(zhí)行耗費(fèi)時間，Tp為并行算法執(zhí)行耗費(fèi)時間，P為算法并行節(jié)點(diǎn)數(shù)。

為了更加準(zhǔn)確的驗(yàn)證實(shí)驗(yàn)結(jié)論，本文分兩種情況進(jìn)行實(shí)驗(yàn)驗(yàn)證，一是節(jié)點(diǎn)數(shù)一定改變多邊形頂點(diǎn)數(shù);二是多邊形頂點(diǎn)數(shù)一定改變節(jié)點(diǎn)數(shù)。首先我們驗(yàn)證節(jié)點(diǎn)數(shù)一定為2，多邊形頂點(diǎn)數(shù)分別為3，10，20，40，實(shí)驗(yàn)結(jié)果如表1節(jié)點(diǎn)數(shù)一定改變多邊形頂點(diǎn)個數(shù)和圖4節(jié)點(diǎn)數(shù)一定改變多邊形頂點(diǎn)個數(shù)所示。

當(dāng)并行節(jié)點(diǎn)數(shù)一定時，改變串行、并行頂點(diǎn)數(shù)量，發(fā)現(xiàn)隨著頂點(diǎn)數(shù)的增加計算時間增大，當(dāng)數(shù)據(jù)過小時CPU消費(fèi)的時間會影響并行計算效率，并行效果不明顯，在頂點(diǎn)數(shù)一定時串行和并行計算時加速比和效率是呈線性增加趨勢。

再次驗(yàn)證頂點(diǎn)數(shù)一定為20，節(jié)點(diǎn)數(shù)分別為1，2，3，4，實(shí)驗(yàn)結(jié)果如表2多邊形頂點(diǎn)個數(shù)一定改變節(jié)點(diǎn)數(shù)和圖5多邊形頂點(diǎn)個數(shù)一定改變節(jié)點(diǎn)數(shù)所示。

當(dāng)頂點(diǎn)數(shù)一定時，改變并行節(jié)點(diǎn)數(shù)量，發(fā)現(xiàn)隨著節(jié)點(diǎn)數(shù)的增加，計算時間增大，當(dāng)數(shù)據(jù)過小時，CPU消費(fèi)的時間會影響并行計算效率。節(jié)點(diǎn)數(shù)繼續(xù)增加，加速比增長緩慢且有下降趨勢，因?yàn)榫€程啟動需要開銷一定的時間。故隨著節(jié)點(diǎn)數(shù)的增加，并行程序的效率越來越低。

綜上所述，本研究中當(dāng)節(jié)點(diǎn)數(shù)為2時，并行計算效率最高，達(dá)到相對最佳并行計算節(jié)點(diǎn)。

4 結(jié)論

本研究主要為了解決多邊形頂點(diǎn)足夠多時，多邊形分割及三角形向量面積計算需要通過多層循環(huán)遍歷，程序串行執(zhí)行效率低下問題。本文提出基于MPI并行計算多邊形交面積，提高多邊形面積計算效率。在多邊形頂點(diǎn)增多時，本文并行計算多邊形面積效率明顯比串行計算速度快，相比串行方法本文并行計算方法在提高計算效率方面具有一定的研究價值。但是本文實(shí)驗(yàn)利用消息傳遞方法實(shí)現(xiàn)多處理機(jī)處理任務(wù)并行，該方法需要網(wǎng)絡(luò)環(huán)境才能實(shí)現(xiàn)多處理機(jī)的并行，本次實(shí)驗(yàn)僅在一種網(wǎng)絡(luò)環(huán)境下進(jìn)行實(shí)驗(yàn)，接下來可以嘗試換一種網(wǎng)絡(luò)帶寬進(jìn)行并行測試，來驗(yàn)證并行實(shí)驗(yàn)的有效性。

參考文獻(xiàn)（References）：

[1] Dahlke， Karl. "Shoelace Formula" （http：//www.mathrefer-ence.com/la-det，shoe.html）. Retrieved 9 June 2008.

[2] Shoelace Theorem （http：//www.artofproblemsolving.com/wiki/index.php？title=Shoelace_Theorem）， Art of Problem Solving Wiki.

[3] Younhee Lee， ?Woong Lim. Shoelace Formula： Connect-ing the Area of a Polygon with Vector Cross Product[J]. The Mathematics Teacher，2017.110（8）：631-636

[4] 朱雅音，王化文，萬豐等. 確定兩個任意簡單多邊形交_并_差的算法[J]. 計算機(jī)研究與發(fā)展， 2003.4：69-76

[5] Preparata. Computational Geometry： An Introduction[J].?texts & monographs in computer science，1986.47（176）.

[6] O' Rourke. Computational Geometry in C[J]. Cambridge：Cam-bridge University Press，1985.37：128-129

[7] Kevin Weiler ， Peter Atherton. Hidden surface removal?using polygon area sorting[C]. Proceedings of the 4th Annual Conference on Computer Graphic and Interactive Techniques，1977.11：214-222

[8] Bala R. Vatti. ?A generic solution to polygon clipping[J].?Communication of the ACM，1992.35：56-63

[9] Hoffmann CM ， The problems of accuracy and robustness?in geometric computations[J]. IEEE Computer，1989.22：31-42

[10] 蘇誠，韓俊剛.Sutherland-Hodgman裁剪算法的改進(jìn)[J].西安郵電學(xué)院學(xué)報，2013.18（3）：80-82

[11] Rivero， F R Feito. Boolean operations on general planarpolygons[M].Computers& Graphics，2000.24（6）：881-898

[12] 齊東洲，吳敏.高效的多邊形布爾計算方法[J].計算機(jī)應(yīng)用，2014.S2：85-89

[13] 陳濤.適用于凹多邊形的Cyrus-Beck改進(jìn)算法[J].計算機(jī)科學(xué)，2006.33（12）：217-220

[14] 劉永奎，高云，黃有群.一個有效的多邊形裁剪算法[J].軟件學(xué)報，2003.14（4）：845-856

[15] 侯寶明，劉雪娜.任意多邊形區(qū)域交的有效算法[J]，計算機(jī)輔助工程，2009.18（2）：73-76

[16] 魏許青.計算多邊形交集_并集面積的算法[J].計算機(jī)工程與科學(xué)，2007.12：89-90

[17] 王結(jié)臣，沈定濤，陳焱明，等.一種有效的復(fù)雜多邊形裁剪算法[J].武漢大學(xué)學(xué)報（信息科學(xué)版），2010.35（3）：369-372

[18] 彭杰，劉南，唐遠(yuǎn)彬等.一種基于交點(diǎn)排序的高效多邊形裁剪算法[J].浙江大學(xué)學(xué)報（理學(xué)版），2012.39（1）：107-111

[19] 陳占龍，吳亮，劉煥煥.多核環(huán)境下Hilbert曲線劃分簡單要素多邊形合并算法[J].計算機(jī)應(yīng)用研究，2012.29（7）：2747-2750

[20] 范俊甫，馬廷，周成虎等.基于集群MPI的圖層級多邊形并行合并算法[J].地球信息科學(xué)學(xué)報，2014.16（4）： 15-21

[21] 趙斯思，周成虎.GPU加速的多邊形疊加分析[J]. 地理科學(xué)進(jìn)展，2013.32（1）：114-120

[22] 高藝，羅健欣，裘杭萍等.基于GPU的任意多邊形相交面積計算方法_高藝[J].測繪工程，2017.26（12）：58-62

[23] Meister， A. L. F.， Generalia de genesi figurarum planarumt inde pendentibus earum affectionibus， https：//books.google.com/books？id=fOE_AAAAcAAJ，1769，Nov.Com. G?tt. （in Latin）， 1：144

[24] https：//baike.baidu.com/item/MPI/15277241？fr=aladdin

[25] 李久楷，朱俊，寧交賢.MPI并行計算性能的研究[J].四川大學(xué)學(xué)報（自然科學(xué)版），2009.33（5）：496-499

[26] 申煥，石曉春，邱宏華.基于MPI的海量遙感影像并行處理技術(shù)探析[J].全球定位系統(tǒng)，2012.37（6）：73-76