點(diǎn)與多邊形或多面體的拓?fù)潢P(guān)系判斷

翟 艷，徐衛(wèi)亞，張 強(qiáng)

（河海大學(xué) 巖土力學(xué)與堤壩工程教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京210098）

0 引 言

點(diǎn)與多邊形或多面體的拓?fù)潢P(guān)系判斷方法，目前主要有射線法，叉積判斷法，角度和法和面積法 （體積法）［1－3］。對(duì)簡(jiǎn)單的多邊形，這些方法雖然都有各自的局限性，但通?？勺龀稣_判斷，而對(duì)復(fù)雜的多邊形，尤其當(dāng)射線過多邊形的拐點(diǎn)或射線與多邊形的某部分邊界重合時(shí)易出現(xiàn)奇異情況，此時(shí)傳統(tǒng)方法不能正確判斷點(diǎn)與多邊形的拓?fù)潢P(guān)系［4］。為解決此問題，一些學(xué)者對(duì)傳統(tǒng)方法進(jìn)行改進(jìn)，也有在傳統(tǒng)方法基礎(chǔ)上提出新的判斷方法。文獻(xiàn) ［5］從點(diǎn)與角的最短距離入手，找出與點(diǎn)距離最小的邊，通過掃描確定唯一關(guān)聯(lián)邊作為判斷依據(jù)，利用該邊的兩個(gè)角與點(diǎn)的位置關(guān)系判斷點(diǎn)與多邊形的位置關(guān)系，但該法在確定有效關(guān)聯(lián)邊時(shí)過程復(fù)雜；文獻(xiàn) ［6］利用直線的正負(fù)性判斷點(diǎn)與多邊形的位置關(guān)系，但該法只是減少求交點(diǎn)的數(shù)量，未對(duì)射線法中存在的奇異情況給出判斷；文獻(xiàn) ［7］引入方向因子和方向邊，通過確定由點(diǎn)與方向邊得到的方向因子判斷點(diǎn)與多邊形的位置關(guān)系，該算法計(jì)算步驟復(fù)雜，判斷過程繁瑣；文獻(xiàn) ［8］克服傳統(tǒng)射線法初始射線選擇有太大主觀性不足，找到多邊形所有頂點(diǎn)在某區(qū)域的最小斜率點(diǎn)，利用該點(diǎn)確定初始判斷射線。但該法僅對(duì)簡(jiǎn)單多邊形適用性較好，對(duì)復(fù)雜多邊形效果不盡人意。

針對(duì)目前改進(jìn)方法存在的問題，本文在傳統(tǒng)射線法的基礎(chǔ)上引入虛交點(diǎn)的概念，對(duì)其進(jìn)行改進(jìn)，改進(jìn)后的射線法可以解決傳統(tǒng)方法在處理奇異情況時(shí)存在的問題，并通過運(yùn)用切割剖面法將該方法應(yīng)用到空間點(diǎn)與多面體拓?fù)潢P(guān)系的判斷中。

1 傳統(tǒng)射線法基本原理

傳統(tǒng)射線法是判斷點(diǎn)與多邊形位置關(guān)系的常用方法，其基本原理請(qǐng)參見文獻(xiàn) ［2］。圖1（a）中，P1點(diǎn)與多邊形有兩個(gè)交點(diǎn)，在多邊形外部；P2點(diǎn)與多邊形有一個(gè)交點(diǎn)，在多邊形內(nèi)部。對(duì)于簡(jiǎn)單多邊形與點(diǎn)的位置關(guān)系，該判別方法結(jié)果準(zhǔn)確。但對(duì)于如圖1（b）所示的復(fù)雜多邊形而言，根據(jù)傳統(tǒng)射線法不能正確地判斷點(diǎn)與多邊形的拓?fù)潢P(guān)系。如圖1（b）所示，點(diǎn)P1與多邊形有4個(gè)交點(diǎn)，根據(jù)傳統(tǒng)的射線法判斷得到點(diǎn)P1在多邊形外部，實(shí)際點(diǎn)P1卻在多邊形內(nèi)部。故傳統(tǒng)射線法在判斷點(diǎn)與復(fù)雜多邊形拓?fù)潢P(guān)系時(shí)存在不足。經(jīng)研究發(fā)現(xiàn)，若過點(diǎn)P的射線通過多邊形的頂點(diǎn)時(shí)，傳統(tǒng)的射線法可能做出錯(cuò)誤的判斷，主要是因?yàn)樯渚€與多邊形的交點(diǎn)總數(shù)的統(tǒng)計(jì)方法不能滿足這些情況。

