點(diǎn)與簡單多邊形位置關(guān)系判別新算法

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

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

引言

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

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

1 算法理論基礎(chǔ)

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

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

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

圖1 多邊形角

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

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

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

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

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

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

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

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

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

1.2 點(diǎn)到角的距離

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

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

圖3 點(diǎn)到線段距離

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

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

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

2 算法描述

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

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

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

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

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

算法結(jié)束。

3 算法分析

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

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

表1 內(nèi)外側(cè)測(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]丁健，江南，芮挺，簡單多邊形方向識(shí)別的健壯算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17 (3)：442-447

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

[5]王華兵，劉偉軍等.一種檢測(cè)點(diǎn)在簡單平面多邊形內(nèi)外的算法[J].儀器儀表學(xué)報(bào)，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)外點(diǎn)判別的新方法[J].計(jì)算機(jī)工程與應(yīng)用，2002，38(19)：119-122

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

[9]劉潤濤，劉玉珍.點(diǎn)在多邊形內(nèi)測(cè)試的新算法[J].工程圖學(xué)學(xué)報(bào)，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)外點(diǎn)判別算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16(7)：935-938

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

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

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