基于動(dòng)態(tài)三角剖分的潛在沖突篩選方法

蘇志剛, 符笑嫻, 郝敬堂

(1. 中國民航大學(xué)中歐航空工程師學(xué)院, 天津 300300; 2. 中國民航大學(xué)智能信號(hào)與圖像處理天津市重點(diǎn)實(shí)驗(yàn)室, 天津 300300; 3. 福建通航航空產(chǎn)業(yè)有限公司, 福建 福州 350000)

?

基于動(dòng)態(tài)三角剖分的潛在沖突篩選方法

蘇志剛1,2, 符笑嫻1,3, 郝敬堂1

(1. 中國民航大學(xué)中歐航空工程師學(xué)院, 天津 300300; 2. 中國民航大學(xué)智能信號(hào)與圖像處理天津市重點(diǎn)實(shí)驗(yàn)室, 天津 300300; 3. 福建通航航空產(chǎn)業(yè)有限公司, 福建 福州 350000)

摘要：圍繞動(dòng)態(tài)Delaunay三角剖分(dynamic delaunay triangulation,DDT)方法難以對(duì)空域動(dòng)態(tài)三角剖分中產(chǎn)生的反轉(zhuǎn)三角形實(shí)現(xiàn)穩(wěn)定局部更新問題,提出以順序的點(diǎn)刪除與點(diǎn)增加的局部更新方式替代反轉(zhuǎn)三角形的局部更新方式的改進(jìn)方法。實(shí)驗(yàn)結(jié)果表明,改進(jìn)的DDT方法獲得的潛在沖突航空器數(shù)目與空域內(nèi)航空器密度無關(guān),且具有更低的局部更新時(shí)間復(fù)雜度和穩(wěn)健性。改進(jìn)的DDT方法更穩(wěn)健,更適用于空管指揮系統(tǒng)的潛在沖突篩選任務(wù)。

關(guān)鍵詞：空中交通管理; 沖突檢測; 動(dòng)態(tài)Delaunay三角剖分; 移動(dòng)點(diǎn)集; 動(dòng)態(tài)更新

0引言

近年來,隨著經(jīng)濟(jì)的飛速發(fā)展,民用航空器總量迅速增加,使得航空器運(yùn)行空域變得越來越擁擠,加之人為、天氣、故障等因素的影響,航空器間空中沖突、甚至空中相撞風(fēng)險(xiǎn)日益增大。例如:1996年沙特與哈薩克斯坦的客機(jī)在空中相撞,導(dǎo)致300多人遇難。2002年德國與俄羅斯的客機(jī)在空中相撞,機(jī)上70多人遇難。

地面空管指揮系統(tǒng)中的短期沖突告警(short term conflict alert,STCA)子系統(tǒng)[1]可以逐對(duì)判斷航空器間突破安全間隔標(biāo)準(zhǔn)的風(fēng)險(xiǎn)[2-4],對(duì)存在危險(xiǎn)接近或相撞可能性的航空器給出相應(yīng)的警示,協(xié)助管制員對(duì)空域內(nèi)航空器進(jìn)行調(diào)度、管理。隨著航空器數(shù)目的增大,STCA子系統(tǒng)計(jì)算復(fù)雜度將以平方量級(jí)增長。為有效地降低系統(tǒng)計(jì)算復(fù)雜度,提高短期沖突檢測的可靠性、實(shí)時(shí)性,STCA子系統(tǒng)進(jìn)行沖突檢測前需要對(duì)潛在沖突進(jìn)行篩選[5-6]。

距離門限法是一種經(jīng)典的潛在沖突篩選方法,以航空器間的距離為準(zhǔn)則篩選潛在沖突對(duì),可以在一定程度上減少STCA負(fù)荷。然而隨著空中航空器數(shù)量的增多,特別是在終端區(qū)域,航空器密度加大,以航空器間距離為基礎(chǔ)的距離門限法需要跟蹤更多的潛在沖突對(duì)。近年來,有學(xué)者將圖形學(xué)的Delaunay三角剖分技術(shù)應(yīng)用于潛在沖突篩選處理[6-9],使得潛在沖突對(duì)篩選數(shù)量與空域內(nèi)航空器密度關(guān)系不大,從而降低了系統(tǒng)計(jì)算復(fù)雜度與空域內(nèi)航空器數(shù)目之間的關(guān)聯(lián)。

