劉金奎 羅銀輝

摘 要：無(wú)人機(jī)飛行區(qū)域電子圍欄規(guī)劃中的核心問(wèn)題在于解決無(wú)人機(jī)所申請(qǐng)飛行區(qū)域與禁飛區(qū)的沖突，而無(wú)人機(jī)飛行區(qū)域的沖突歸根結(jié)底在于所申請(qǐng)飛行區(qū)域與禁飛區(qū)拓?fù)潢P(guān)系的判斷。為了能夠有效判斷飛行區(qū)域之間的拓?fù)潢P(guān)系，提出一種無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系判斷方法：基于點(diǎn)集拓?fù)淅碚?，利用九交模型?IM）對(duì)無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系進(jìn)行重新劃分和描述；提出解決無(wú)人機(jī)電子圍欄飛行區(qū)域拓?fù)潢P(guān)系判斷的算法流程以及計(jì)算實(shí)現(xiàn)方法；最后，利用VC++設(shè)計(jì)飛行區(qū)域拓?fù)潢P(guān)系判斷實(shí)驗(yàn)。結(jié)果表明，該方法能夠快速、有效判斷出相關(guān)拓?fù)潢P(guān)系。

關(guān)鍵詞：無(wú)人機(jī)；拓?fù)潢P(guān)系；九交模型；飛行區(qū)域沖突

DOI：10.11907/rjdk.172789

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

民用無(wú)人機(jī)發(fā)展帶來(lái)了民用無(wú)人機(jī)市場(chǎng)的繁榮，同時(shí)也由于管理的無(wú)序性使得“黑飛”問(wèn)題頻頻出現(xiàn)[1]。無(wú)人機(jī)實(shí)名制以及無(wú)人機(jī)飛行計(jì)劃申請(qǐng)是根除“黑飛”問(wèn)題的重要手段。隨著電子圍欄技術(shù)的發(fā)展與成熟，其在無(wú)人機(jī)飛行區(qū)域規(guī)劃中的應(yīng)用能夠有效解決無(wú)人機(jī)離地飛行計(jì)劃申請(qǐng)。而無(wú)人機(jī)飛行區(qū)域電子圍欄規(guī)劃中最主要的難點(diǎn)在于解決無(wú)人機(jī)飛行區(qū)域電子圍欄申請(qǐng)過(guò)程中出現(xiàn)的申請(qǐng)區(qū)域電子圍欄沖突問(wèn)題。由于無(wú)人機(jī)的飛行高度有嚴(yán)格限制，所以其電子圍欄區(qū)域?yàn)樘厥獾娜S區(qū)域，即底面為多邊形柱體。申請(qǐng)區(qū)域電子圍欄沖突問(wèn)題研究實(shí)際可以轉(zhuǎn)化為無(wú)人機(jī)飛行區(qū)域的空間拓?fù)潢P(guān)系判斷問(wèn)題研究。此外，由于無(wú)人機(jī)的飛行區(qū)域存在安全余度考量，因此本文研究的無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系與九交模型（9IM）描述的拓?fù)潢P(guān)系不同，需要對(duì)無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系描述進(jìn)行研究。

對(duì)于拓?fù)潢P(guān)系的描述，目前最主要的有基于邏輯的公理化拓?fù)淅碚摵蛡鹘y(tǒng)數(shù)學(xué)拓?fù)鋬煞N方法，其中應(yīng)用最多的是RCC（區(qū)域連接演算）形式化模型和4/9交模型。此外，還有很多學(xué)者提出的改進(jìn)方法。例如，趙仁量等[2]利用空間實(shí)體的Voronoi區(qū)域替代空間實(shí)體外部，改進(jìn)了9交模型，提出了基于Voronoi圖的新9交模型（V9I）。在拓?fù)潢P(guān)系計(jì)算方面：陳軍等[3]提出線(xiàn)目標(biāo)間復(fù)雜拓?fù)潢P(guān)系的分解-組合計(jì)算思路，計(jì)算線(xiàn)目標(biāo)之間的拓?fù)潢P(guān)系；鄧念東等[4]采用GTP作為描述空間目標(biāo)的體元，通過(guò)描述體元之間的關(guān)系，進(jìn)而表達(dá)空間目標(biāo)之間的拓?fù)潢P(guān)系；趙紅超[5]以擴(kuò)展的BMN交點(diǎn)算法為支撐，利用模板元編程的特性，設(shè)計(jì)并實(shí)現(xiàn)了點(diǎn)、線(xiàn)、面之間的拓?fù)潢P(guān)系的判斷；倪建華[6]針對(duì)空間拓?fù)潢P(guān)系類(lèi)型區(qū)分不夠詳細(xì)和算法描述薄弱等問(wèn)題，對(duì)點(diǎn)、線(xiàn)、面目標(biāo)之間拓?fù)潢P(guān)系的描述和計(jì)算進(jìn)行了研究；ArcGIS在組件ArcObjects的 IRelationalOperator接口中實(shí)現(xiàn)了7種拓?fù)潢P(guān)系，分別為相等、包含、被包含、相離、重疊、相接和相交[7]；Oracle公司提供了Oracle Spatial插件，并在Oracle中提供SDO_RELATE等函數(shù)查詢(xún)目標(biāo)間的拓?fù)潢P(guān)系。Oracle描述的拓?fù)潢P(guān)系類(lèi)型分別為相離、相接、重疊-邊界相交、重疊-邊界相離、相等、包含、被包含、覆蓋、位于和任意相交。

