基于斜率的多邊形內(nèi)外點(diǎn)快速判別算法

洪志強(qiáng)

(江蘇科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003)

0 引言

點(diǎn)與多邊形的位置關(guān)系的判別，是計算機(jī)圖形學(xué)中的一個基本問題，這在計算機(jī)圖形處理、模式識別、CAD及可視化領(lǐng)域中有著廣泛的應(yīng)用。在三維渲染的光線跟蹤等算法中更是有著舉足輕重的作用，該算法的優(yōu)劣，直接關(guān)系到算法的效率及應(yīng)用可行性。由于這是一個基本的圖形算法，近年來也鮮見有人發(fā)文章對此進(jìn)行深入研究[1]，因此，目前大部分工程中所使用的還是相對傳統(tǒng)的算法。傳統(tǒng)的點(diǎn)與多邊形的位置關(guān)系判別法主要有射線法[2]、角度和法[3]、重心坐標(biāo)法[4-5]等及其一些改進(jìn)算法[6-12]。這些方法雖也可行，但其運(yùn)算復(fù)雜度和計算量卻仍然很大，實(shí)際應(yīng)用過程中耗時太多，導(dǎo)致一些以此為基礎(chǔ)的復(fù)雜算法難以投入應(yīng)用。像射線法[1]，該方法需要從待測點(diǎn)水平引出一條射線，然后依次對多邊形各邊進(jìn)行求交運(yùn)算，而一次求交運(yùn)算就包含多次乘除法運(yùn)算，可見其運(yùn)算量多大，況且還有奇異點(diǎn)的特殊情況需要單獨(dú)處理，因此，這種算法確實(shí)難以滿足要求。而角度和法[2]需要計算各邊到待測點(diǎn)的內(nèi)角，這其中除了有復(fù)雜的三角函數(shù)運(yùn)算之外，還有多次近似計算，其算法復(fù)雜程度和運(yùn)算精度都有問題，還有重心坐標(biāo)法，此法還引入了矩陣運(yùn)算[4]，或是多變量的方程求解運(yùn)算[5]，其運(yùn)算復(fù)雜程度也是難以滿足需求。而基于這些算法之上的改進(jìn)算法[6]及其在應(yīng)用過程中與其它算法結(jié)合的算法[13-14]，計算量仍然很大。

本文提出一種基于斜率的快速判別法。該算法在運(yùn)算過種中只需計算該點(diǎn)與多邊形各頂點(diǎn)的連線的斜率，然后依次與多邊形各頂點(diǎn)的兩條鄰邊的斜率進(jìn)行比較，即可得到判定結(jié)果。該算法的核心思想是將問題最簡化，最終判定的只是點(diǎn)與角的位置關(guān)系，整個判定過程算法簡單，沒有復(fù)雜的點(diǎn)乘、叉乘三角函數(shù)等運(yùn)算，而僅只有平均n/2次除法及一些簡單的邏輯判斷，從而有效降低了運(yùn)算復(fù)雜度，獲得了很高的運(yùn)算效率。

1 基本約定與算法思想

1.1 正方向的約定

在圖形處理運(yùn)算中，多邊形通常被表示為一連串的頂點(diǎn)序列，這些序列的先后關(guān)系即為順序，一個簡單的多邊形頂點(diǎn)序列通常有兩種，即順時針和逆時針，這兩種順序繪制出來分別為多邊形的正面和反面，這里約定采用逆時針順序?yàn)槎噙呅蔚恼较?，即正面朝上，如圖1所示。

圖1 方向約定

1.2 坐標(biāo)系統(tǒng)

在笛卡爾坐標(biāo)中，平面的中心為坐標(biāo)原點(diǎn)，坐標(biāo)軸的箭頭所指方向?yàn)樵撦S的正方向，而在屏幕坐標(biāo)中，屏幕的左上角為坐標(biāo)原點(diǎn)，水平向右方向?yàn)閤軸正方向，垂直向下方向?yàn)閥軸的正方向。如圖2所示。

圖2 坐標(biāo)系統(tǒng)圖