空域內(nèi)航空器的移動(dòng)特征,使學(xué)者將移動(dòng)點(diǎn)的Delaunay三角剖分技術(shù)應(yīng)用于空管領(lǐng)域[7-10]。文獻(xiàn)[7]將快拍式Delaunay三角剖分(snapshot Delaunay triangulation,SDT)用于潛在沖突篩選。SDT方法需要周期地根據(jù)航空器位置信息進(jìn)行Delaunay三角剖分,沒有利用刷新前后航空器位置關(guān)系的繼承性,因此,其計(jì)算復(fù)雜度較高。動(dòng)能Delaunay三角剖分(kinetic Delaunay triangulation,KDT)方法[8,10]根據(jù)移動(dòng)點(diǎn)的速度、位置信息,以連續(xù)時(shí)間的方式預(yù)測三角網(wǎng)格發(fā)生拓?fù)渥兓臅r(shí)刻,僅在發(fā)生拓?fù)渥兓臅r(shí)刻對(duì)發(fā)生拓?fù)渥兓木植窟M(jìn)行三角剖分更新。KDT方法解決了空間三角剖分的拓?fù)浣Y(jié)構(gòu)的繼承問題,可以有效地降低系統(tǒng)預(yù)選的復(fù)雜度,但對(duì)拓?fù)浣Y(jié)構(gòu)變化時(shí)刻的解算會(huì)引入額外計(jì)算量,當(dāng)存在大量拓?fù)渥兓瘯r(shí),相應(yīng)引入的復(fù)雜度較大[11-12]。動(dòng)態(tài)Delaunay三角剖分(dynamic Delaunay triangulation,DDT)方法[9]檢測在離散時(shí)間點(diǎn)處的拓?fù)渥兓?對(duì)局部進(jìn)行三角剖分更新。DDT方法與KDT方法相比,減少了拓?fù)浣Y(jié)構(gòu)變化時(shí)刻解算的計(jì)算量。文獻(xiàn)[9]所提出的DDT方法可以有效地解決航空器進(jìn)入、離開或位置更新等情況下的空域Delaunay三角剖分的動(dòng)態(tài)更新問題,但當(dāng)空域Delaunay三角剖分的拓?fù)浣Y(jié)構(gòu)發(fā)生較大變化時(shí),如存在反轉(zhuǎn)三角形的情況時(shí),該方法無法有效地完成空域Delaunay三角剖分的局部更新,甚至可能陷入死循環(huán)[13]。

本文將在文獻(xiàn)[9]的DDT方法基礎(chǔ)上,針對(duì)反轉(zhuǎn)三角形的存在導(dǎo)致DDT方法不穩(wěn)定問題,提出一種可以有效解決反轉(zhuǎn)三角形存在時(shí)的局部更新的方法,使得改進(jìn)的DDT方法更適于應(yīng)用到短期沖突檢測的篩選處理中。

1空域Delaunay三角剖分

當(dāng)航空器在航路上飛行時(shí),航空器間的短期沖突檢測主要是針對(duì)同一高度層的航空器進(jìn)行的,因此將空域中同一高度層的航空器看作離散點(diǎn)集,并依據(jù)Delaunay三角剖分準(zhǔn)則,使得剖分后三角形的外接圓內(nèi)不包含除頂點(diǎn)處航空器以外的任意航空器,形成以航空器為頂點(diǎn)的不均勻的三角形網(wǎng)格,如圖1所示。由圖1可見,空域內(nèi)的航空器以最近鄰的三個(gè)航空器形成三角形,連接航空器的線段(三角形的邊)均不相交,且與遠(yuǎn)處的航空器不直接發(fā)生聯(lián)系。這個(gè)特點(diǎn)與空管指揮系統(tǒng)中的潛在沖突航空器的特征相似,因此,可以利用Delaunay三角剖分所獲得的空域內(nèi)航空器的拓?fù)浣Y(jié)構(gòu),并以此作為潛在沖突篩選手段。

圖1　空域Delaunay三角剖分