綜上所述，九交模型（9IM）廣泛應(yīng)用于拓?fù)潢P(guān)系的描述，能夠區(qū)分較多的拓?fù)潢P(guān)系。對(duì)于無(wú)人機(jī)飛行區(qū)域而言，傳統(tǒng)9IM所描述的某些拓?fù)潢P(guān)系類(lèi)型并不需要確定區(qū)分。為了能夠更加快速、簡(jiǎn)潔地判斷申請(qǐng)的無(wú)人機(jī)飛行區(qū)域與禁飛區(qū)是否存在沖突，本文對(duì)無(wú)人機(jī)飛行區(qū)域間拓?fù)潢P(guān)系進(jìn)行重新描述并對(duì)拓?fù)潢P(guān)系計(jì)算算法進(jìn)行研究。

1 無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系描述

空間關(guān)系主要包括拓?fù)潢P(guān)系、順序關(guān)系和度量關(guān)系。其中，拓?fù)潢P(guān)系是最為基礎(chǔ)和重要的空間關(guān)系。其計(jì)算建立在對(duì)空間目標(biāo)拓?fù)潢P(guān)系合理的描述上，適合空間目標(biāo)實(shí)際情況的拓?fù)潢P(guān)系描述能夠大大提高拓?fù)潢P(guān)系計(jì)算效率。本文研究對(duì)象是無(wú)人機(jī)飛行區(qū)域，在現(xiàn)實(shí)中不需要對(duì)9IM中所描述的鄰接、相等、覆蓋和反覆蓋進(jìn)行準(zhǔn)確區(qū)分，因?yàn)樵谟?jì)算兩個(gè)區(qū)域邊界存在相切時(shí)有很多情況需要考慮，這會(huì)大大增加計(jì)算量。只需要判斷兩個(gè)區(qū)域的邊界是否存在交集，只要交集不為空就可以把兩個(gè)區(qū)域的拓?fù)潢P(guān)系認(rèn)定為交疊。根據(jù)對(duì)九交模型（9IM）所描述的二維空間對(duì)象拓?fù)潢P(guān)系的分析以及無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系的特殊性，對(duì)無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系進(jìn)行重新歸納和描述。無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系可以歸納為以下4種：第一，相離，即區(qū)域a的所有邊界點(diǎn)都在區(qū)域b之外，同時(shí)區(qū)域b的所有邊界點(diǎn)都在區(qū)域a之外；第二，包含，即區(qū)域a的所有邊界點(diǎn)全在區(qū)域b的內(nèi)部；第三，反包含，即區(qū)域b所有的邊界點(diǎn)全在區(qū)域a的內(nèi)部；第四，交疊，即區(qū)域a與區(qū)域b的邊界存在交點(diǎn)（邊界交集不為空）。

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

根據(jù)無(wú)人機(jī)飛行區(qū)域的特殊性，將無(wú)人機(jī)飛行區(qū)域的拓?fù)潢P(guān)系歸納描述為4種拓?fù)潢P(guān)系：{Disjoint，Contains，Contained-by，Cross}。圖1給出了無(wú)人機(jī)飛行區(qū)域的4種拓?fù)潢P(guān)系，并給出了相應(yīng)的9IM矩陣表現(xiàn)形式。

2 無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系計(jì)算

2.1 無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系判斷流程

