一種無人機飛行區域拓撲關系判斷算法

劉金奎 羅銀輝

摘 要：無人機飛行區域電子圍欄規劃中的核心問題在于解決無人機所申請飛行區域與禁飛區的沖突，而無人機飛行區域的沖突歸根結底在于所申請飛行區域與禁飛區拓撲關系的判斷。為了能夠有效判斷飛行區域之間的拓撲關系，提出一種無人機飛行區域拓撲關系判斷方法：基于點集拓撲理論，利用九交模型（9IM）對無人機飛行區域拓撲關系進行重新劃分和描述；提出解決無人機電子圍欄飛行區域拓撲關系判斷的算法流程以及計算實現方法；最后，利用VC++設計飛行區域拓撲關系判斷實驗。結果表明，該方法能夠快速、有效判斷出相關拓撲關系。

關鍵詞：無人機；拓撲關系；九交模型；飛行區域沖突

DOI：10.11907/rjdk.172789

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）004-0054-04

Abstract：The core issue in UAV flight area electronic fence planning is to solve conflict between the UAV application area and the no-fly zone.While the conflict of the UAV flight area lies in the analysis of the topological relation between the applied flight area and the no-fly zone.In order to effectively determine the topological relationship between flight regions，the paper presents a method of determining topological relation of UAV flight area： Based on the theory of point set topology， the q intersection model （9IM） is used to re-divide and describe the topological relation of UAV flight area.The algorithm flow and the method of calculating the topology relation of the UAV electronic fence flight area are proposed.Finally， the validity of the method is verified by using VC ++ to design the flight area topological relation. The result shows that this method can quickly and effectively judge the topological relation.

Key Words：UAV； topological relations； 9IM； flight area conflict

0 引言

民用無人機發展帶來了民用無人機市場的繁榮，同時也由于管理的無序性使得“黑飛”問題頻頻出現[1]。無人機實名制以及無人機飛行計劃申請是根除“黑飛”問題的重要手段。隨著電子圍欄技術的發展與成熟，其在無人機飛行區域規劃中的應用能夠有效解決無人機離地飛行計劃申請。而無人機飛行區域電子圍欄規劃中最主要的難點在于解決無人機飛行區域電子圍欄申請過程中出現的申請區域電子圍欄沖突問題。由于無人機的飛行高度有嚴格限制，所以其電子圍欄區域為特殊的三維區域，即底面為多邊形柱體。申請區域電子圍欄沖突問題研究實際可以轉化為無人機飛行區域的空間拓撲關系判斷問題研究。此外，由于無人機的飛行區域存在安全余度考量，因此本文研究的無人機飛行區域拓撲關系與九交模型（9IM）描述的拓撲關系不同，需要對無人機飛行區域拓撲關系描述進行研究。

對于拓撲關系的描述，目前最主要的有基于邏輯的公理化拓撲理論和傳統數學拓撲兩種方法，其中應用最多的是RCC（區域連接演算）形式化模型和4/9交模型。此外，還有很多學者提出的改進方法。例如，趙仁量等[2]利用空間實體的Voronoi區域替代空間實體外部，改進了9交模型，提出了基于Voronoi圖的新9交模型（V9I）。在拓撲關系計算方面：陳軍等[3]提出線目標間復雜拓撲關系的分解-組合計算思路，計算線目標之間的拓撲關系；鄧念東等[4]采用GTP作為描述空間目標的體元，通過描述體元之間的關系，進而表達空間目標之間的拓撲關系；趙紅超[5]以擴展的BMN交點算法為支撐，利用模板元編程的特性，設計并實現了點、線、面之間的拓撲關系的判斷；倪建華[6]針對空間拓撲關系類型區分不夠詳細和算法描述薄弱等問題，對點、線、面目標之間拓撲關系的描述和計算進行了研究；ArcGIS在組件ArcObjects的 IRelationalOperator接口中實現了7種拓撲關系，分別為相等、包含、被包含、相離、重疊、相接和相交[7]；Oracle公司提供了Oracle Spatial插件，并在Oracle中提供SDO_RELATE等函數查詢目標間的拓撲關系。Oracle描述的拓撲關系類型分別為相離、相接、重疊-邊界相交、重疊-邊界相離、相等、包含、被包含、覆蓋、位于和任意相交。