在實(shí)際繪圖中常用屏幕坐標(biāo)系，因此本文也使用屏幕坐標(biāo)系。

1.3 斜率

任取直線l上不同的兩點(diǎn)分別記為P1(x1，y1)，P2(x2，y2)，應(yīng)用斜率公式:

即可求得直線l的斜率。在三角形中，計算各邊的斜率只需取各邊的相應(yīng)頂點(diǎn)，代入公式即可求得。注意，對于垂直的邊，因x1=x2，有分母dx=0，所以為避免被0除的錯誤，這里以一個很小的數(shù)來代替，如dx=1e－6。

顯然，由斜率公式可得，當(dāng)分子或分母同為正或同為負(fù)時，斜率保持不變，這種性質(zhì)在圖形中的表示如圖3所示。

圖3 方向不同但斜率相同的兩直線

1.4 斜率變化空間

在以逆時針為序的屏幕坐標(biāo)空間中，為計算各種方向的直線的斜率，可以如下操作:

任取直線一兩點(diǎn)，分別計為點(diǎn)A和點(diǎn)B，計算其斜率。然后固定其中一點(diǎn)如點(diǎn)A不動，以該點(diǎn)為圓心，逆時針旋轉(zhuǎn)該直線，由B點(diǎn)的不同值即可計算出不同傾斜角度的直線的斜率在屏幕坐標(biāo)空間中的變化范圍，顯然，水平軸逆時針旋轉(zhuǎn)從0到360度時其直線斜率變化曲線如同正切曲線，如圖4(b)所示。顯然，在圖4(a)中逆時針旋轉(zhuǎn)的直線，斜率范圍在區(qū)間(a)或(b)時其變化率為(0，+∞)，斜率范圍在區(qū)間(c)或(d)時，其變化率為(－∞，0)。

圖4 斜率的變化范圍

1.5 點(diǎn)與角的位置關(guān)系

在圖5中，∠AOB與點(diǎn) P的關(guān)系為點(diǎn) P位于∠AOB內(nèi)，而∠AOB與點(diǎn) P'的關(guān)系為點(diǎn) P'不在∠AOB內(nèi)。顯然，點(diǎn)P是否在∠AOB內(nèi)根據(jù)其點(diǎn)P與點(diǎn)O的連線的直線的斜率與∠AOB的兩邊的斜率相比較而得知。雖然∠A'OB'內(nèi)點(diǎn)不在∠AOB內(nèi)，但斜率相同，此處無需判別點(diǎn)是處在∠AOB內(nèi)還是∠A'OB'內(nèi)，而是將區(qū)域(c)和區(qū)域(d)都看作∠AOB的內(nèi)點(diǎn)有效區(qū)，而區(qū)域(a)和區(qū)域(b)看作∠AOB的內(nèi)點(diǎn)無效區(qū)，因此，這里只需看點(diǎn) P是在(a)、(b)、(c)、(d)中的哪個區(qū)，即可判別出點(diǎn)P是否在∠AOB內(nèi)點(diǎn)有效區(qū)。

圖5 角與點(diǎn)的位置關(guān)系

1.6 同斜率點(diǎn)的排除

由上面所得，每個角即有兩個內(nèi)點(diǎn)有效區(qū)，而其中一個是真內(nèi)點(diǎn)，另一個是其對頂角的內(nèi)點(diǎn)，如何排除其對頂角的內(nèi)點(diǎn)，可以如圖6(a)所示。

圖6 同斜率點(diǎn)非內(nèi)點(diǎn)區(qū)域的排除