圖1 圖形實(shí)例

2 改進(jìn)射線法基本原理

本文中的多邊形節(jié)點(diǎn)排列順序?yàn)槟鏁r(shí)針或者順時(shí)針，改進(jìn)射線法的實(shí)現(xiàn)步驟如下：

步驟1 判斷點(diǎn)P是否位于多邊形邊界上，若點(diǎn)P位于邊界上，返回點(diǎn)P位于多邊形邊界上，否則，執(zhí)行步驟2至步驟4。

根據(jù)多邊形頂點(diǎn)排列順序，從第一個(gè)頂點(diǎn)開始依次連接多邊形相鄰的頂點(diǎn)，將多邊形拆分為一些線段。遍歷所有線段，判斷點(diǎn)P是否位于線段上，若點(diǎn)P位于某條線段上，則點(diǎn)P位于多邊形的邊界上。

步驟2 按照傳統(tǒng)的射線法計(jì)算過點(diǎn)P的射線與多邊形的交點(diǎn)總數(shù)inter＿point＿total。對(duì)所有的線段進(jìn)行循環(huán)，求解過點(diǎn)P的水平向右 （或鉛垂線）射線與線段的交點(diǎn)（在端點(diǎn)處的交點(diǎn)除外）總數(shù)Num1；在循環(huán)過程中，對(duì)每個(gè)交點(diǎn)進(jìn)行判斷，若該交點(diǎn)位于線段的某個(gè)端點(diǎn)，則Num2＝Num2＋1；Num2表示射線與多邊形線段相交在端點(diǎn)處的交點(diǎn)個(gè)數(shù)。則過點(diǎn)P的射線與多邊形的交點(diǎn)總數(shù)inter＿point＿total＝Num1＋Num2。

步驟3 計(jì)算過點(diǎn)P的射線與多邊形的虛交點(diǎn)總數(shù)virtual＿inter＿point＿total。

若過點(diǎn)P的射線與多邊形的某個(gè)交點(diǎn)為多邊形的某些頂點(diǎn)，在某些情況下，這些交點(diǎn)的一部分或全部為虛交點(diǎn)。下面具體說明虛交點(diǎn)的計(jì)算過程：

以過點(diǎn)P的水平向右的射線為例，根據(jù)多邊形的頂點(diǎn)排列順序，從第一個(gè)頂點(diǎn)開始判斷，若某個(gè)頂點(diǎn)V（m）的Y坐標(biāo)值與點(diǎn)P的Y坐標(biāo)值相等，則從頂點(diǎn)V（m＋1）依次查找與點(diǎn)P的Y坐標(biāo)相同的頂點(diǎn)個(gè)數(shù)Num3，判斷頂點(diǎn)V（m－1）和V（m＋Num3＋1）與射線的關(guān)系，若這兩個(gè)頂點(diǎn)位于射線的上下側(cè)，則頂點(diǎn) V（m＋1）到V（m＋Num3）為虛交點(diǎn)，virtual＿inter＿point＿total＝virtual＿inter＿point＿total＋Num3，若這兩個(gè)頂點(diǎn)位于射線的同一側(cè)，則頂點(diǎn)V（m）到V（m＋Num3）為虛交點(diǎn)，virtual＿inter＿point＿total＝virtual＿inter＿point＿total＋Num3＋1；從頂點(diǎn)V（m＋Num3＋2）繼續(xù)進(jìn)行判斷，將虛交點(diǎn)的總數(shù)virtual＿inter＿point＿total進(jìn)行累加，直到所有頂點(diǎn)全部判斷完畢。

步驟4 計(jì)算過點(diǎn)P的射線與多邊形的真實(shí)交點(diǎn)總數(shù)real＿inter＿point＿total。