空域Delaunay三角剖分的初始化就是根據(jù)系統(tǒng)中航空器的初始位置,按照靜態(tài)離散點(diǎn)集的方式對(duì)其進(jìn)行Delaunay三角剖分。空域Delaunay三角剖分的初始化可以采用分治算法、逐點(diǎn)插入法、三角網(wǎng)生長法等經(jīng)典算法實(shí)現(xiàn),本文采用逐點(diǎn)插入法。逐點(diǎn)插入法的起始需要獲得包含全部離散點(diǎn)集的凸多邊形,然后采用逐點(diǎn)插入的方式進(jìn)行Delaunay三角剖分。為降低尋找凸多邊形的復(fù)雜度,可將關(guān)注空域的四角設(shè)置4個(gè)虛擬點(diǎn),進(jìn)而形成包含空域全部航空器的凸多邊形,而且執(zhí)行逐點(diǎn)插入法即可完成空域的初始Delaunay三角剖分。

2拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)更新

空域內(nèi)航空器的運(yùn)行將引起空域三角網(wǎng)格的改變,由于航空器的軌跡的連續(xù)性,航空器間的拓?fù)浣Y(jié)構(gòu)呈現(xiàn)出緩變特點(diǎn),使得空域Delaunay三角剖分具有相對(duì)穩(wěn)定性。對(duì)于空域的三角網(wǎng)格,在緩變過程中出現(xiàn)不滿足Delaunay三角剖分準(zhǔn)則的三角網(wǎng)格也只發(fā)生在局部的,而非整體性的。DDT方法就是根據(jù)空域內(nèi)航空器的增、減及位置變化,對(duì)空域的初始Delaunay三角剖分進(jìn)行局部動(dòng)態(tài)更新,實(shí)現(xiàn)空域Delaunay三角剖分的動(dòng)態(tài)更新的目的。

空域內(nèi)出現(xiàn)新增航空器時(shí),可以采用點(diǎn)插入技術(shù)對(duì)空域內(nèi)局部Delaunay三角剖分進(jìn)行更新[14]。首先檢索出外接圓包含新增航空器的三角形,刪除相應(yīng)三角形,形成凸多邊形。將凸多邊形的頂點(diǎn)與新增航空器點(diǎn)相連接即完成局部Delaunay三角剖分。假設(shè)需要判斷出現(xiàn)在點(diǎn)P4處的航空器是否位于ΔP1P2P3的外接圓內(nèi)。根據(jù)點(diǎn)P1、P2、P3和P4的橫、縱坐標(biāo)xi和yi(i=1,2,3,4)可以定義矩陣

(1)

假設(shè)P1、P2、P3為逆時(shí)針排列,若C1234的行列式|C1234|>0,則點(diǎn)P4在ΔP1P2P3的外接圓內(nèi),若行列式|C1234|<0,則點(diǎn)P4在ΔP1P2P3的外接圓外[15]。由于三角形頂點(diǎn)的排列順、逆時(shí)針判斷較為不便,因此引入輔助點(diǎn)P5,使其位于P1P2的延長線上,且坐標(biāo)為(x5,y5)=(2x2-x1,2y2-y1)。顯然輔助點(diǎn)P5一定位于ΔP1P2P3的外接圓外。所以,若點(diǎn)P4在ΔP1P2P3的外接圓內(nèi),判斷準(zhǔn)則

(2)

必然成立。

若空域內(nèi)某航空器飛離時(shí),由于該點(diǎn)的消失,使得空域Delaunay三角剖分的局部出現(xiàn)空腔,而且該空腔有可能不是凸多邊形,直接對(duì)其三角剖分可能出現(xiàn)交叉的邊。可以采用凸耳權(quán)值的點(diǎn)刪除算法進(jìn)行維護(hù)[16]。

航空器運(yùn)動(dòng)引起空域三角形緩變,出現(xiàn)局部三角形不再滿足Delaunay三角剖分準(zhǔn)則,即原有的外接圓內(nèi)出現(xiàn)了其他航空器。進(jìn)入三角形外接圓的航空器與該三角形構(gòu)成兩個(gè)共邊三角形結(jié)構(gòu),利用局部優(yōu)化程序(local optimization procedure,LOP)可以實(shí)現(xiàn)局部拓?fù)涓耓13,17]。

3對(duì)反轉(zhuǎn)三角形的局部更新

