基于點包容性檢測的工程船越界檢測算法 *

潘 偉，謝新連，李 猛

(大連海事大學 綜合運輸研究所，遼寧 大連116026)

0 引 言

隨著海運事業(yè)的發(fā)展，人工航道逐漸增多，受自然因素的影響[1]，人工航道的水深不能長久滿足通航要求，致使一部分挖泥船定期在航道中進行疏浚作業(yè)[2]。在長江沿江地區(qū)經(jīng)濟高速發(fā)展的背景下，長江入?？诤降来笆置芗痆3]，加劇了通航船舶與疏浚工程船的碰撞危險，相關(guān)管理部門頒布了相應的航道管理辦法來保證航道的正常通航秩序[4]。針對從事疏浚的工程船與航行船舶之間的沖突問題，在通航密度大的時間段內(nèi)，疏浚工程船需讓出主航道，使航行船舶能夠根據(jù)管理部門安排有序通過。通過對工程船事故的調(diào)查發(fā)現(xiàn)，存在部分工程船為盡快完成施工要求，在交通管制時段內(nèi)違規(guī)作業(yè)，造成險情甚至嚴重的碰撞事故。為了減少該類險情的發(fā)生，在交通管制區(qū)域進行實時監(jiān)控，當有工程船違規(guī)進入交通管制區(qū)域時，會立刻被監(jiān)控中心識別，如果及時對其發(fā)出警告，有極大可能在構(gòu)成險情前使其退出交通管制區(qū)域。為實現(xiàn)工程船實時監(jiān)控，檢測工程船船位與交通管制區(qū)域的包含關(guān)系成為了核心問題。

在海事安全領域，對于船舶越界研究相對較少。但如果將船抽象為點，區(qū)域抽象為多邊形，那么問題則轉(zhuǎn)化為多邊形的點包容性檢測問題，該問題早在上個世紀便開始研究。早期學者主要針對多邊形、多面體、流體等形式進行包容性檢測的可行性進行了研究[5-7]。后期逐漸發(fā)展為優(yōu)化包容性檢測的效率以及適用范圍，提出了“密切邊”等新理論來提升包容性檢測效率[8-9]。此外還有學者通過對原始的多邊形、多面體等進行分解、排序來提升包容性檢測的效率[10-14]。為了充分利用現(xiàn)有軟件的運行效率，數(shù)據(jù)庫管理系統(tǒng)提供的優(yōu)化查詢機制也被用來計算包容性檢測問題[15]。

綜上，點包容性測試算法通過不斷優(yōu)化，已能滿足一定實際需求，可將點包容性檢測算法應用于交通管制區(qū)域內(nèi)工程船的實時監(jiān)控。首先對交通管制區(qū)域邊界和船位進行數(shù)學建模，為保證船位精度，采用雷達數(shù)據(jù)和AIS數(shù)據(jù)融合后的船位信息，并將船位誤差轉(zhuǎn)化到多邊形邊界中，將問題轉(zhuǎn)化為多邊形的點包容性檢測問題；再結(jié)合水上交通實時監(jiān)控對運算效率的需要，通過旋轉(zhuǎn)區(qū)域模型以及射線法判定條件對射線法進一步優(yōu)化，以提高求解數(shù)學模型的運算效率。

1 數(shù)學建模

檢測工程船與交通管制區(qū)域存在包含關(guān)系，需要對工程船船位與交通管制區(qū)域進行數(shù)學建模，通過模型求解來判斷工程船是否在交通管制區(qū)域內(nèi)。

1.1 船位信息

船舶航行信息的融合是航海領域的熱門研究方向，融合后的船舶航行數(shù)據(jù)兼具雷達與AIS數(shù)據(jù)的優(yōu)點，使獲得的船位信息更加可靠。船位誤差δ是不能夠被完全消除的，當獲取的船位為點P時，則船舶的真實船位在以點P為中心，最大誤差δmax為半徑的圓形區(qū)域中，如圖1。

圖1 真實船位可能存在的區(qū)域Fig. 1 The area where the true ship may exist

1.2 交通管制區(qū)域邊界

根據(jù)墨卡托投影原理，投影后的海圖從赤道向兩極存在緯度漸長率，當基準緯度采用0°時，轉(zhuǎn)化公式為：

(1)

式中：R為地球半徑；(λ,φ)為弧度制表示的經(jīng)緯度坐標；(x,y)為轉(zhuǎn)化后的均勻直角坐標系坐標；e為第一偏心率。

通過式(1)將海圖上確定航道邊界的點和船位坐標從經(jīng)緯度坐標轉(zhuǎn)化為均勻直角坐標，進行點包容性檢測。

圖2 采用外切直線段簡化弧形邊界Fig. 2 Simplify the arc boundary with tangent lines