對(duì)于無孔洞的多邊形，通過執(zhí)行步驟1至步驟4判斷點(diǎn)與多邊形的拓?fù)潢P(guān)系。首先執(zhí)行步驟1判斷點(diǎn)P是否位于邊界上，若點(diǎn)P位于邊界上，返回點(diǎn)P位于邊界上，否則，執(zhí)行步驟2至步驟4求解過點(diǎn)P的射線與該多邊形的真實(shí)交點(diǎn)的總數(shù)，real＿inter＿point＿total＝inter＿point＿total－virtural＿inter＿point＿total，若real＿inter＿point＿total為奇數(shù)，則返回點(diǎn)P位于多邊形內(nèi)部，否則，返回點(diǎn)P位于多邊形外。

對(duì)于還有孔洞的多邊形，需要對(duì)其內(nèi)部邊界和外部邊界分別執(zhí)行步驟1至步驟4。首先執(zhí)行步驟1來判斷點(diǎn)P是否位于內(nèi)部邊界或外部邊界上。若點(diǎn)P位于多邊形內(nèi)邊界或外邊界上，返回點(diǎn)P位于多邊形的邊界上。否則，執(zhí)行步驟2至步驟4求解過點(diǎn)P的射線與內(nèi)邊界多邊形的真實(shí)交點(diǎn)總數(shù)real＿inter＿point＿total1和所有外部多邊形的真實(shí)交點(diǎn)總數(shù)real＿inter＿point＿total2，射線與多邊形邊界的真實(shí)交點(diǎn)總數(shù)real＿inter＿point＿total＝real＿inter＿point＿total1＋real＿inter＿point＿total2；若real＿inter＿point＿total為奇數(shù)，返回點(diǎn)P位于含孔洞多邊形的內(nèi)部，否則，返回點(diǎn)P位于含孔洞的多邊形外部。

3 算例驗(yàn)證

下面分別給出點(diǎn)與無孔洞的多邊形和有孔洞的多邊形的拓?fù)潢P(guān)系的算例以驗(yàn)證上述改進(jìn)射線法的正確性。

對(duì)于無孔洞多邊形如圖2（a）所示，圖示無孔洞多邊形有11個(gè)頂點(diǎn)V1～V11，共有11條線段。

圖2 復(fù)雜多邊形算例

（1）P1點(diǎn)：

步驟1 P1不在多邊形邊界上；

步驟2 Num1＝0；Num2＝1；inter＿point＿total＝Num1＋Num2＝1；

步驟3 多邊形頂點(diǎn)V8和V6在射線的同一側(cè)，V7為虛交點(diǎn)，故virtual＿inter＿point＿total＝1；

步驟4 real＿inter＿point＿total＝inter＿point＿totalvirtural＿inter＿point＿total＝1－1＝0；

P1點(diǎn)位于多邊形外部。

（2）P2點(diǎn)：

步驟1 P2不在多邊形邊界上；

步驟2 Num1＝1；Num2＝3；inter＿point＿total＝Num1＋Num2＝4；

步驟3 Num3＝2，多邊形頂點(diǎn)V11和V7在射線的同一側(cè)，V8～V10均為虛交點(diǎn)，故virtual＿inter＿point＿total＝3；

步驟4 real＿inter＿point＿total＝inter＿point＿totalvirtural＿inter＿point＿total＝4－3＝1；

P2點(diǎn)位于多邊形內(nèi)部。

（3）P4點(diǎn)：

步驟1 P2不在多邊形邊界上；

步驟2 Num1＝0；Num2＝4；inter＿point＿total＝Num1＋Num2＝4；

步驟3 Num3＝3，多邊形頂點(diǎn)V1和V6在射線的異側(cè)，V3～V5均為虛交點(diǎn)，故virtual＿inter＿point＿total＝3；

步驟4 real＿inter＿point＿total＝inter＿point＿totalvirtural＿inter＿point＿total＝4－3＝1；

P4點(diǎn)位于多邊形內(nèi)部。