前面的DDT方法可以實(shí)現(xiàn)對(duì)空域內(nèi)航空器間拓?fù)浣Y(jié)構(gòu)的基本動(dòng)態(tài)維護(hù),然而,當(dāng)存在位置變化較大的航空器、或存在尺度較小的三角形時(shí)會(huì)出現(xiàn)三角形反轉(zhuǎn)的可能性。三角形反轉(zhuǎn)即為該三角形的頂點(diǎn)排列的順、逆時(shí)針順序發(fā)生改變,如圖2所示。圖2中點(diǎn)A在前后兩個(gè)時(shí)刻的位置變化,使得三角網(wǎng)格頂點(diǎn)ABC由順時(shí)針方向轉(zhuǎn)變?yōu)槟鏁r(shí)針方向。反轉(zhuǎn)ΔABC有存在使其周邊的三角形不再滿足Delaunay三角剖分準(zhǔn)則,如圖2(b)的陰影區(qū)域。采用LOP處理已經(jīng)無法獲得正確的Delaunay三角剖分,需要新的局部動(dòng)態(tài)維護(hù)方案。

圖2　反轉(zhuǎn)三角形網(wǎng)格對(duì)局部的影響

實(shí)現(xiàn)對(duì)反轉(zhuǎn)三角形的局部拓?fù)涓碌那疤崾切枰ㄎ环崔D(zhuǎn)三角形。判斷是否存在反轉(zhuǎn)三角形的基礎(chǔ)是檢測三角形頂點(diǎn)的排列方向是否發(fā)生改變。定義在第n時(shí)刻三角網(wǎng)格頂點(diǎn)矩陣

(3)

式中,xi(n)和yi(n)分別為三角形第i(i=1,2,3)個(gè)頂點(diǎn)Pi在第n時(shí)刻的橫、縱坐標(biāo)。如果三角形的頂點(diǎn)P1、P2和P3是按順時(shí)針排列,則三角形頂點(diǎn)矩陣T(n)的行列式|T(n)|<0,反之則|T(n)|>0。因此,三角形頂點(diǎn)排列方向是否發(fā)生改變可由式(4)判斷。

(4)

式(4)表明根據(jù)相鄰時(shí)刻的三角形頂點(diǎn)矩陣行列式的值是否異號(hào)可以判斷三角形是否為反轉(zhuǎn)三角形。遍歷空域內(nèi)全部三角形,檢索出所有反轉(zhuǎn)三角形。

反轉(zhuǎn)三角形確定后,還需要進(jìn)一步確定反轉(zhuǎn)點(diǎn)。反轉(zhuǎn)點(diǎn)是指進(jìn)入反轉(zhuǎn)三角形的共邊三角形內(nèi)部的反轉(zhuǎn)三角形的頂點(diǎn),如圖2所示的頂點(diǎn)A。反轉(zhuǎn)點(diǎn)鄰近離散點(diǎn)的局部拓?fù)浣Y(jié)構(gòu)發(fā)生急劇變化,需要進(jìn)行重新Delaunay三角剖分。對(duì)于反轉(zhuǎn)三角形,可以存在3個(gè)與其共邊的三角形,因此需要根據(jù)反轉(zhuǎn)點(diǎn)與共邊三角形的關(guān)系確定反轉(zhuǎn)點(diǎn)。

判斷某點(diǎn)在三角形內(nèi)部的方法可采用內(nèi)角和法、同向法、重心法等方法,本文采用計(jì)算效率較高的重心法。假設(shè)判斷ΔP1P2P3的頂點(diǎn)P1是否為反轉(zhuǎn)點(diǎn),點(diǎn)P1所對(duì)應(yīng)的共邊三角形為ΔP2P3P4,需要判斷下一時(shí)刻點(diǎn)P1是否落在ΔP2P3P4內(nèi)。定義矩陣

(5)

(6)

(7)

利用式(5)～式(7)可得

(8)

(9)

式中,(·)-1表示求倒數(shù)操作。因此,若點(diǎn)P1落在共邊ΔP2P3P4內(nèi)需滿足

(10)

若式(10)不成立,則說明點(diǎn)P1未落在共邊ΔP2P3P4內(nèi)。

