陳金林，劉謝進(jìn)，李寧

(淮南師范學(xué)院 數(shù)學(xué)與計算科學(xué)系,安徽 淮南 232038)

引言

在計算幾何、計算機(jī)圖形學(xué)等領(lǐng)域常用簡單多邊形來描述幾何形體，很多情況下運(yùn)算處理的對象是簡單平面多邊形[1]。判別多邊形是否為簡單多邊形以及簡單多邊形內(nèi)外點的判別算法就很重要，因為這些算法是許多算法的基礎(chǔ)[2]。迄今為止，對判斷點與多邊形位置關(guān)系算法的研究比較多。經(jīng)典的算法有叉積判斷法[3]，射線法[4，5]，有向三角形面積之和的符號法[6]，有向回路法和網(wǎng)格法[7]等。其中叉積法只適用于凸多邊形，并且對所有邊都需叉積運(yùn)算，運(yùn)算量大。文獻(xiàn)[8]所涉及到有向回路法本質(zhì)上是非零環(huán)繞數(shù)規(guī)則法，但它只適用于凸多邊形，空間復(fù)雜度較大，本質(zhì)上是一種以空間換取時間的算法。射線法通常需要求交點，雖然在文獻(xiàn)[8]對射線法進(jìn)行了改進(jìn)，但也只是減少求交點數(shù)量。在文獻(xiàn)[9]中所提及的射線法不需要求交點，但對關(guān)聯(lián)集合求解判別增加了空間復(fù)雜度。

點與相關(guān)邊的判別法[10-14]是掃描與點關(guān)聯(lián)性（密切邊[11]、單調(diào)性[12]）最大的邊，在多邊形中這樣的邊可能不唯一，判別測試點與此相關(guān)邊的位置關(guān)系，確定點與多邊形的位置關(guān)系。此類算法計算速度快，穩(wěn)定性高，但是查找到的相關(guān)的邊通常不唯一。本文提出了基于點與角的最短距離的一種新的方法，掃描與點距離最小時關(guān)聯(lián)的邊，這樣的邊在多邊形中可能不止一個，但掃描過程結(jié)束后只保留一個作為判斷依據(jù)，在多邊形中，有兩個角共有這條邊。選擇其中任意一個角，判別點與這個角的內(nèi)外位置關(guān)系，確定點與多邊形的位置關(guān)系。

1 算法理論基礎(chǔ)

1.1 角的正負(fù)側(cè)

定義多邊形中具有相同頂點的邊稱為相鄰的邊，如Pi-1Pi與PiPi+1是兩條相鄰的邊，若多邊形中不相鄰的邊不相交，則稱該多邊形為簡單多邊形。

由線段Pi-1Pi與PiPi+1線段所形成的角為∠Pi-1PiPi+1，如圖1。

圖1 多邊形角

一個簡單多邊形，如果多邊形上的點按逆時針排列，那么多邊形每條線段的正側(cè)有一部分包含在多邊形的內(nèi)部，而且相鄰的兩個線段的正側(cè)區(qū)域有公共部分，這個共同的正側(cè)區(qū)域必有包含在多邊形內(nèi)部的部分。相鄰兩條線段共同的正側(cè)或負(fù)側(cè)，用于判斷多邊形的內(nèi)外側(cè)。有如下定義。

規(guī)定角∠Pi-1PiPi+1的正負(fù)側(cè)，當(dāng)人按Pi-1→Pi→Pi+1方向行走時，始終保持在人左（右）手區(qū)域為角∠Pi-1PiPi+1正（負(fù)）側(cè)，否則為負(fù)（正）側(cè)。如圖2所示。

圖2 角的內(nèi)外側(cè)(a)、(b)

以此定義，測試點P在角∠Pi-1PiPi+1的正負(fù)側(cè)可以按以下的規(guī)則判斷。

有向線段PiPi+1與有向線段相交于P，則交點Pi相對于Pi-1Pi的特征值為λ，如圖2(a)中λ=1，b中λ=-1。

點P到有向線段PiPi+1、Pi-1Pi所在直線的距離分別為Di，Di-1。

①若λ=-1時，Di〉0，Di-1〉0同時成立，那么P在角∠Pi-1PiPi+1的正側(cè)，否則在其負(fù)側(cè)，如圖2（b）。

②若λ=1時，Di〈0，Di-1〈0同時成立，那么P在角∠Pi-1PiPi+1的負(fù)側(cè)，否則在其正側(cè)，如圖2（a）。

角的正側(cè)區(qū)域有一部分包含在多邊形的內(nèi)部。若點在這一部分區(qū)域內(nèi)，即點在多邊形的內(nèi)部。

1.2 點到角的距離

過測試點P作有向線段PiPi+1所在直線l的垂線，垂線與直線l交點Pv為垂足，也稱為P在直線l上的投影，垂足Pv與P的距離為點P到直線l的距離。P到有向線段PiPi+1距離可定義為：

定義：P到線段PiPi+1所有點距離最小值稱為P到線段PiPi+1距離。如下圖3所示：

圖3 點到線段距離

通過以上的定義，可以通過以下方法求點到線段的距離。

由上面的點到線段的距離定義可以給出測試點到角的距離定義，同是按角的正負(fù)區(qū)域劃分。P點到角∠Pi-1PiPi+1的距離，即它到兩個邊線段的最小距離。

