魏榮灝，李京兵，史永忠

（浙江省河海測(cè)繪院，浙江 杭州 310008）

1 問(wèn)題的提出

在海洋測(cè)繪工作中，采用驗(yàn)潮方法對(duì)大范圍海域進(jìn)行小比例尺測(cè)繪時(shí)，使用單潮位站進(jìn)行水位改正的方法難以滿足技術(shù)規(guī)范［1］的要求，必須進(jìn)行分帶潮位內(nèi)插；采用多波束測(cè)深系統(tǒng)進(jìn)行大比例尺測(cè)量時(shí)，為了保證測(cè)區(qū)數(shù)據(jù)全覆蓋，獲取數(shù)據(jù)常常會(huì)超出測(cè)量范圍；另外，大部分多波束后處理軟件常以矩形為單元處理數(shù)據(jù)，處理結(jié)果導(dǎo)出后往往與實(shí)際復(fù)雜的測(cè)區(qū)形狀不同，測(cè)區(qū)外部經(jīng)常存在多余數(shù)據(jù)，因此，必須對(duì)測(cè)區(qū)內(nèi)外的數(shù)據(jù)進(jìn)行篩選。采用人工方式操作時(shí)，不但費(fèi)事費(fèi)力，還容易出現(xiàn)錯(cuò)漏，需要反復(fù)操作，比較枯燥。若采用計(jì)算機(jī)自動(dòng)處理，主要工作在于判別測(cè)點(diǎn)數(shù)據(jù)與測(cè)區(qū)的相對(duì)關(guān)系，即判斷點(diǎn)與多邊形的相對(duì)關(guān)系。

判斷點(diǎn)在多邊形內(nèi)或外是一個(gè)基本卻又非常重要的問(wèn)題，在計(jì)算幾何、計(jì)算機(jī)圖形學(xué)、模式識(shí)別和地理信息系統(tǒng)中有大量的應(yīng)用。為解決該問(wèn)題，國(guó)內(nèi)外眾多學(xué)者已經(jīng)進(jìn)行了大量的研究，提出的算法主要可以分為2類(lèi)：奇偶法 （射線法）［2－4］和非零環(huán)繞數(shù)法 （轉(zhuǎn)角法）［2，5，6］。如果多邊形是簡(jiǎn)單的 （沒(méi)有自相交點(diǎn)），那么2個(gè)算法都可以給出相同的結(jié)果；但對(duì)于非簡(jiǎn)單多邊形，轉(zhuǎn)角法則有很高的精度。傳統(tǒng)觀點(diǎn)認(rèn)為射線法的效率較高，轉(zhuǎn)角法的速度較慢。

本文主要針對(duì)實(shí)際工作中需要判別點(diǎn)與任意多邊形的關(guān)系，特別是存在自相交與帶島等特例的情況，研究利用改進(jìn)的轉(zhuǎn)角法判別點(diǎn)與多邊形的相對(duì)關(guān)系，實(shí)現(xiàn)算法并應(yīng)用于實(shí)踐。

2 轉(zhuǎn)角法及其改進(jìn)模型

2.1 轉(zhuǎn)角法

轉(zhuǎn)角法是對(duì)角度的積分算法［7］。為了使其具有普遍性，定義在二維平面中某個(gè)封閉曲線關(guān)于某點(diǎn)的環(huán)繞數(shù)wn。令C（u）＝ （x（u），y（u）），0≤u≤1且C（0）＝C（1），是二維連續(xù)曲線，點(diǎn)P為不在C（u）上的點(diǎn)。令CP（u）＝C（u）－P為從點(diǎn)P到C（u）的矢量，且其單位方向矢量為W（u）＝CP（u）／｜CP（u）｜。則該式定義了一個(gè)連續(xù)的從曲線C到單位圓S1的映射，且 W（u）可以表示為 W（u）＝ （cos（u），sin（u））。式中：（u）是正的逆時(shí)針?lè)较虻慕?。環(huán)繞數(shù)就等于W（u）環(huán)繞S1的次數(shù)的整數(shù)部分，可用式（1）表示：