由于航空器間安全距離的限制,航空器的單次位置變化量通常小于Delaunay剖分后的三角形尺度,反轉(zhuǎn)點(diǎn)一般只落在反轉(zhuǎn)三角形的共邊三角形內(nèi)。反轉(zhuǎn)點(diǎn)在短時(shí)間內(nèi)跨越多個(gè)三角形,落在非共邊三角形內(nèi)的可能性非常小,本文不予考慮。

由于反轉(zhuǎn)點(diǎn)的存在,反轉(zhuǎn)三角形周邊的部分三角形需要重新進(jìn)行局部Delaunay三角剖分。本局部的Delaunay剖分等價(jià)于原來所處位置消失了一個(gè)點(diǎn),同時(shí)在反轉(zhuǎn)點(diǎn)的共邊三角形內(nèi)增加一個(gè)新點(diǎn)。因此,對(duì)于反轉(zhuǎn)三角形的局部更新可以用刪除點(diǎn)與增加點(diǎn)的方式進(jìn)行局部更新。由圖2(b)可見,反轉(zhuǎn)點(diǎn)A在共邊三角形中按增加點(diǎn)進(jìn)行更新時(shí),可能會(huì)影響刪除點(diǎn)區(qū)域的剖分,因此,反轉(zhuǎn)三角形的局部更新需要按刪除點(diǎn)、增加點(diǎn)的順序進(jìn)行更新。

4仿真實(shí)驗(yàn)

本部分將采用數(shù)值仿真的方法比較改進(jìn)的DDT方法與SDT方法、距離門限方法作為潛在沖突篩選方法的篩選效率。根據(jù)空管指揮系統(tǒng)的實(shí)際指標(biāo),仿真實(shí)驗(yàn)中考慮1 000km×1 000km空域。空域內(nèi)航空器的位置及速度以隨機(jī)方式產(chǎn)生,其中航空器的位置分布服從以空域中心為的二維高斯分布,航空器速度大小服從700～1 000km/h內(nèi)的均勻分布,速度方向服從360°方向的均勻分布。假設(shè)空域內(nèi)的航空器以勻速直線運(yùn)動(dòng)。

首先,分析空域內(nèi)航空器數(shù)目對(duì)不同篩選方法初始化時(shí)間及篩選潛在沖突航空器數(shù)量的影響。將空域內(nèi)航空器數(shù)目由20加逐步增加到500架,在每個(gè)數(shù)據(jù)點(diǎn)執(zhí)行100次蒙特卡羅實(shí)驗(yàn),分別統(tǒng)計(jì)改進(jìn)的DDT方法、SDT方法、距離門限法在以50km和100km為門限時(shí)完成首次潛在沖突航空器檢測所需的時(shí)間和潛在沖突航空器的平均數(shù)量,如圖3所示。

圖3　空域內(nèi)航空器數(shù)量對(duì)篩選方法初始化的影響

如前所述,改進(jìn)的DDT方法和SDT方法篩選潛在沖突航空器是利用空域航空器的Delaunay三角剖分實(shí)現(xiàn)的。這兩種方法確定的潛在沖突航空器的平均數(shù)量是指空域內(nèi)航空器所在三角剖分中的邊的平均數(shù)。距離門限法是計(jì)算兩兩航空器之間的距離,通過與相應(yīng)門限值比較來確定是否存在潛在沖突對(duì)。因此,距離門限法的初始化時(shí)間與門限值無關(guān),改進(jìn)的DDT方法和SDT方法均需要完成空域航空器的Delaunay三角剖分,所以兩者的初始化時(shí)間也相同,如圖3(a)所示。由如圖3(a)還可以看出,隨著空域內(nèi)航空器數(shù)目的增加,所有方法的初始化時(shí)間均增加,而且距離門限法時(shí)間增長速度明顯快于改進(jìn)的DDT方法和SDT方法。當(dāng)空域內(nèi)航空器數(shù)目較少時(shí),距離門限法的效率優(yōu)于改進(jìn)的DDT方法和SDT方法,但空域內(nèi)航空器數(shù)目增加到一定數(shù)量時(shí),改進(jìn)的DDT方法和SDT方法將優(yōu)于距離門限方法。