∠AOB有兩個內(nèi)點(diǎn)無效區(qū)(斜線)，點(diǎn) P為∠AOB的內(nèi)點(diǎn)，而點(diǎn)P'為∠A'OB'的內(nèi)點(diǎn)，點(diǎn)P與點(diǎn)P'所在區(qū)域均為∠AOB的內(nèi)點(diǎn)有效區(qū)，邊AO與OB為∠AOB的鄰邊，∠AOB與∠OBA為鄰角。顯然，∠OBA也有兩個內(nèi)點(diǎn)無效區(qū)(格子)，點(diǎn)P在∠OBA的內(nèi)點(diǎn)有效區(qū)，點(diǎn)P″也在∠OBA的內(nèi)點(diǎn)有效區(qū)，這里，點(diǎn)P'雖處于∠AOB的內(nèi)點(diǎn)有效區(qū)，但是處于∠OBA的內(nèi)點(diǎn)無效區(qū)。顯然，點(diǎn)P'所在區(qū)域不同時處于∠AOB與∠OBA的內(nèi)點(diǎn)區(qū)域，應(yīng)該排除。這里，只有點(diǎn)P才是∠AOB與∠OBA的真正內(nèi)點(diǎn)。

由上擴(kuò)展到三角形3個角的情況，如圖6(b)所示，所有不同時處于所有角的內(nèi)點(diǎn)區(qū)域的點(diǎn)P'、P″、P?都會被排除，因此，只有點(diǎn)P所在才域的點(diǎn)才是三角形的真正內(nèi)點(diǎn)。同理，即可快速判斷出多邊形內(nèi)點(diǎn)。

2 算法描述

算法主要分為4個步驟:

(1)預(yù)處理。

本文提出的算法只適用于有序的逆時針順序凸多邊形。若順序相反，可反轉(zhuǎn)頂點(diǎn)次序再作判斷。若為凹多邊形，則需先對多邊形在凹點(diǎn)處進(jìn)行分解，使之成為多個凸多邊形序列，再依次作判斷。

(2)計算出多邊形的各邊斜率，若需多次使用，只需首次計算一次，然留結(jié)果供后續(xù)使用而無需重復(fù)計算。

(3)記待測點(diǎn)為P(xp，yp)，依取第i個多邊形頂點(diǎn)A(xa，ya)，計算由該兩點(diǎn)組成的直線的斜率，記為spa。

(4)取第i個頂點(diǎn)的前向邊與后向邊斜率分別記為 se1、se2，對 se1、se2進(jìn)行比較，可以分兩大類:se1＜ se2和se1＞se2，具體比較如下:

①se1＜se2。

如圖7所示，當(dāng)se1＜0，se2＜0時，該角的內(nèi)點(diǎn)無效區(qū)域?yàn)?s)、(s1)和(s2)，顯然，當(dāng)(s)和(s1)+(s2)為同斜率區(qū)域時，只需判斷區(qū)域(s1)+s(2)即可。如圖7所示，區(qū)域(s1)的斜率＞se2，(s2)的斜率＜se1，因此，只需判是否滿足條件 spa＜se1或spa＞se2即可。

圖7 各種斜率情況下的內(nèi)點(diǎn)無效區(qū)域

同理，當(dāng)se1＜0、se2＞0和se1＞0、se2＞0時分別如圖7(b)和(c)所示，也只需判斷是否滿足條件spa＜se1或 spa＞se2即可。

②se1＞se2。

如圖7所示，當(dāng)se1＜0、se2＜0時，該角的內(nèi)點(diǎn)無效區(qū)域?yàn)?s)和(s1)，顯然，只需判別是否滿足條件spa＜se1并且 spa＞se2即可。

同理，當(dāng)se1＜0、se2＞0和se1＞0、se2＞0時分別如圖7(b)和(c)所示，也只需判斷是否滿足條件spa＜se1并且 spa＞ se2即可。

當(dāng)然，當(dāng)se1=se2時，該多邊形為退化多邊形，即可認(rèn)為是少一條同斜率的邊的多邊形，因此可以不作第三種情況考慮。

判別過程中，對于任何不滿足判別要求的點(diǎn)即可判為外點(diǎn)。

(5)對于滿足所有頂點(diǎn)的判別要求的內(nèi)點(diǎn)，為多邊形的真正內(nèi)點(diǎn)，輸出真值，算法結(jié)束。

綜上，可用簡潔的判別函數(shù)描述如下:

若對所有頂點(diǎn)進(jìn)行判別通過，即為真正內(nèi)點(diǎn)，輸出即可。由此可見，該判別算法的簡潔高效。

3 算法測試

3.1 自測試