在上述判斷流程中涉及到折線(xiàn)與面位置關(guān)系的判斷、直線(xiàn)與面位置關(guān)系的判斷、點(diǎn)是否在面內(nèi)的判斷、點(diǎn)是否在線(xiàn)上的判斷和兩條直線(xiàn)是否相交的判斷。以下分別對(duì)所涉及的判斷算法進(jìn)行分析。

折線(xiàn)與面位置關(guān)系的判斷：折線(xiàn)與面位置關(guān)系可以劃分為折線(xiàn)與面相交、折線(xiàn)與面相離和折線(xiàn)在面內(nèi)部3種關(guān)系[9]。在進(jìn)行位置關(guān)系判斷時(shí)，如果折線(xiàn)中每一條直線(xiàn)都在面的內(nèi)部，則折線(xiàn)在面的內(nèi)部；如果折線(xiàn)中有任一條直線(xiàn)與面相交，則折線(xiàn)與面相交；如果折線(xiàn)中所有直線(xiàn)都在面的外部，則折線(xiàn)與面相離。

直線(xiàn)與面位置關(guān)系的判斷：直線(xiàn)與面位置關(guān)系可以劃分為直線(xiàn)與面相交、直線(xiàn)與面相離和直線(xiàn)在面內(nèi)部3種關(guān)系[10]。在進(jìn)行位置關(guān)系判斷時(shí)，如果直線(xiàn)的兩個(gè)端點(diǎn)都在面的內(nèi)部，則直線(xiàn)在面內(nèi)部；如果直線(xiàn)的兩個(gè)端點(diǎn)分別在面的不同部分，則直線(xiàn)與面相交；如果直線(xiàn)的兩個(gè)端點(diǎn)都在面外部，且直線(xiàn)與面邊界的任一直線(xiàn)段都不相交，則直線(xiàn)與面相離。

點(diǎn)是否在面內(nèi)的判斷：采用傳統(tǒng)的射線(xiàn)法進(jìn)行計(jì)算，通過(guò)穿過(guò)該點(diǎn)射線(xiàn)與面交點(diǎn)的個(gè)數(shù)判斷[11]。若交點(diǎn)個(gè)數(shù)為奇數(shù)，則點(diǎn)在面內(nèi)；若交點(diǎn)個(gè)數(shù)為偶數(shù)，則點(diǎn)在面外部。

點(diǎn)是否在線(xiàn)上的判斷：首先分別計(jì)算直線(xiàn)的長(zhǎng)度和點(diǎn)到直線(xiàn)兩個(gè)端點(diǎn)的長(zhǎng)度，用點(diǎn)到直線(xiàn)兩個(gè)端點(diǎn)長(zhǎng)度的和減去直線(xiàn)的長(zhǎng)度，得到的值取絕對(duì)值除以直線(xiàn)的長(zhǎng)度，然后將值與α對(duì)比，如果小于α，則點(diǎn)在直線(xiàn)上；否則點(diǎn)不在線(xiàn)上。

2.2 無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系計(jì)算實(shí)現(xiàn)方法

根據(jù)上述算法思想及流程，以VC++語(yǔ)言作為工具實(shí)現(xiàn)其具體計(jì)算，在實(shí)現(xiàn)過(guò)程中定義以下函數(shù)：polygonAndPolygon（）判斷面與面關(guān)系；polyLineAndPolygon（）判斷折線(xiàn)與面關(guān)系；LineAndPolygon（）判斷直線(xiàn)與面關(guān)系；isPointInPolygon（）判斷點(diǎn)是否在面內(nèi)；isLineIntersect（）判斷兩條直線(xiàn)是否相交；isPointInLine（）函數(shù)判斷點(diǎn)是否在線(xiàn)上。在算法實(shí)現(xiàn)過(guò)程中各個(gè)函數(shù)的調(diào)用關(guān)系見(jiàn)圖2。

3 實(shí)驗(yàn)驗(yàn)證

在實(shí)驗(yàn)中（電腦配置：英特爾酷睿3處理器3.50GHZ，4.00GB內(nèi)存，500GB硬盤(pán)，win7 64位操作系統(tǒng)），以Visual Studio 2013作為開(kāi)發(fā)平臺(tái)，以VC++為可視化工具，設(shè)計(jì)一個(gè)拓?fù)潢P(guān)系判斷驗(yàn)證系統(tǒng)，包括飛行區(qū)域的輸入、飛行區(qū)域的交互（縮放、平移、刪除）、飛行區(qū)域的選取以及飛行區(qū)域拓?fù)潢P(guān)系的計(jì)算等功能。在驗(yàn)證過(guò)程中，由于要驗(yàn)證區(qū)域是驗(yàn)證者輸入的，特別是對(duì)于區(qū)域邊界間存在相互重合的情況可能會(huì)很難輸入準(zhǔn)確，因此輸入?yún)^(qū)域的誤差可能會(huì)造成判斷結(jié)果與實(shí)際輸入位置關(guān)系存在不一致的情況。以下是分別對(duì)所描述飛行區(qū)域拓?fù)潢P(guān)系判斷的驗(yàn)證：