以矩形交通管制區(qū)域為例，將區(qū)域與船位進行數(shù)學建模后如圖3(a)，交通管制區(qū)域為矩形A1B1C1D1，真實船位在以點P為中心，δmax為半徑的圓形區(qū)域中。若以此模型進行檢測，是多邊形的多邊形包容性檢測問題，檢測方法比多邊形的點包容性檢測問題復雜。為降低算法復雜度，需將模型從多邊形的多邊形包容性檢測問題，轉(zhuǎn)化為多邊形的點包容性檢測問題。需將船位誤差轉(zhuǎn)化到區(qū)域范圍誤差中，轉(zhuǎn)化后如圖3(b)。

圖3 修正前后的船位與交通管制區(qū)域Fig. 3 Ship position and traffic control area before and aftercorrection

圖3(b)中，將原船位誤差半徑δmax附加到區(qū)域范圍中，得到新的區(qū)域范圍為圓角矩形A2B2C2D2，船位則直接采用點P表示。

筆者認為轉(zhuǎn)化后的區(qū)域A2B2C2D2具有如下性質(zhì)：利用轉(zhuǎn)化后的區(qū)域A2B2C2D2進行點的多邊形包容性檢測時，當圓心點不在區(qū)域A2B2C2D2內(nèi)，可斷定原圓形區(qū)域內(nèi)的任何一點均不在原矩形區(qū)域A1B1C1D1內(nèi)。

對該性質(zhì)進行證明(以點在多邊形上側(cè)為例)：設以點P(x0,y0)為圓心，δmax為半徑的圓形區(qū)域，與多邊形A1B1C1D1的上側(cè)邊界無交點，與圓形區(qū)域距離最近的邊界直線l0如式(2)：

l0:y=ax+b

(2)

邊界直線l0在附加誤差半徑δmax后得到修正的邊界直線l，如式(3)：

(3)

式中：α為該邊界直線與x軸夾角。

點P(如圖3)在直線l上側(cè)，將點P的坐標帶入式(3)，點P位置有：

(4)

由于a=tanα，有：

(5)

a(x0+sinα×δmax)+b-(y0-cosα×δmax)<0

(6)

點P1(x0+sinα×δmax,y0-cosα×δmax)為原圓形區(qū)域下半邊界距邊界直線l0最近的點，且在直線l0上側(cè)。結(jié)合P(x0,y0)在多邊形A1B1C1D1上側(cè)(圖3)可知，原圓形區(qū)域內(nèi)任何一點均在多邊形A1B1C1D1上側(cè)。同理可證點在多邊形下側(cè)的情形。

在實際計算過程中發(fā)現(xiàn)，圓角矩形的形式增加了計算復雜程度，不利于提高檢驗效率，因此對圓角矩形進行進一步簡化，采用矩形形式進行檢測，如圖3(c)。從警報范圍來看，簡化后矩形區(qū)域包含圓角矩形區(qū)域，對于增補的4個角的面積，從理論上看會造成誤報警，但其面積占整體區(qū)域比例小，且能大幅提高算法效率，可認為增補具有意義。

綜上，轉(zhuǎn)化后的數(shù)學模型為多邊形的點包容性問題，求解運算復雜程度大幅降低。

2 算法優(yōu)化

采用射線法求解筆者建立的模型。射線法的基本原理為：若要判斷點P是否包含在多邊形中，需從點P引出一條射線，射線與多邊形邊界的交點個數(shù)為奇數(shù)則點P在多邊形內(nèi)，交點個數(shù)為偶數(shù)則點P在多邊形外，射線方向不影響算法檢測結(jié)果。在實際運算中，發(fā)現(xiàn)射線法的檢測時間會隨船舶數(shù)量和交通管制區(qū)域邊界頂點數(shù)量增多明顯增長，無法滿足實時監(jiān)測需求，需對射線法進行優(yōu)化。

2.1 多邊形分區(qū)優(yōu)化與射線方向設置

為提升求解速度，射線法在求解過程中普遍會設定射線方向。采用垂直于坐標軸的射線(簡稱垂向射線)，當確定點的橫坐標在多邊形各個邊界表達式的定義域外時，可判定點在多邊形外。在判斷點所在的子區(qū)域時，垂向射線法可以降低運算維度。

假設某區(qū)域如圖4，進行建模后獲得多邊形Q1Q2Q3Q4Q5Q6Q7Q8Q9Q10Q11，各邊的函數(shù)表達式集合為{Fi|i=1,2,…,11}，存在6個需要檢測的點為{P1,P2,P3,P4,P5,P6}。

高校圖書館員牢固樹立“互聯(lián)網(wǎng)+”思維，實現(xiàn)圖書館服務創(chuàng)新，將圖書館建設成匯聚優(yōu)質(zhì)資源服務的網(wǎng)絡平臺、教學資源可持續(xù)建設和運營平臺，服務于高校師生的發(fā)展,以實際行動積極推動圖書管理信息化建設。