綜上所述，九交模型（9IM）廣泛應用于拓撲關系的描述，能夠區分較多的拓撲關系。對于無人機飛行區域而言，傳統9IM所描述的某些拓撲關系類型并不需要確定區分。為了能夠更加快速、簡潔地判斷申請的無人機飛行區域與禁飛區是否存在沖突，本文對無人機飛行區域間拓撲關系進行重新描述并對拓撲關系計算算法進行研究。

1 無人機飛行區域拓撲關系描述

空間關系主要包括拓撲關系、順序關系和度量關系。其中，拓撲關系是最為基礎和重要的空間關系。其計算建立在對空間目標拓撲關系合理的描述上，適合空間目標實際情況的拓撲關系描述能夠大大提高拓撲關系計算效率。本文研究對象是無人機飛行區域，在現實中不需要對9IM中所描述的鄰接、相等、覆蓋和反覆蓋進行準確區分，因為在計算兩個區域邊界存在相切時有很多情況需要考慮，這會大大增加計算量。只需要判斷兩個區域的邊界是否存在交集，只要交集不為空就可以把兩個區域的拓撲關系認定為交疊。根據對九交模型（9IM）所描述的二維空間對象拓撲關系的分析以及無人機飛行區域拓撲關系的特殊性，對無人機飛行區域拓撲關系進行重新歸納和描述。無人機飛行區域拓撲關系可以歸納為以下4種：第一，相離，即區域a的所有邊界點都在區域b之外，同時區域b的所有邊界點都在區域a之外；第二，包含，即區域a的所有邊界點全在區域b的內部；第三，反包含，即區域b所有的邊界點全在區域a的內部；第四，交疊，即區域a與區域b的邊界存在交點（邊界交集不為空）。

如果空間目標a和b的內部、邊界和外部分別用a°、a、a-和b°、b、b-表示，則9IM的表現形式如式（1）所示[8]。交集之間可能的取值為{*，1，0}，其中，“*”表示不關心交集的值；“0”表示交集為空；“1”表示交集不為空。

根據無人機飛行區域的特殊性，將無人機飛行區域的拓撲關系歸納描述為4種拓撲關系：{Disjoint，Contains，Contained-by，Cross}。圖1給出了無人機飛行區域的4種拓撲關系，并給出了相應的9IM矩陣表現形式。

2 無人機飛行區域拓撲關系計算

2.1 無人機飛行區域拓撲關系判斷流程

在上述判斷流程中涉及到折線與面位置關系的判斷、直線與面位置關系的判斷、點是否在面內的判斷、點是否在線上的判斷和兩條直線是否相交的判斷。以下分別對所涉及的判斷算法進行分析。

折線與面位置關系的判斷：折線與面位置關系可以劃分為折線與面相交、折線與面相離和折線在面內部3種關系[9]。在進行位置關系判斷時，如果折線中每一條直線都在面的內部，則折線在面的內部；如果折線中有任一條直線與面相交，則折線與面相交；如果折線中所有直線都在面的外部，則折線與面相離。

直線與面位置關系的判斷：直線與面位置關系可以劃分為直線與面相交、直線與面相離和直線在面內部3種關系[10]。在進行位置關系判斷時，如果直線的兩個端點都在面的內部，則直線在面內部；如果直線的兩個端點分別在面的不同部分，則直線與面相交；如果直線的兩個端點都在面外部，且直線與面邊界的任一直線段都不相交，則直線與面相離。

點是否在面內的判斷：采用傳統的射線法進行計算，通過穿過該點射線與面交點的個數判斷[11]。若交點個數為奇數，則點在面內；若交點個數為偶數，則點在面外部。

點是否在線上的判斷：首先分別計算直線的長度和點到直線兩個端點的長度，用點到直線兩個端點長度的和減去直線的長度，得到的值取絕對值除以直線的長度，然后將值與α對比，如果小于α，則點在直線上；否則點不在線上。