在潛在沖突航空器篩選方面,由圖3(b)可見,距離門限方法所篩選出的潛在沖突航空器數(shù)目與空域內(nèi)航空器數(shù)目及門限大小有關(guān)。空域內(nèi)航空器數(shù)目的增大,導(dǎo)致篩選出的潛在沖突航空器平均數(shù)呈線性增長,而且增長的速率與門限有大小有關(guān)。在圖3(b)中,航空器數(shù)目的增大,導(dǎo)致空域內(nèi)航空器的密度加大,由此可以推斷,在航空器密集區(qū)域,如終端區(qū)域等,采用距離門限方法篩選出手潛在沖突航空器數(shù)量將顯著增加。由圖3(b)可見,改進(jìn)的DDT方法和SDT方法所篩選出的潛在沖突航空器數(shù)目約為3,并且與空域內(nèi)航空器的數(shù)目或航空器的密度無關(guān),因此,更適宜使用在航空器密集區(qū)域的短時(shí)沖突告警檢測的篩選處理。

其次,分析空域內(nèi)增、減航空器對(duì)篩選方法效率的影響。考慮空域內(nèi)已有航空器200架,采用逐一增加的方式將航空器數(shù)量增加到225架,考察每增加一架航空器時(shí),每個(gè)篩選方法對(duì)時(shí)間的消耗。同樣,在每個(gè)數(shù)據(jù)點(diǎn)處進(jìn)行100次蒙特卡羅實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖4所示。由圖4可見,距離門限方法的刷新時(shí)間隨著航空器數(shù)目的增加而增大,這與圖3(a)結(jié)果一致。隨著航空器數(shù)目的增加,SDT方法的時(shí)間消耗有些許增加,這是因?yàn)槊看慰沼駾elaunay三角剖分的離散點(diǎn)數(shù)增加所致。改進(jìn)的DDT方法的時(shí)間消耗基本不變,且時(shí)間消耗最低。每次增加1個(gè)目標(biāo),對(duì)于改進(jìn)的DDT方法只是對(duì)空域Delaunay剖分的局部進(jìn)行更新,因此,每次引入的計(jì)算量基本相當(dāng)。

圖4　空域內(nèi)航空器數(shù)量逐一增加對(duì)刷新時(shí)間的影響

相類似地考慮空域內(nèi)航空逐一刪除對(duì)篩選方法效率的影響。仍然假設(shè)空域內(nèi)已有航空器200架,采用逐一刪除方式將航空器數(shù)量減少到175架,考察每刪除一架航空器時(shí),每個(gè)篩選方法對(duì)時(shí)間的消耗。同樣,在每個(gè)數(shù)據(jù)點(diǎn)處進(jìn)行100次蒙特卡羅實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖5所示。與圖4相比較,距離門限方法的刷新時(shí)間與航空器數(shù)目相關(guān),SDT方法的時(shí)間消耗也與航空器數(shù)目有關(guān),但受影響程序不顯著,改進(jìn)的DDT方法的時(shí)間消耗基本不受航空器數(shù)目的影響,且時(shí)間消耗最低。

圖5　空域內(nèi)航空器數(shù)量逐一減少對(duì)刷新時(shí)間的影響

再考慮同時(shí)增加若干架航空器對(duì)各篩選方法的時(shí)間消耗的影響。實(shí)驗(yàn)條件同前,只是每次增加的航空器個(gè)數(shù)由1個(gè)逐步增加到25個(gè)。在每種情況下進(jìn)行100次蒙特卡羅實(shí)驗(yàn),統(tǒng)計(jì)結(jié)果如圖6所示。與圖4相比較可見,距離門限法和SDT方法的時(shí)間消耗一致,而對(duì)于改進(jìn)的DDT方法,時(shí)間消耗存在一定的增長。這是因此每次增加的航空器數(shù)目不同,局部更新的量也相應(yīng)地增大,從而導(dǎo)致時(shí)間消耗增加。

圖6　批量增加空域內(nèi)航空器數(shù)量對(duì)刷新時(shí)間的影響

