潘 偉，謝新連，李 猛

(大連海事大學(xué) 綜合運(yùn)輸研究所，遼寧 大連116026)

0 引 言

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

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

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

1 數(shù)學(xué)建模

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

1.1 船位信息

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

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

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

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

(1)

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

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

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

以矩形交通管制區(qū)域?yàn)槔瑢^(qū)域與船位進(jìn)行數(shù)學(xué)建模后如圖3(a)，交通管制區(qū)域?yàn)榫匦蜛1B1C1D1，真實(shí)船位在以點(diǎn)P為中心，δmax為半徑的圓形區(qū)域中。若以此模型進(jìn)行檢測，是多邊形的多邊形包容性檢測問題，檢測方法比多邊形的點(diǎn)包容性檢測問題復(fù)雜。為降低算法復(fù)雜度，需將模型從多邊形的多邊形包容性檢測問題，轉(zhuǎn)化為多邊形的點(diǎ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，船位則直接采用點(diǎn)P表示。

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

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

l0:y=ax+b

(2)

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

(3)

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

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

(4)

由于a=tanα，有：

(5)

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

(6)

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

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

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

2 算法優(yōu)化

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

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

為提升求解速度，射線法在求解過程中普遍會(huì)設(shè)定射線方向。采用垂直于坐標(biāo)軸的射線(簡稱垂向射線)，當(dāng)確定點(diǎn)的橫坐標(biāo)在多邊形各個(gè)邊界表達(dá)式的定義域外時(shí)，可判定點(diǎn)在多邊形外。在判斷點(diǎn)所在的子區(qū)域時(shí)，垂向射線法可以降低運(yùn)算維度。

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

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

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

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

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

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

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

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

2.2 包容性檢測判定條件設(shè)置

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

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

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

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

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

(7)

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

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

(8)

式中：xp,yp為P點(diǎn)坐標(biāo)值。

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

(9)

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

(10)

2.3 算法流程

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

3 算例分析

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

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

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

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

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

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

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

圖10 4種算法運(yùn)行時(shí)間比較Fig. 10 Comparison of running time of four kinds of algorithms

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

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

4 結(jié) 論

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

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

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

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