在處理任意點(diǎn)P與由頂點(diǎn)V1，V2，……，VN＝V0構(gòu)成的多邊形相對(duì)關(guān)系時(shí)，積分可以簡(jiǎn)化為計(jì)算帶符號(hào)的角度的總和，這些角為PVi與PVi＋1的夾角。若i＝angle（PVi，PVi＋1），則有：

當(dāng)代數(shù)和為0，則點(diǎn)P在多邊形的外部，否則，點(diǎn)在多邊形的內(nèi)部或邊界上。

2.2 改進(jìn)的轉(zhuǎn)角法

由于轉(zhuǎn)角法中使用了非常耗時(shí)的arccos函數(shù)，故效率不高，改進(jìn)的轉(zhuǎn)角法可以克服該缺點(diǎn)。在S1中任取一點(diǎn)Q。由于曲線W （u）環(huán)繞，則其可能多次經(jīng)過(guò)Q點(diǎn)。當(dāng)W（u）按逆時(shí)針?lè)较蚪?jīng)過(guò)Q點(diǎn)時(shí)，記為＋1次；順時(shí)針則記為－1次，則次數(shù)總和就是W環(huán)繞S1的次數(shù)，正好等于環(huán)繞數(shù)wn。以被檢測(cè)點(diǎn)P為端點(diǎn)向Q方向延伸做一條射線R，則R穿越C的交點(diǎn)與W經(jīng)過(guò)Q的點(diǎn)是一一對(duì)應(yīng)的。當(dāng)R從C的右邊跨到左邊時(shí)，該穿越數(shù)為正，記為＋1；反之為負(fù)，記為－1。當(dāng)曲線C退化為多邊形時(shí)，算法只需要對(duì)多邊形C的每一條邊做一次判斷。對(duì)所有的邊測(cè)試完后，將所有的穿越值加起來(lái)就是環(huán)繞數(shù)wn了。當(dāng)wn為0時(shí)，點(diǎn)在多邊形外；否則在多邊形內(nèi)［7］。

3 算法實(shí)現(xiàn)

改進(jìn)的轉(zhuǎn)角法不但具有與射線法相同的效率，且更加精確［7］。實(shí)現(xiàn)該算法的問(wèn)題主要有2個(gè)，一是射線的穿越數(shù)正負(fù)判別，二是射線的選取。在討論完這2個(gè)問(wèn)題后，將算法進(jìn)行具體實(shí)現(xiàn)，并與人工處理結(jié)果進(jìn)行驗(yàn)證。

3.1 穿越數(shù)符號(hào)判別

判別穿越數(shù)的正負(fù)號(hào)時(shí)，可以通過(guò)曲線C的一個(gè)法線矢量與方向適量Q的數(shù)量積的符號(hào)來(lái)判斷。當(dāng)曲線C退化為多邊形時(shí)，只需要對(duì)C的每一條邊做一次判斷。

在實(shí)際判別過(guò)程中，不需要計(jì)算射線與邊的交點(diǎn)，只需要判別點(diǎn)P是否在邊的左邊。對(duì)于方向向上與方向向下的邊的判別與是否在左邊的規(guī)則不同。對(duì)于方向向上的邊，如果穿越射線到達(dá)P的右邊，則P在邊ViVi＋1的左邊 （見(jiàn)圖1）；對(duì)于方向向下的邊，若穿越射線的正方向，則P在邊 ViVi＋1的右邊 （見(jiàn)圖2）。

圖1 方向向上的邊判別圖

圖2 方向向下的邊判別圖

3.2 射線選取

為了減少程序的計(jì)算量，常選取為一條向點(diǎn)P右邊延伸且平行于X軸的射線。利用這條射線可以很容易地判別是否與多邊形的邊有交點(diǎn)。為了計(jì)算環(huán)繞數(shù)，算法簡(jiǎn)單地遍歷多邊形的所有邊，測(cè)試是否穿越邊及與穿越邊的相對(duì)關(guān)系 （左右側(cè)），最后將環(huán)繞數(shù)求和，便可判斷其對(duì)應(yīng)關(guān)系。

3.3 算法實(shí)現(xiàn)