最后,分析空域Delaunay剖分中存在反轉(zhuǎn)三角形時(shí),各種篩選方法的時(shí)間消耗。考慮空域內(nèi)存在航空器200架,通過交換某個(gè)三角形的兩個(gè)頂點(diǎn)坐標(biāo)來形成反轉(zhuǎn)三角形,分別統(tǒng)計(jì)存在1個(gè)到25個(gè)反轉(zhuǎn)三角形時(shí)的幾種方法的時(shí)間消耗。在每個(gè)實(shí)驗(yàn)條件下進(jìn)行100次蒙特卡羅實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖7所示。由圖7可見,當(dāng)空域內(nèi)Delaunay剖分中存在反轉(zhuǎn)三角形時(shí),空域內(nèi)航空器數(shù)目未發(fā)生改變,所以不影響距離門限方法和SDT方法的時(shí)間消耗,而對(duì)于改進(jìn)的DDT方法,反轉(zhuǎn)三角形數(shù)量影響著局部更新復(fù)雜度,隨著反轉(zhuǎn)三角形數(shù)量的增大,改進(jìn)的DDT方法的時(shí)間消耗呈線性增長。在實(shí)際運(yùn)行環(huán)境中,瞬時(shí)增加的反轉(zhuǎn)三角形的個(gè)數(shù)通常較少,一般不會(huì)超過3個(gè),由圖7可見,在較少反轉(zhuǎn)三角形的條件下,改進(jìn)的DDT方法的時(shí)間消耗明顯低于其他方法。

圖7　空域內(nèi)反轉(zhuǎn)三角形個(gè)數(shù)對(duì)刷新時(shí)間的影響

5結(jié)論

本文對(duì)DDT方法的改進(jìn),使其可以有效地解決空域Delaunay三角剖分中的反轉(zhuǎn)三角形檢測問題,通過對(duì)反轉(zhuǎn)點(diǎn)的確定,可以用順序點(diǎn)刪除與點(diǎn)添加的局部更新方式實(shí)現(xiàn)對(duì)反轉(zhuǎn)三角形的局部更新。本文所提方法既保持了DDT方法的局部更新特點(diǎn),又解決文獻(xiàn)[9]中DDT方法無法對(duì)反轉(zhuǎn)三角形情況進(jìn)行拓?fù)涓碌娜毕?因此,本文提出的改進(jìn)的DDT方法是一種穩(wěn)健、高效的Delaunay三角剖分動(dòng)態(tài)維護(hù)方法。實(shí)驗(yàn)結(jié)果表明,該方法在航空器潛在沖突篩選處理上具有較明顯的效率優(yōu)勢。

參考文獻(xiàn)：

[1] EUROCONTROL. Eurocontral guidance material for short term conflict alert, May 2009[EB/OL].[2015-06-13].http:∥www.eurocontrol.int/publications/eurocontrol-guidance-material-short-term-conflict-alert.

[2] Hess M, Heidger R, Bredemeyer J. Tracker quality monitoring by nondedicated calibration flights[J].IEEEAerospaceandElectronicSystemsMagazine, 2014, 29(8): 10-16.

[3] Liu W, Hwang I. Probabilistic aircraft mid-air conflict resolution using stochastic optimal control[J].IEEETrans.onIntelligentTransportationSystems, 2014, 15(1): 37-46.

[4] Matsuno Y, Tsuchiya T. Stochastic 4D trajectory optimization for aircraft conflict resolution[C]∥Proc.oftheIEEEAerospaceConference, 2014：1-10.

[5] Richard E, Jonathan F. Multiobjective optimization of safety related systems: an application to short-term conflict alert[J].IEEETrans.onEvolutionaryComputation, 2006, 10(2): 187-198.

[6] Chiang Y J, Klosowski J T, Lee C, et al. Geometric algorithms for conflict detection/resolution in air traffic management[C]∥Proc.ofthe36thIEEEConferenceonDecisionandControl, 1997: 1835-1840.

[7] Liu X, Han S C. Delaunay method for free flight conflict detection[J].JournalofDataAcquisition&Processing,2002,17(4):446-449.(劉星,韓松臣.用于自由飛行沖突探測的Delaunay方法[J].數(shù)據(jù)采集與處理,2002,17(4):446-449.)

[9] Su Z G, Wang Z, Wu R. Robust dynamic Delaunay triangulation technology for moving points[J].SystemsEngineeringandElectronics, 2013, 35(8): 1764-1768. (蘇志剛, 王爭, 吳仁彪. 面向移動(dòng)點(diǎn)的穩(wěn)健動(dòng)態(tài)Delaunay三角剖分技術(shù)[J].系統(tǒng)工程與電子技術(shù), 2013, 35(8): 1764-1768.)