2.2 無人機飛行區域拓撲關系計算實現方法

根據上述算法思想及流程，以VC++語言作為工具實現其具體計算，在實現過程中定義以下函數：polygonAndPolygon（）判斷面與面關系；polyLineAndPolygon（）判斷折線與面關系；LineAndPolygon（）判斷直線與面關系；isPointInPolygon（）判斷點是否在面內；isLineIntersect（）判斷兩條直線是否相交；isPointInLine（）函數判斷點是否在線上。在算法實現過程中各個函數的調用關系見圖2。

3 實驗驗證

在實驗中（電腦配置：英特爾酷睿3處理器3.50GHZ，4.00GB內存，500GB硬盤，win7 64位操作系統），以Visual Studio 2013作為開發平臺，以VC++為可視化工具，設計一個拓撲關系判斷驗證系統，包括飛行區域的輸入、飛行區域的交互（縮放、平移、刪除）、飛行區域的選取以及飛行區域拓撲關系的計算等功能。在驗證過程中，由于要驗證區域是驗證者輸入的，特別是對于區域邊界間存在相互重合的情況可能會很難輸入準確，因此輸入區域的誤差可能會造成判斷結果與實際輸入位置關系存在不一致的情況。以下是分別對所描述飛行區域拓撲關系判斷的驗證：

圖3選取一組相離區域進行驗證，可以看出其位置關系與判斷結果相一致，即區與區拓撲關系為相離。

圖4、圖5和圖6分別選取3種不同的相交位置關系進行拓撲關系驗證，其驗證結果與預期算法結果相一致，即區與區拓撲關系為相交。

圖7中選取灰色區域包含于黑色區域進行驗證，其實際位置關系與判斷結果相一致，即區與區拓撲關系為包含。

圖8中選取灰色區域包含黑色區域進行驗證，其實際位置關系與判斷結果相一致，即區與區拓撲關系為反包含。

4 結語

對于無人機飛行區域而言，不需要對飛行區域邊界存在切點的問題進行明確區分，能夠更加簡化對無人機飛行區域拓撲關系的描述，從而減少算法計算量。因此，本文采用9IM對無人機飛行區域拓撲關系進行重歸新納和描述，詳細介紹了拓撲關系判斷中的算法流程以及具體實現方法，并通過實驗驗證了算法的可行性。飛行區域拓撲關系的判斷能夠有效解決飛行區域沖突問題，進而在無人機飛行區域電子圍欄規劃中能得到有效應用。

參考文獻：

[1] 柯玉寶，車彥卓.如何規范管理無人機[J].機器人產業，2016，1：16-21.

[2] 趙仁量.基于Voronoi圖的空間關系計算研究[D].長沙：中南大學，2002.

[3] 陳軍，劉萬增，李志林，等.線目標拓撲關系的細化計算方法[J].測繪學報，2006，35（8）：255-230.

[4] 鄧念東，候恩科.基于GTP單純刨分的地下實體拓撲關系形式化描述方法[J].煤炭學報，2008，33（5）：527-531.

[5] 趙紅超.空間關系的研究和實現[D].北京：中國科學院，2006.

[6] 倪建華.拓撲關系計算方法研究與實現[D].長沙：中南大學，2009.

[7] 高峰.技術引領未來——無人機云系統全面解析[J].計算機與網絡，2016，7：13-14.

[8] 鄧敏，李成名，劉文寶.利用拓撲和度量相結合的方法描述面目標間的空間關系[J].測繪學報，2002，31（2）：2-3.

[9] 齊東洲，吳敏.高效的多邊形布爾計算方法[J].計算機應用，2014，34（S2）：78-82.

[10] 李永紅，華一新.一種快速判斷線段相交的方法[J].測繪通報，2003，30（7）：1-2.

[11] 王潤科，張彥麗.判斷點與多邊形位置關系的算法綜述[J].甘肅聯合大學學報，2006，20（6）：2-4.

（責任編輯：何 麗）