對(duì)于有孔洞多邊形如圖2（b）所示。其中圖2（c）所示陰影部分為有孔洞多邊形的內(nèi)部。

（1）P1點(diǎn)：內(nèi)邊界

步驟1 P1不在多邊形內(nèi)邊界上；

步驟2 Num1＝2；Num2＝0；inter＿point＿total＝Num1＋Num2＝2；

步驟3 Num3＝0，virtual＿inter＿point＿total＝0；

步驟4 real＿inter＿point＿total1＝inter＿point＿total－virtural＿inter＿point＿total＝2－0＝2；

外邊界：

步驟1 P1不在多邊形外邊界上；

步驟2 Num1＝2；Num2＝2；inter＿point＿total＝Num1＋Num2＝4；

步驟3 Num3＝1，多邊形頂點(diǎn)V11和V14在射線的異側(cè)，V12～V13均為虛交點(diǎn)，故virtual＿inter＿point＿total＝2；

步驟4 real＿inter＿point＿total2＝inter＿point＿total－virtural＿inter＿point＿total＝4－2＝2；

real＿inter＿point＿total＝real＿inter＿point＿total1＋real＿inter＿point＿total2＝4；

P1點(diǎn)位于多邊形外部。

（2）P2點(diǎn)：內(nèi)邊界

步驟1 P2不在多邊形內(nèi)邊界上；

步驟2 Num1＝0；Num2＝3；inter＿point＿total＝Num1＋Num2＝3；

步驟3 Num3＝2，V21和V24位于射線同側(cè)，V25～V27均為虛交點(diǎn)，故virtual＿inter＿point＿total＝3；

步驟4 real＿inter＿point＿total1＝inter＿point＿total－virtural＿inter＿point＿total＝3－3＝0；

外邊界：

步驟1 P2不在多邊形外邊界上；

步驟2 Num1＝1；Num2＝0；inter＿point＿total＝Num1＋Num2＝1；

步驟3 Num3＝0，virtual＿inter＿point＿total＝0；

步驟4 real＿inter＿point＿total2＝inter＿point＿total－virtural＿inter＿point＿total＝1－0＝1；

real＿inter＿point＿total＝real＿inter＿point＿total1＋real＿inter＿point＿total2＝1；

P2點(diǎn)位于多邊形內(nèi)部。

（3）P3點(diǎn)：內(nèi)邊界

步驟1 P3不在多邊形內(nèi)邊界上；

步驟2 Num1＝1；Num2＝1；inter＿point＿total＝Num1＋Num2＝2；

步驟3 Num3＝0，V21和V23位于射線同側(cè)，V22為虛交點(diǎn)，故virtual＿inter＿point＿total＝1；

步驟4 real＿inter＿point＿total1＝inter＿point＿total－virtural＿inter＿point＿total＝2－1＝1；

外邊界：

步驟1 P1不在多邊形外邊界上；

步驟2 Num1＝1；Num2＝0；inter＿point＿total＝Num1＋Num2＝1；

步驟3 Num3＝0，virtual＿inter＿point＿total＝0；

步驟4 real＿inter＿point＿total2＝inter＿point＿total－virtural＿inter＿point＿total＝1－0＝1；

real＿inter＿point＿total＝real＿inter＿point＿total1＋real＿inter＿point＿total2＝2；

P3點(diǎn)位于多邊形外部。

經(jīng)無孔洞多邊形和有孔洞多邊形與點(diǎn)的拓?fù)潢P(guān)系實(shí)例驗(yàn)證可知，本文提出的基于改進(jìn)射線法的點(diǎn)與多邊形的拓?fù)潢P(guān)系快速判別方法具有相當(dāng)?shù)臏?zhǔn)確性。

4 點(diǎn)與多面體的拓?fù)潢P(guān)系判斷

相比于平面內(nèi)點(diǎn)與多邊形的拓?fù)潢P(guān)系判斷，空間點(diǎn)與多面體的拓?fù)潢P(guān)系判斷更難。對(duì)于簡(jiǎn)單的多面體來說，可以用射線法準(zhǔn)確地判斷點(diǎn)與多面體的拓?fù)潢P(guān)系，但對(duì)于復(fù)雜的多面體來說，射線法不能給出正確的結(jié)果［9，10］。本文利用切割剖面法將三維問題轉(zhuǎn)化為二維問題，即將點(diǎn)與多面體的拓?fù)潢P(guān)系判斷轉(zhuǎn)化為點(diǎn)與多邊形的拓?fù)潢P(guān)系判斷。其具體思想如下：