圖4 根據(jù)x值將區(qū)域分段Fig. 4 Segment the region according to the x value

獲取多邊形各頂點的橫坐標值為集合{x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11}，將頂點的x坐標按數(shù)值升序排序并獲得一個序列x11,x1,x10,x2,x3,x9,x6,x4,x5,x7,x8。根據(jù)實際情況，工程船在交通管制區(qū)域的邊界上同樣具有碰撞危險，因此區(qū)域的x值的取值范圍為[x11,x8]。當檢驗點P的橫坐標不在[x11,x8]中，則立刻可以判定點P不在多邊形區(qū)域內(nèi)。將序列去重后得：x11,x1,x10,x2,x3,x6,x4,x7,x8，區(qū)域[x11,x8]被分為8個子區(qū)域(圖4)，虛線將多邊形分為8個區(qū)段，采用羅馬數(shù)字為區(qū)段編號，各區(qū)段的x坐標范圍為{DⅠ,DⅡ,…,DⅧ}。

圖5 平行邊界與輔助線示意Fig. 5 Schematic diagram of parallel boundary and auxiliary line

根據(jù)通航水域警戒區(qū)與監(jiān)控區(qū)域邊界設置的實際情況，監(jiān)控區(qū)域中存在一定量的平行元素(包括邊界和與邊界平行的輔助連線)，如圖5。圖5中虛線Q2Q10、Q6Q9、Q3Q9為輔助線。邊界Q1Q11、Q7Q8與輔助線Q2Q10、Q6Q9平行，邊界Q4Q5與輔助線Q3Q9平行。

結(jié)合分區(qū)原則，對區(qū)域繞指定點進行二維旋轉(zhuǎn)。求得區(qū)域每個頂點與其他頂點的連線斜率，獲得斜率集合Sl。求集合眾數(shù)Ml，其對應的直線與y軸之間的銳夾角即為旋轉(zhuǎn)角β。如圖6，將原區(qū)域繞點G旋轉(zhuǎn)度，獲得新的區(qū)域位置，該區(qū)域由8個區(qū)段減少到6個區(qū)段。

圖6 區(qū)域旋轉(zhuǎn)示意Fig. 6 Schematic diagram of regional rotation

2.2 包容性檢測判定條件設置

基于船舶航行以及監(jiān)控實際需求，考慮船舶在邊界上同樣存在碰撞風險，需要對射線法的判定條件進行進一步優(yōu)化。以在區(qū)段Ⅵ檢測為例(圖7)，線段Q6Q7在區(qū)段Ⅵ中的部分為Q′6Q7，線段Q8Q9在區(qū)段Ⅵ中的部分為Q8Q′9，點P1、P2、P3、P4為4個檢測點。點P1引出向上的垂向射線與邊界有一個交點，點P3引出向上的垂向射線與邊界有0個交點，均符合射線法的判斷準則。點P2、P4情況較為復雜，由點P2引出向上的垂向射線穿過多邊形兩條邊界Q′6Q7、Q8Q′9及一個頂點Q5。經(jīng)過頂點Q5的情況較為特殊，結(jié)合各區(qū)段采用閉區(qū)間的要求，Q5既屬于區(qū)段Ⅴ，又屬于區(qū)段Ⅵ，為保持每區(qū)段邊界的個數(shù)為偶數(shù)，交點為頂點Q5的類似情況不計入任何區(qū)段的交點個數(shù)中，設置判定條件：①當需要判定的點所引出的射線經(jīng)過某邊界點，且該邊界點不為穿越該區(qū)段的邊界點時，該點不計入射線穿越邊界個數(shù)；②當需要判定的點所引出的射線與邊界共線時，統(tǒng)計射線穿過共線邊界的端點個數(shù)即可；③若所需判定的點為垂向線段端點(即多邊形的頂點)，判定其在多邊形內(nèi)。

圖7 點與特殊邊界的關(guān)系Fig. 7 The relationship between points and special boundaries

設定判定條件后點P2引出的垂向射線與多邊形的交點個數(shù)為2個，判定點P2在多邊形外；點P4引出的垂向射線與多邊形交點個數(shù)為1個，判定點P4在多邊形內(nèi)，與實際相符且符合射線法的判斷準則。

通過設置判定條件，確定了每一個區(qū)段內(nèi)邊界的數(shù)量均為偶數(shù)。根據(jù)射線法的判斷準則，統(tǒng)計射線穿過邊界的次數(shù)。當射線起點的x值在第i區(qū)段的區(qū)間范圍Di中時，僅需要判斷射線起點(船位)與兩個邊界的關(guān)系，以兩條邊界為例，如式(7)：

Ti(x,y)=aix+bi-y