圖3選取一組相離區(qū)域進(jìn)行驗(yàn)證，可以看出其位置關(guān)系與判斷結(jié)果相一致，即區(qū)與區(qū)拓?fù)潢P(guān)系為相離。

圖4、圖5和圖6分別選取3種不同的相交位置關(guān)系進(jìn)行拓?fù)潢P(guān)系驗(yàn)證，其驗(yàn)證結(jié)果與預(yù)期算法結(jié)果相一致，即區(qū)與區(qū)拓?fù)潢P(guān)系為相交。

圖7中選取灰色區(qū)域包含于黑色區(qū)域進(jìn)行驗(yàn)證，其實(shí)際位置關(guān)系與判斷結(jié)果相一致，即區(qū)與區(qū)拓?fù)潢P(guān)系為包含。

圖8中選取灰色區(qū)域包含黑色區(qū)域進(jìn)行驗(yàn)證，其實(shí)際位置關(guān)系與判斷結(jié)果相一致，即區(qū)與區(qū)拓?fù)潢P(guān)系為反包含。

4 結(jié)語(yǔ)

對(duì)于無(wú)人機(jī)飛行區(qū)域而言，不需要對(duì)飛行區(qū)域邊界存在切點(diǎn)的問(wèn)題進(jìn)行明確區(qū)分，能夠更加簡(jiǎn)化對(duì)無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系的描述，從而減少算法計(jì)算量。因此，本文采用9IM對(duì)無(wú)人機(jī)飛行區(qū)域拓?fù)潢P(guān)系進(jìn)行重歸新納和描述，詳細(xì)介紹了拓?fù)潢P(guān)系判斷中的算法流程以及具體實(shí)現(xiàn)方法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的可行性。飛行區(qū)域拓?fù)潢P(guān)系的判斷能夠有效解決飛行區(qū)域沖突問(wèn)題，進(jìn)而在無(wú)人機(jī)飛行區(qū)域電子圍欄規(guī)劃中能得到有效應(yīng)用。

參考文獻(xiàn)：

[1] 柯玉寶，車(chē)彥卓.如何規(guī)范管理無(wú)人機(jī)[J].機(jī)器人產(chǎn)業(yè)，2016，1：16-21.

[2] 趙仁量.基于Voronoi圖的空間關(guān)系計(jì)算研究[D].長(zhǎng)沙：中南大學(xué)，2002.

[3] 陳軍，劉萬(wàn)增，李志林，等.線(xiàn)目標(biāo)拓?fù)潢P(guān)系的細(xì)化計(jì)算方法[J].測(cè)繪學(xué)報(bào)，2006，35（8）：255-230.

[4] 鄧念東，候恩科.基于GTP單純刨分的地下實(shí)體拓?fù)潢P(guān)系形式化描述方法[J].煤炭學(xué)報(bào)，2008，33（5）：527-531.

[5] 趙紅超.空間關(guān)系的研究和實(shí)現(xiàn)[D].北京：中國(guó)科學(xué)院，2006.

[6] 倪建華.拓?fù)潢P(guān)系計(jì)算方法研究與實(shí)現(xiàn)[D].長(zhǎng)沙：中南大學(xué)，2009.

[7] 高峰.技術(shù)引領(lǐng)未來(lái)——無(wú)人機(jī)云系統(tǒng)全面解析[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2016，7：13-14.

[8] 鄧敏，李成名，劉文寶.利用拓?fù)浜投攘肯嘟Y(jié)合的方法描述面目標(biāo)間的空間關(guān)系[J].測(cè)繪學(xué)報(bào)，2002，31（2）：2-3.

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

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

[11] 王潤(rùn)科，張彥麗.判斷點(diǎn)與多邊形位置關(guān)系的算法綜述[J].甘肅聯(lián)合大學(xué)學(xué)報(bào)，2006，20（6）：2-4.

（責(zé)任編輯：何 麗）