步驟1 過點(diǎn)P做平行于某個(gè)坐標(biāo)平面，求得該平面與多面體邊界的交線。

本文中所述的多面體的邊界由三角形和四邊形構(gòu)成；因此求解平面與多面體邊界的交線的實(shí)質(zhì)是求解平面與三角形和四邊形的交線，為了編程方便可以將四邊形轉(zhuǎn)化為兩個(gè)三角形形。

對(duì)于不含孔洞的多面體來說，多面體的只有一個(gè)外邊界，邊界單元面的屬性標(biāo)記為外；對(duì)于含孔洞的多面體來說；多面體有內(nèi)邊界和外邊界組成，外部邊界單元面的屬性標(biāo)記為外；內(nèi)部單元面的屬性標(biāo)記為內(nèi)。若平面與某個(gè)單元面相交 （交線為線段），標(biāo)記該交線的邊界屬性與單元面的屬性一致。

步驟2 根據(jù)交線的邊界屬性，將其分為外邊界交線和內(nèi)邊界交線，并將內(nèi)邊界交線和外邊界交線均轉(zhuǎn)化為節(jié)點(diǎn)排列有序的內(nèi)邊界多邊形和外邊界多邊形。

步驟3 利用改進(jìn)后射線法，判斷點(diǎn)P與多邊形的拓?fù)潢P(guān)系，根據(jù)點(diǎn)與多邊形的拓?fù)潢P(guān)系確定點(diǎn)與多面體的拓?fù)潢P(guān)系。

若點(diǎn)P位于多邊形上，則點(diǎn)P位于多面體的邊界上。對(duì)于不含孔洞的多面體來說，若點(diǎn)P位于外邊界多邊形內(nèi)部，則點(diǎn)P位于多面體內(nèi)部；若點(diǎn)P位于外邊界多邊形外，則點(diǎn)P位于多面體外部。對(duì)于含孔洞的多面體來說，若點(diǎn)P位于內(nèi)邊界多邊形內(nèi)部，則點(diǎn)P位于多面體外部；若點(diǎn)P位于外邊界多邊形內(nèi)，同時(shí)位于內(nèi)多邊形外，則點(diǎn)P位于多面體內(nèi)部。

5 結(jié)束語

（1）在判定點(diǎn)與多邊形拓?fù)潢P(guān)系的傳統(tǒng)射線法的基礎(chǔ)上，引入虛交點(diǎn)的概念對(duì)其進(jìn)行改進(jìn)，解決了傳統(tǒng)射線法在判斷點(diǎn)與復(fù)雜多邊形拓?fù)潢P(guān)系，尤其是射線經(jīng)過多邊形頂點(diǎn)時(shí)存在的不足，并分別經(jīng)有孔洞和無孔洞多邊形與點(diǎn)的拓?fù)潢P(guān)系實(shí)例驗(yàn)證，結(jié)果表明本文提出的方法判斷結(jié)果準(zhǔn)確，簡(jiǎn)單易行，可操作性強(qiáng)。

（2）不同于傳統(tǒng)體積法判斷點(diǎn)與多面體的拓?fù)潢P(guān)系，本文利用切割剖面法將點(diǎn)與多面體的拓?fù)潢P(guān)系判斷轉(zhuǎn)化為點(diǎn)與多邊形的拓?fù)潢P(guān)系判斷，避免了傳統(tǒng)體積法難于計(jì)算多面體體積的問題。

［1］CHEN Zhengyang，WANG Liqing，CHEN Shuqiang.Method of point inclusion test for simple polygons based on forked point［J］.Computer Engineering，2007，33 （17）：239－240 （in Chinese）.［陳正陽，王麗青，陳樹強(qiáng).基于單調(diào)鏈的判斷點(diǎn)是否在多邊形內(nèi)的方法 ［J］.計(jì)算機(jī)工程，2007，33 （17）：239－240.］