根據(jù)2.2節(jié)的改進(jìn)算法，編制程序進(jìn)行具體實(shí)現(xiàn)。判別點(diǎn)與多邊形的相對(duì)關(guān)系時(shí)，為了提升程序的處理效率，在讀取多邊形的各條邊的坐標(biāo)數(shù)據(jù)后，先生成一個(gè)涵蓋該多邊形的最小矩形范圍，然后再依次計(jì)算并保存多邊形各條邊的相關(guān)參數(shù)，降低程序計(jì)算量。在判別點(diǎn)與多邊形的相對(duì)關(guān)系時(shí)，首先判別點(diǎn)是否處于最小矩形范圍內(nèi)，如果點(diǎn)不在該范圍內(nèi)，則不可能落在多邊形內(nèi)，可直接排除；利用2.2節(jié)算法，依次判別各個(gè)數(shù)據(jù)點(diǎn)與多邊形各條邊的相對(duì)關(guān)系，計(jì)算點(diǎn)的環(huán)繞數(shù)。若環(huán)繞數(shù)等于0，則該點(diǎn)在多邊形的外部；否則，該點(diǎn)在多邊形的內(nèi)部，并對(duì)其進(jìn)行標(biāo)記。處理完所有的數(shù)據(jù)后，將結(jié)果保存到文件中。

3.4 算例驗(yàn)證

為了驗(yàn)證程序的正確性，采用象山港某航道1∶500的多波束測(cè)量數(shù)據(jù)進(jìn)行測(cè)試。測(cè)試區(qū)域分為2個(gè)部分，第一部分為四邊形，第二部分?jǐn)?shù)據(jù)為任意多邊形，其中數(shù)據(jù)格網(wǎng)間距為4m，共有425301個(gè)。如果采用人工方式在AutoCAD中進(jìn)行篩選，由于數(shù)據(jù)量大、導(dǎo)入時(shí)耗時(shí)長(zhǎng)、操作效率低，容易產(chǎn)生錯(cuò)漏。采用程序處理時(shí)，只需按照給定的格式分別編輯多邊形角點(diǎn)坐標(biāo)及測(cè)點(diǎn)數(shù)據(jù)，便可以得到篩選后的結(jié)果。分別將采用人工方式和程序自動(dòng)篩選的數(shù)據(jù)放在一起進(jìn)行比較，兩者之間的結(jié)果基本一致，采用程序進(jìn)行處理效率較高。

4 結(jié) 語(yǔ)

本文通過(guò)分析點(diǎn)與多邊形的相對(duì)關(guān)系，研究利用改進(jìn)的轉(zhuǎn)角法對(duì)地形數(shù)據(jù)進(jìn)行篩選，使用該方法不但精度高，而且效率高，有效提高了作業(yè)效率。但是，目前該方法主要針對(duì)測(cè)區(qū)可以由多邊形進(jìn)行定義的情況，若測(cè)區(qū)邊界存在圓弧等情況，則只能采用逼近或者人工局部干預(yù)的方法。為使算法滿足更多情況，則需要繼續(xù)研究。

［1］中交天津航道局有限公司，中交天津港航勘察設(shè)計(jì)研究院有限公司.JTS 131—2012水運(yùn)工程測(cè)量規(guī)范 ［S］.北京：人民交通出版社，2012.

［2］Franco P.Preparata，Michael Ian Shamos.Computational Geometry：An Introduction ［M］.New York：Springer－Verlag，1985.

［3］周培德.判定點(diǎn)是否在多邊形內(nèi)部的算法 ［J］.北京理工大學(xué)學(xué)報(bào)，1995，15 （4）：437－440.

［4］張寧寧，張樹(shù)有，譚建榮.映射相關(guān)邊概念的多邊形內(nèi)外點(diǎn)判別算法 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16（7）：935－938.

［5］沈陳華.平面上點(diǎn)與多邊形包含關(guān)系的Q算法 ［J］.揚(yáng)州大學(xué)學(xué)報(bào)，1999，2 （4）：24－26.

［6］董秀山，劉潤(rùn)濤.判別點(diǎn)與簡(jiǎn)單多變性位置關(guān)系的新算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 （2）：185－186.

［7］張宏，溫永寧，劉愛(ài)利.地理信息系統(tǒng)算法基礎(chǔ) ［M］.北京：科學(xué)出版社，2006.