潘 偉，謝新連，李 猛

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

0 引 言

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

在海事安全領域，對于船舶越界研究相對較少。但如果將船抽象為點，區(qū)域抽象為多邊形，那么問題則轉化為多邊形的點包容性檢測問題，該問題早在上個世紀便開始研究。早期學者主要針對多邊形、多面體、流體等形式進行包容性檢測的可行性進行了研究[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ù)融合后的船位信息，并將船位誤差轉化到多邊形邊界中，將問題轉化為多邊形的點包容性檢測問題；再結合水上交通實時監(jiān)控對運算效率的需要，通過旋轉區(qū)域模型以及射線法判定條件對射線法進一步優(yōu)化，以提高求解數(shù)學模型的運算效率。

1 數(shù)學建模

檢測工程船與交通管制區(qū)域存在包含關系，需要對工程船船位與交通管制區(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°時，轉化公式為：

(1)

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

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

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

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

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

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

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

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

l0:y=ax+b

(2)

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

(3)

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

點P(如圖3)在直線l上側，將點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上側。結合P(x0,y0)在多邊形A1B1C1D1上側(圖3)可知，原圓形區(qū)域內(nèi)任何一點均在多邊形A1B1C1D1上側。同理可證點在多邊形下側的情形。

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

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

2 算法優(yōu)化

采用射線法求解筆者建立的模型。射線法的基本原理為：若要判斷點P是否包含在多邊形中，需從點P引出一條射線，射線與多邊形邊界的交點個數(shù)為奇數(shù)則點P在多邊形內(nèi)，交點個數(shù)為偶數(shù)則點P在多邊形外，射線方向不影響算法檢測結果。在實際運算中，發(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)質資源服務的網(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平行。

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

圖6 區(qū)域旋轉示意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的情況較為特殊，結合各區(qū)段采用閉區(qū)間的要求，Q5既屬于區(qū)段Ⅴ，又屬于區(qū)段Ⅵ，為保持每區(qū)段邊界的個數(shù)為偶數(shù)，交點為頂點Q5的類似情況不計入任何區(qū)段的交點個數(shù)中，設置判定條件：①當需要判定的點所引出的射線經(jīng)過某邊界點，且該邊界點不為穿越該區(qū)段的邊界點時，該點不計入射線穿越邊界個數(shù)；②當需要判定的點所引出的射線與邊界共線時，統(tǒng)計射線穿過共線邊界的端點個數(shù)即可；③若所需判定的點為垂向線段端點(即多邊形的頂點)，判定其在多邊形內(nèi)。

圖7 點與特殊邊界的關系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中時，僅需要判斷射線起點(船位)與兩個邊界的關系，以兩條邊界為例，如式(7)：

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

(7)

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

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

(8)

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

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

(9)

將該結論推廣到一個區(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次實驗，結果如圖10。

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

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

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 結 論

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

1)實驗結果表明優(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)完成船位越界檢測任務。