在簡單n多邊形的n個角中，與測試點距離（若等于零，點在多邊形上）最小的線段至少存在一個。選擇任意一條作為相關(guān)線段，在多邊形中有兩個相鄰的角共有此線段，從中任一個角與點的距離相關(guān)性最強(qiáng)。如果測試點在此角負(fù)側(cè)，判定點在多邊形外部，否則在其內(nèi)部。確定點與多邊形內(nèi)外位置關(guān)系。

2 算法描述

算法輸入簡單n邊形的點序列 （逆時針序列）的橫縱坐標(biāo)以及測試點的橫縱坐標(biāo)，點序列集D= {P1，P2，…Pn}。判別測試P點是否在多邊形的內(nèi)部、外部、或邊界上。

算法實現(xiàn)步驟：

Step1輸入：點序列集D={P1，P2，…Pn}，d=0，s= 0;

Step2求解：求點P與Pi-1Pi邊線段的距離并存儲在變量d，s=i-1。如果點P到向量PiPi+1的距離小于前一步的距離d，用新的距離值替換d，并更新下標(biāo)s=i。如此循環(huán)求解到最后一個邊停止。

Step3判別：若d=0，則測試點P在多邊形上,否則，使用1.1節(jié)中的方法，判別點P與∠Ps-1PsPs+1的內(nèi)外側(cè)，點P與∠Ps-1PsPs+1內(nèi)外側(cè)關(guān)系與點P與多邊形內(nèi)外側(cè)性質(zhì)相同。

算法結(jié)束。

3 算法分析

對上述算法的時間復(fù)雜度。算法第二步中，對點到線段距離求解和替代中至多有8次乘法運(yùn)算，一次掃描運(yùn)算總共有8N次的乘法運(yùn)算，可以找出與點到距離最小的一條線段。在第三步的判別點與角的正負(fù)關(guān)系時也只是8次乘法運(yùn)算。判別中總共運(yùn)算次數(shù)最多是8N+8次的乘法運(yùn)算。從這個方面可以看到此算法的運(yùn)算速度大大提高。算法在matlab環(huán)境中進(jìn)行測試，通過對大量多邊形相對給定點的求解試驗，結(jié)果表明該算法運(yùn)行穩(wěn)定可靠。

本文中所提出的算法計算復(fù)雜度是線性的。所用的測試程序在Pentium(R)Dual-Core，1.99GB內(nèi)存微機(jī)，用Matlab6.5所編制。本文的算法對單位圓和邊長為1個單位的三角形、五角星形、六角星形上4000個、400000個采樣點進(jìn)所組成的簡單多邊進(jìn)行測試計算時間。從下表可見，與文獻(xiàn)[5]、[11]中的算法在同樣的環(huán)境下運(yùn)算進(jìn)行比較，本文的算法在運(yùn)算時間上要優(yōu)于這兩種算法。

表1 內(nèi)外側(cè)測試

[1]LI W.A point inclusion test algorithm for simple polygons[J].Lecture Notes in Computer Science，2005，3480：759-775

[2]Tate S J，Jared G E M.Recognising symmetry in solid models[J].Computer-Aided Design，2003，53 (7)：673-692

[3]丁健，江南，芮挺，簡單多邊形方向識別的健壯算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2005，17 (3)：442-447

[4]董秀山，劉潤濤.判斷點與簡單多邊形位置關(guān)系的新算法[J].計算機(jī)工程與應(yīng)用，2009，45(2)：185-187

[5]王華兵，劉偉軍等.一種檢測點在簡單平面多邊形內(nèi)外的算法[J].儀器儀表學(xué)報，2007，28(8)：479-482

[6]Feito F，Torres J C，Urena A.Orientation，simplicity，and inclusion test for planar polygons[J].Computers &Graphics，1995，19(4)：595-600

[7]郭雷，王洵，王曉蒲.有向回路法和網(wǎng)格法：多邊形內(nèi)外點判別的新方法[J].計算機(jī)工程與應(yīng)用，2002，38(19)：119-122

[8]郝建強(qiáng)，宮云戰(zhàn)，葉紅.點對多邊形位置檢測的穩(wěn)定串行最優(yōu)與并行的算法[J].計算機(jī)應(yīng)用研究，2010，27(4)：1342-1348

[9]劉潤濤，劉玉珍.點在多邊形內(nèi)測試的新算法[J].工程圖學(xué)學(xué)報，2008，2：89-93

[10]Wu Hua-yu，Gong Jian-ya，Li De-ren et al.An algebraic algorithm for point inclusion query[J].Computers&Graphics，2000，24(4)：517-522

[11]張寧寧，張樹有，譚建榮.映射相關(guān)邊概念的多邊形內(nèi)外點判別算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2004，16(7)：935-938

[12]李基拓，陸國棟，馮星.基于單調(diào)性與相關(guān)邊的多邊形內(nèi)外點判斷算法[J].中國圖象圖形學(xué)報，2002,7(6)：596-600

[13]胡景松，張麗芬.點與簡單多邊形關(guān)系的新算法[J].計算機(jī)工程，2004，30(20)：86-88

[14]WU H.An algebraic algorithm for point imclusion query[J].Computers&Graphics，2000，24：517-522