(7)

式中：Ti(x,y)為點與直線的關(guān)系判別函數(shù);i=1,2;ai與bi為直線參數(shù),i=1,2。

利用T(x,y)判斷點P(xP,yp)與邊界關(guān)系并滿足：

(8)

式中：xp,yp為P點坐標值。

若點在兩條邊界直線的同一側(cè)，表示點在多邊形外，其他情況均表示點在多邊形內(nèi)(點在多邊形邊界上算作在多邊形內(nèi))，則可歸納出：

(9)

將該結(jié)論推廣到一個區(qū)段內(nèi)存在兩條以上邊界的情況。區(qū)段內(nèi)邊界數(shù)量為偶數(shù)k，則判定表達式為：

(10)

2.3 算法流程

將優(yōu)化部分整合，完成優(yōu)化射線法的整體設計，包括3大部分：獲得數(shù)據(jù)、區(qū)域模型處理、算法檢驗。算法流程如圖8。

3 算例分析

為了檢驗優(yōu)化后的射線法(下簡稱優(yōu)化射線法)有效性，選取吳淞口附近的一個警戒區(qū)進行算例分析，如圖9。

為了體現(xiàn)優(yōu)化射線法的優(yōu)越性，采用角度和法、傳統(tǒng)射線法、垂向射線法、優(yōu)化射線法共4種算法同時對相同環(huán)境數(shù)據(jù)進行檢驗。前3種算法計算流程見文獻[20]，傳統(tǒng)射線法采用斜率為1的射線進行算法檢驗；垂向射線法采用垂直于x軸并向x軸正方向延長的射線進行檢驗。4種算法均采用C++ 語言編寫實現(xiàn)，運行主機CPU為i7 5700HQ，內(nèi)存為32 GB，操作系統(tǒng)為Windows 7。

圖8 算法流程Fig. 8 Algorithm flow chart

將吳淞口水域附近選定的監(jiān)控區(qū)域進行數(shù)字化，獲得邊界坐標，并選擇大于邊界的范圍作為實驗區(qū)域。為方便獲取算法運行時間，在實驗區(qū)域內(nèi)隨機生成10萬個點，為能夠有效比較4種算法的運行效率，用4種算法檢驗同一組隨機點，進行100次實驗，結(jié)果如圖10。

圖9 吳淞口警戒區(qū)及航道Fig. 9 Precautionary area and channel of Wusongkou

對圖10進行分析，可以得到以下結(jié)論：

1)角度和法、傳統(tǒng)射線法、垂向射線法、優(yōu)化射線法4種算法均具有良好的穩(wěn)定性，在實驗環(huán)境一定的情況下，射線法相比于角度和法更加穩(wěn)定。

圖10 4種算法運行時間比較Fig. 10 Comparison of running time of four kinds of algorithms

2)優(yōu)化射線法相比于垂向傳統(tǒng)射線法運行效率提升約25.68%；優(yōu)化射線法相比于傳統(tǒng)射線法運行效率提升約35.51%。

3)射線法在優(yōu)化過程中，運行效率有大幅提升，其穩(wěn)定性與傳統(tǒng)射線法、垂向傳統(tǒng)射線法相近，可通過并發(fā)方式進一步提高算法穩(wěn)定性。

4 結(jié) 論

根據(jù)對工程船實際監(jiān)控需要，采用點包容性測試算法來解決通航水域施工船越界檢測問題。對算法進行應用時發(fā)現(xiàn)，不同包容性檢測算法的應用范圍存在較大的差異，導致不同算法解決同樣問題時運算效率不同。針對需要監(jiān)控的通航水域特點，創(chuàng)新采用了多邊形分區(qū)與射線方向相結(jié)合的優(yōu)化方法，使其在解決工程船越界檢測問題時具有更高的運算效率，并獲得以下結(jié)論：

1)實驗結(jié)果表明優(yōu)化射線法在運算效率方面有了較大幅度的提升，與固定斜率的射線法(斜率不為0)相比運行效率提升約35.51%，與垂直設置射線的射線法相比運行效率提升約25.68%。并且在處理復雜多邊形區(qū)域時能保持高效率運算。

2)從實際應用角度來看，在無法降低獲取船位報文與解碼時間的情況下，大幅提高檢測算法的運算效率是保證檢測系統(tǒng)在規(guī)定時間內(nèi)完成檢測任務的有效方式。

3)改進后的算法可以推廣到不同的監(jiān)控環(huán)境中，例如禁航區(qū)的船舶監(jiān)控、錨地船舶監(jiān)控、施工水域船舶監(jiān)控等。尤其是針對通航密集的水域進行船舶檢測，改進后算法的高效性和穩(wěn)定性可以幫助監(jiān)控系統(tǒng)在規(guī)定時間內(nèi)完成船位越界檢測任務。