［2］WANG Yanping，LIU Yonghe.The algorithm of using the method of radial to judge the points in flat in and out of the polygon ［J］.Shanxi Architecture，2007，33 （33）：364－365 （in Chinese）.［王燕平，劉永和.射線法判斷平面中的點(diǎn)在多邊形內(nèi)外的算法 ［J］.山西建筑，2007，33 （33）：364－365.］

［3］CHEN Ruiqing，ZHOU Jian，YU Lie.Fast method to determine spatial relationship between point and polygon ［J］.Journal of Xi’an Jiaotong University，2007，41 （1）：59－63 （in Chinese）.［陳瑞卿，周健，虞烈.一種判斷點(diǎn)與多邊形關(guān)系的快速算法［J］.西安交通大學(xué)學(xué)報(bào)，2007，41 （1）：59－63.］

［4］LIU Liang.An optimized algorithm to determine topo－relation between point and polygon and clockwise or anti－clockwise in polygon ［J］.Geomatics ＆Information Technology，2007，30（1）：84－86 （in Chinese）.［劉梁.點(diǎn)、多邊形拓?fù)潢P(guān)系與多邊形順、逆判斷優(yōu)化算法 ［J］.測(cè)繪與空間地理信息，2007，30（1）：84－86.］

［5］CHEN Jinlin，LIU Xiejin，LI Ning.New algorithm for determining position relation between simple polygon and point ［J］.Journal of Huainan Normal University，2012，14 （5）：120－122（in Chinese）.［陳金林，劉謝進(jìn)，李寧.點(diǎn)與簡(jiǎn)單多邊形位置關(guān)系判別新算 ［J］.淮南師范學(xué)院學(xué)報(bào)，2012，14 （5）：120－122.］

［6］HAO Jianqiang，GONG Yunzhan，YE Hong.Stable serial optimal and parallel algorithm of point－in－polygon test ［J］.Application Research of Computers，2010，27 （4）：1342－1348（in Chinese）.［郝建強(qiáng)，宮云戰(zhàn)，葉紅.點(diǎn)與多邊形位置檢測(cè)的串行最優(yōu)與并行的算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（4）：1342－1348.］

［7］ZHANG Ka，SHENG Yehua，YE Chun.Algorithm of polygon point in－out test based on direction factor and direction edge［J］.Science of Surveying and Mappong，2010，35 （4）：174－176（in Chinese）.［張卡，盛業(yè)華，葉春.基于方向因子和方向邊的多邊形內(nèi)外點(diǎn)判斷算法 ［J］.測(cè)繪科學(xué)，2010，35（4）：174－176.］

［8］DONG Xiushan，LIU Runtao.New algorithm for determining position relation between simple polygon and point ［J］.Computer Engineering and Applications，2009，45 （2）：185－186 （in Chinese）.［董秀山，劉潤(rùn)濤.判斷點(diǎn)與簡(jiǎn)單多邊形位置關(guān)系的新算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 （2）：185－186.］

［9］SHI Lu，BAI Bing，LI Xiaochun.New algorithm to judge the relation of spatial location between point and polyhedron［C］／／The Tenth National Exhibition of Rock Mechanics and Engineering Academic Conference Proceedings，2008：295－298（in Chinese）.［石露，白冰，李小春.判斷點(diǎn)與多面體空間位置關(guān)系的一個(gè)新算法 ［C］／／第十屆全國(guó)巖石力學(xué)與工程學(xué)術(shù)大會(huì)論文集，2008：295－298.］

［10］WU Bofeng，LIN Jiaxiang，WANG Weibin.The research on judging topological relationships between a point and a polyhedron ［J］.Journal of Fuzhou University （Natural Science），2010，38 （5）：634－639 （in Chinese）.［吳博峰，林甲祥，王偉斌.點(diǎn)與多面體空間拓?fù)潢P(guān)系的判定研究 ［J］.福州大學(xué)學(xué)報(bào) （自然科學(xué)版），2010，38 （ 5）：634－639.］