[10] Rubin N. On kinetic Delaunay triangulations: a near quadratic bound for unit speed motions[C]∥Proc.oftheIEEE54thAnnualSymposiumonFoundationsofComputerScience, 2013, 519-528.

[11] Zhou Y, Sun F, Wang W, et al. Fast updating of Delaunay triangulation of moving points by bi-cell filtering[J].ComputerGraphicsForums, 2010, 29(7): 2233-2242.

[12] Machado P, Castro M, Tournois J, et al. Filtering relocations on a Delaunay triangulation[J].ComputerGraphicsForums, 2009, 28(5): 1465-1474.

[13] Zhou Y F, Sun F, Wang W P, et al. A new algorithm for fast updating Delaunay triangulation of moving points based on local fixing[J].JournalofComputer-AidedDesign&ComputerGraphics,2011,23(12):2006-2012.(周元峰,孫峰,王文平,等. 基于局部修復(fù)的移動(dòng)數(shù)據(jù)點(diǎn)Delaunay三角化快速更新方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2011,23(12):2006-2012.)

[14] Kolingerová I, ?alik B. Improvements to randomized incremental Delaunay insertion[J].ComputersandGraphics, 2002, 26(3): 477-490.

[15] Guibas L, Russel D. An empirical comparison of techniques for updating Delaunay triangulations[C]∥Proc.ofthe20thAnnualSymposiumonComputationalGeometry, 2004：170-179.

[16] Devillers O. On deletion in Delaunay triangulation[C]∥Proc.ofthe15thAnnualACMSymposiumonComputationalGeometry, 1999: 181-188.

[17] Rubin N. On topological changes in the Delaunay triangulation of moving points[J].Discrete&ComputationalGeometry, 2013, 49(4) : 710-746.

蘇志剛(1972-),男,教授,博士,主要研究方向?yàn)槔走_(dá)信號(hào)處理、陣列信號(hào)處理、空中交通管理、信息融合。

E-mail:ssrsu@vip.sina.com

符笑嫻(1990-),女,碩士研究生,主要研究方向?yàn)榭罩薪煌ü芾怼_突檢測。

E-mail:fuxiaoxian1990@163.com

郝敬堂(1989-),男,助理實(shí)驗(yàn)員,碩士,主要研究方向?yàn)榭罩薪煌ü芾怼⒖展苣繕?biāo)仿真、空管中間件。

E-mail:liuzhijingquan1989@126.com

Dynamic triangulation based method for screening potential conflicts

SU Zhi-gang1,2, FU Xiao-xian1,3, HAO Jing-tang1

(1.Sino-EuropeanInstituteofAviationEngineering,CivilAviationUniversityofChina,Tianjin300300,China;2.TianjinKeyLaboratoryforAdvancedSignalProcessing,CivilAviationUniversityofChina,Tianjin300300,China; 3.FujianGeneralAviationIndustryCompanyLimited,Fuzhou350000,China)

Abstract:Focusing on the difficulty that the dynamic delaunay triangulation (DDT) method could not stably realize local updating for the inverted triangle produced in the airspace triangulation, a modified method is proposed to replace the local updating for the inverted triangle with two local updatings in sequence in cases of point deletion and point insertion. Experimental results show that the number of potential conflict aircrafts using the modified DDT is independent with the aircraft density in airspace, and the modified DDT method has much lower time complexity of local updating. Modified DDT is more robust and more suitable for screening the potential conflict aircrafts in the air traffic control automation system.

Keywords:air traffic management; conflict detection; dynamic delaunay triangulation (DDT); moving point set; dynamic updating

收稿日期：2015-02-15；修回日期：2015-12-16；網(wǎng)絡(luò)優(yōu)先出版日期：2016-03-22。

基金項(xiàng)目：國家科技支撐計(jì)劃 (2011BAH24B12)；中央高校基本科技業(yè)務(wù)費(fèi)中國民航大學(xué)專項(xiàng)項(xiàng)目(3122014H003)資助課題

中圖分類號(hào)：TP 302

文獻(xiàn)標(biāo)志碼：A

DOI:10.3969/j.issn.1001-506X.2016.06.36

作者簡介：

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160322.1650.010.html