測試程序使用 C++Builder2010編譯，在1.7 GHZ的Intel i7740QM CPU上單線程進(jìn)行測試，每秒可以進(jìn)行千萬次左右的四邊形內(nèi)點(diǎn)判別算法。

圖8 對隨機(jī)生成的三角形和多邊形進(jìn)行內(nèi)點(diǎn)測試

如圖8所示，對隨機(jī)生成的凸多邊形進(jìn)行10000次隨機(jī)取點(diǎn)測試，圖藍(lán)(深)色點(diǎn)為外點(diǎn)，黃(淺)色點(diǎn)為內(nèi)點(diǎn)，無論是從速度上還是準(zhǔn)確性上都取得了非常好的效果。

3.2 對比測試

分別使用內(nèi)角和法、射線法和斜率判別法進(jìn)行多邊形內(nèi)點(diǎn)測試。測試首先生成100萬個隨機(jī)點(diǎn)，然后使用3種算法對隨機(jī)生成的三角形進(jìn)行內(nèi)外點(diǎn)測試，并記錄下每次使用時間。循環(huán)測試100次，分別計算各種算法的平均使用時間，測試的結(jié)果對比如表1所示。

表1 主要算法速度測試對比

4 結(jié)束語

作為圖形學(xué)中的一個基礎(chǔ)的并且廣泛使用的算法，對此算法進(jìn)行的點(diǎn)滴改進(jìn)，都對許多以此為基礎(chǔ)的復(fù)雜算法有著深遠(yuǎn)的影響。雖然本文所提出的算法需要一些前提條件，但在圖形學(xué)中，這些條件一般都不難具備。為了獲得更高的運(yùn)算效率，少量的額外運(yùn)算開銷也是值得的，另外，在3D圖形處理中也經(jīng)常需要進(jìn)行位置關(guān)系判別，若能將此算法加以擴(kuò)展乃至應(yīng)用，那將是一件很有意義的事情。因此，合理使用此算法，即可有效提升現(xiàn)有的圖形算法效率，為實(shí)際工程應(yīng)用提供更多可能。

[1]王潤科，張顏麗.判斷點(diǎn)與多邊形位置關(guān)系的算法綜述[J].甘肅聯(lián)合大學(xué)學(xué)報，2006，20(6):32-35，41.

[2]Taloy G.Point in polygon test[J].Survey Review，1994，32(254):479-484.

[3]Badouel Didier.An Efficient Ray-Polygon Intersection[M].AP Professional，1990.

[4]Eric Lengyel.Mathematics for 3D Game Programming and Computer Graphics(3rd Edition)[M].USA:Course Technology PTR，2012:141-143.

[5]Matt Pharr，Greg Humphreys.Physically Based Rending(2nd Edition)[M].USA:Morgan Kaufmann，2010:140-142.

[6]Yang Sheng，Yong Jun-Hai，Sun Jiaguang.A point-in-polygon method based on a quasi-closest point[J].Computers＆ Geosciences，2010，36(2):205-213.

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

[8]周欣，張樹有，潘志庚.基于鏈碼和特征形的多邊形內(nèi)外點(diǎn)判斷算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)報，2006，18(9):1317-1321.

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

[10]陳瑞卿，周健，虞烈.一種判斷點(diǎn)與多邊形關(guān)系的快速算法[J].西安交通大學(xué)學(xué)報，2007，41(1):59-63.

[11]王晨，池建斌，馮桂珍.一種判定點(diǎn)和多邊形包含關(guān)系的有效算法[J].計算機(jī)應(yīng)用與軟件，2005，22(4):110-112.

[12]李雪，石廣田.一種三角形內(nèi)外點(diǎn)的快速判定方法[J].現(xiàn)代電子技術(shù)，2008，267(4):110-112.

[13]Li Jing，Wang Wencheng，Wu Enhua.Point-in-polygon tests by convex decomposition[J].Computers ＆ Graphics，2007，31(4):636-648.

[14]Alireza Zareia，Mohammad Ghodsi.Query point visibility computation in polygons with holes[J].Computational Geometry，2008，39(2):78-90.