向 俊，王 靜，夏幼明

（1.廣西廣播電視大學(xué) 教學(xué)資源與技術(shù)中心，廣西 南寧530022；2.中國電信集團(tuán)山東分公司網(wǎng)絡(luò)中心，山東 濟(jì)南250101；3.云南師范大學(xué) 信息學(xué)院，云南 昆明650092）

0 引 言

在矢量GIS空間拓?fù)潢P(guān)系研究中，點(diǎn)與多邊形位置關(guān)系的判斷是最基本的問題，也是比較復(fù)雜的問題。許多學(xué)者研究了諸多算法來解決點(diǎn)與多邊形位置關(guān)系問題。如射線法、轉(zhuǎn)角法及改進(jìn)的射線法［1］，射線法能較好地解決點(diǎn)與復(fù)雜多邊形的位置關(guān)系。Sheng Yang等人針對點(diǎn)與多邊形位置關(guān)系判斷問題，提出了一種數(shù)值穩(wěn)定的解決方法，該方法準(zhǔn)確性較高，但時(shí)間代價(jià)大［2］。Juan J為了減少判斷點(diǎn)與多邊形關(guān)系時(shí)計(jì)算所耗費(fèi)的時(shí)間，提出了一種新的基于分層的數(shù)據(jù)結(jié)構(gòu)分析方法，該方法能減少算法的復(fù)雜性［3］。該方法優(yōu)點(diǎn)是判斷準(zhǔn)確，缺點(diǎn)是運(yùn)行時(shí)需要特定的平臺(tái)支持。劉梁為解決以往算法的不可靠和過于復(fù)雜問題，提出了面積判斷法，解決了在含有孤島的多邊形中，點(diǎn)與多邊形的關(guān)系判斷問題［4］，該方法具有準(zhǔn)確性、靈活性等優(yōu)點(diǎn)，但該方法未應(yīng)用于復(fù)雜的多邊形中。Jing Li等人為了提高判斷點(diǎn)是否在多邊形中的效率，提出通過在凸多邊形集中分解成單個(gè)多邊形，然后構(gòu)建BSP樹，在多邊形中，算法通過兩步執(zhí)行一個(gè)包含查詢，該方法的執(zhí)行效率較高［5］。李楠等為了解決多邊形內(nèi)外算法中BSP樹退化為鏈表的問題，提出一種改進(jìn)的點(diǎn)在多邊形內(nèi)外的判斷算法。首先對水平掃描線按照Y值進(jìn)行排序，然后將水平掃描線按二分法的順序插入到BSP樹中［6］，實(shí)驗(yàn)結(jié)果表明該方法具有最優(yōu)的查找效果，算法簡單易實(shí)現(xiàn)，是正確有效的。劉亞彬等通過計(jì)算交點(diǎn)數(shù)的奇偶性，給出判斷點(diǎn)與多邊形拓?fù)潢P(guān)系的方法，該方法能準(zhǔn)確判斷簡單多邊形，但不能有效的應(yīng)用在復(fù)雜多邊形中［7］。陳樹強(qiáng)等將矢量與射線相結(jié)合來判斷點(diǎn)與多邊形的關(guān)系，該方法簡單、快速，但對復(fù)雜多邊形準(zhǔn)確性不高［8］。Luo Guo等人提出了4個(gè)指標(biāo)將點(diǎn)與多邊形關(guān)系應(yīng)用在土地利用中，但這些指標(biāo)有局限性，且效率不高［9］。董秀山為提高判斷點(diǎn)與多邊形位置關(guān)系時(shí)的速度，提出首先查找所有頂點(diǎn)在確定區(qū)域內(nèi)斜率最小點(diǎn)，以此作射線，該射線不穿過多邊形頂點(diǎn)的新算法，該算法效率高，但不適合多邊形頂點(diǎn)數(shù)少的情況［10］。綜上所述，較多學(xué)者從不同的角度和原理提出不同的判斷點(diǎn)是否在多邊形中的算法，部分學(xué)者則是在判斷點(diǎn)與多邊形關(guān)系現(xiàn)有算法的基礎(chǔ)上，通過改進(jìn)和擴(kuò)展提高算法準(zhǔn)確性和效率，但還不能很好解決判斷點(diǎn)與復(fù)雜多邊形關(guān)系。本文根據(jù)射線所經(jīng)過不同類型的頂點(diǎn)，提出加1加2和加3運(yùn)算改進(jìn)并擴(kuò)展了射線法，該算法的原理簡單，判斷準(zhǔn)確性高，不僅在簡單多邊形中有效，而且在不同類型的復(fù)雜多邊形中也有效。

1 基本概念

多邊形：是系列首尾相連接線段的有限集合。設(shè)多邊形為P，可以用點(diǎn)序列P0，P1，…，Pn－1，Pn＝P0表示，P0P1，P1P2，…，Pn－1Pn＝Pn－1P0是多邊形的邊，Pi（i＝0，1，…，n－1）是多邊形的頂點(diǎn)［11］。

2 射線算法基本原理

2.1 射線算法基本思想

一條射線以點(diǎn)P為起始點(diǎn)，然后延長，穿過多邊形的邊界次數(shù)稱為交點(diǎn)數(shù)目。如果交點(diǎn)數(shù)目是偶數(shù)時(shí)，則點(diǎn)P在多邊形外部；如果交點(diǎn)數(shù)目是奇數(shù)時(shí)，則點(diǎn)P在多邊形內(nèi)部［12］。在圖1中，如點(diǎn)in1和點(diǎn)out1所示。

2.2 射線算法優(yōu)缺點(diǎn)分析

圖1 簡單多邊形

在圖1中，以out1點(diǎn)為起點(diǎn)的射線延長到多邊形時(shí)經(jīng)過P1，P2，P3，P4這4個(gè)交點(diǎn)，以out2點(diǎn)為起點(diǎn)的射線與多邊形交點(diǎn)個(gè)數(shù)是0，以in1點(diǎn)為起點(diǎn)的射線與多邊形交點(diǎn)是3；根據(jù)射線法判斷out1點(diǎn)和out2點(diǎn)在多邊形的外部，in1點(diǎn)在多邊形的內(nèi)部；該算法原理簡單，思想明確，效率比較高，但存在不足：如以in2點(diǎn)為起點(diǎn)的射線與多邊形交點(diǎn)是2，則判斷該點(diǎn)位于多邊形外，與實(shí)際相矛盾。對于以下特殊的情況：①不能處理公共頂點(diǎn)，即射線與多邊形兩條邊的交點(diǎn)重合且兩條邊位于射線的同側(cè)；②不能處理帶空洞的多邊形，即射線穿過帶洞的多邊形；③不能處理過共四邊或共2n（n＞2）邊的交點(diǎn)，即射線與多邊形四條以上的邊相交而且交點(diǎn)重合；④不能處理重疊的多邊形，即射線穿過在多邊形內(nèi)部重疊的另一個(gè)多邊形。以上4種情況如果使用射線法則會(huì)得到錯(cuò)誤的結(jié)果，因此該方法存在著缺點(diǎn)。

3 射線算法的擴(kuò)展和改進(jìn)

3.1 判斷射線是否與邊界有交點(diǎn)的方法

方法1：如果邊界的兩個(gè)端點(diǎn)分別位于射線的上下兩側(cè)，也同時(shí)位于判斷點(diǎn)的右側(cè)，則射線與該邊界有交點(diǎn)［13］。在圖1中，out1點(diǎn)與邊界bc；設(shè)判斷點(diǎn)為P0（x0，y0），邊 界 的 兩 個(gè) 端 點(diǎn) 為 Pi（xi，yi）、Pi＋1（xi＋1，yi＋1）；（xi＞x0∧xi＋1＞x0）and （（yi＞y0∧yi＋1＜y0）or （yi＋1＞y0∧yi＜y0））。

方法2：如果邊界的兩個(gè)端點(diǎn)分別位于射線的上下兩側(cè)，并分別位于判斷點(diǎn)的左右兩側(cè)，則射線與邊界點(diǎn)可能有交點(diǎn)也可能沒有交點(diǎn)。在圖1中如in1點(diǎn)與邊界bc和cd的關(guān)系。如果判斷點(diǎn)與邊界點(diǎn)的下側(cè)端點(diǎn)連線的斜率小于該邊界的斜率，即邊在判斷點(diǎn)的左側(cè)，則無交點(diǎn)［13］。如果判斷點(diǎn)與邊界點(diǎn)的下側(cè)端點(diǎn)連線的斜率大于該邊界的斜率，即邊在判斷點(diǎn)的右側(cè)，則有交點(diǎn)［13］。

方法3：在最小邊界矩形方法基礎(chǔ)上，本文提出通過比較面積大小，來判斷射線與多邊形邊界是否相交。如圖2所示。

在圖2（a）中，設(shè)多邊形任意兩個(gè)端點(diǎn)為Pi和Pi＋1，由端點(diǎn)Pi和Pi＋1作最小邊界矩形 （APiBPi＋1），以P0為起始點(diǎn)的射線與邊界線相交于點(diǎn)C，與最小邊界矩形的邊相交于點(diǎn)I。在圖2（b）中，由端點(diǎn)P’i和P’i＋1作最小邊界矩形A’P’iB’P’i＋1，以P’0為起始點(diǎn)的射線與最小邊界矩形的邊相交與點(diǎn)I’。

圖2 射線與多邊形邊界關(guān)系

在圖2（a）中，多邊形P0IPi＋1的面積為S1，多邊形P0IBPi的面積S2，最小邊界矩形APiBPi＋1的面積為S。如果S／2＜ （S1＋S2），則射線與多邊形邊界有交點(diǎn)。如果S／2＝ （S1＋S2），則射線起始點(diǎn)在多邊形邊界上 （在圖2（a）中，如C為射線的起始點(diǎn)的情況）。如果S／2＞ （S1＋S2），則射線與多邊形邊界無交點(diǎn)，如圖2（b）所示：S（A’P’iB’P’i＋1）／2＞S（P’i＋1P’0I’）＋S（P’0I’B’P’i）。

3.2 判斷射線經(jīng)過的頂點(diǎn)類型的方法

設(shè)由端點(diǎn) Pi－1（xi－1，yi－1），Pi（xi，yi），Pi＋1（xi＋1，yi＋1）3個(gè)點(diǎn)構(gòu)成多邊形Pi－1PiPi＋1的三條邊界線，其中該多邊形的兩條邊界線分別是Pi－1Pi和PiPi＋1，Pi稱為多邊形的頂點(diǎn)或者兩條邊的交點(diǎn)。設(shè)P0（x0，y0）是判斷點(diǎn)。有如下4種類型：

類型1：向量 （Pi＋1－Pi）× （Pi－Pi－1）≠0，并且經(jīng)過頂點(diǎn)Pi的兩條邊界線Pi－1Pi和PiPi＋1位于射線的同側(cè)。判斷條件y0＝y(tǒng)iand（（yi－1＞y0∧yi＋1＞y0）or（yi－1＜y0∧yi＋1＜y0））。

類型2：向量 （Pi＋1－Pi）× （Pi－Pi－1）≠0，并且經(jīng)過頂點(diǎn)Pi的兩條邊界線Pi－1Pi和PiPi＋1位于射線的不同側(cè)。判斷條件y0＝y(tǒng)iand（（yi－1＞y0∧yi＋1＜y0）or（yi－1＜y0∧yi＋1＞y0））。

類型3：圖4中E，F(xiàn)，G，H，J為5個(gè)點(diǎn)，其中E，G，H，J為頂點(diǎn)。當(dāng)向量 （E－F）× （F－H）＝0并且（G－F）× （F－J）＝0時(shí)，此時(shí)F是線段EH和JG的交點(diǎn)，而不是多邊形的頂點(diǎn)。

類型4：圖4中當(dāng)C和F是多邊形KCDEFJ的頂點(diǎn)時(shí)，并且射線L’2經(jīng)過的頂點(diǎn)與其余的頂點(diǎn)組成多多邊形。如：ABC、KCDEFJ、GFH等多邊形。設(shè)頂點(diǎn)的坐標(biāo)分別為 （A（xA，yA），B（xB，yB），C（xC，yC），D（xD，yD），E（xE，yE），F(xiàn)（xF，yF），G（xG，yG），H（xH，yH），J（xJ，yJ），K（xK，yK）），起始點(diǎn) X1（x1，y1），X2（x2，y2）如下2種判斷條件：

條件1：當(dāng)多邊形的兩條邊在射線的同一側(cè)。判斷條件：y1＝y(tǒng)Cand （yA＞yC）∧ （yB＞yC）∧ （yK＜yC）∧（yD＜yC）。

條件2：當(dāng)多邊形的兩條邊界在射線的不同側(cè)。判斷條件：y2＝y(tǒng)Fand （yE＞yF）∧ （yJ＜yF）∧ （yG＞yF）∧（yH＜yF）。

算法描述：首先要計(jì)算點(diǎn)是否在多邊形的任何一條邊界上，如果點(diǎn)不在邊界上時(shí)，則以該點(diǎn)為起點(diǎn)，沿平行于x軸的方向作射線l，并且l與多邊形邊界相交，射線方程表示為其中u＞＞0。

假設(shè)u＞＞0，存在如下4種情況：

情況1：當(dāng)射線不與多邊形邊界重合并且經(jīng)過多邊形的某個(gè)頂點(diǎn) （射線經(jīng)過多邊形兩條邊界的交點(diǎn)）：如果連接該頂點(diǎn)的兩條邊在射線的同一側(cè) （如圖3的L2過點(diǎn)d），則交點(diǎn)數(shù)加1；如果連接該頂點(diǎn)的兩條邊不在射線的同一側(cè) （如圖3中L2過點(diǎn)f），則交點(diǎn)數(shù)加2。

圖3 復(fù)雜多邊形

情況2：如果射線與多邊形的某條邊重合，如圖3所示，射線L3經(jīng)過邊界線段hq，則將重合線看作一個(gè)交點(diǎn)I，然后確定與重合線段兩個(gè)端點(diǎn) （h，q）相連的線段與射線的位置關(guān)系，由情況1的方法計(jì)算交點(diǎn)數(shù)。

情況3：在多邊形中，如果連接該頂點(diǎn)共有四條邊，當(dāng)任意能組成多邊形的兩條邊分別位于射線的同一側(cè)時(shí)如：AC和BC，KC和DC （如圖4中L’1過點(diǎn)C），則交點(diǎn)數(shù)加1。當(dāng)任意能組成多邊形的兩條邊分別位于射線的不同側(cè)時(shí)如：EF和JF，GF和HF （如圖4中L’2過點(diǎn)F），則交點(diǎn)數(shù)加3。

圖4 多多邊形

情況4：在多邊形中，當(dāng)連接該頂點(diǎn)共有2n（n＞2）條邊，并組成多個(gè)多邊形時(shí) （如圖5中由V7V8V9、V1V2V9、V5V6V9和V3V4V9這4個(gè)三角形組成），此時(shí)只需考慮過該頂點(diǎn)的射線所穿過的部分多邊形 （如圖5所示，L1穿過V7V8V9和V3V4V9兩個(gè)三角形，從而簡化為上面的情況3；當(dāng)射線只過頂點(diǎn)，不穿過部分多邊形時(shí) （如L1過三角形V1V2V9和V5V6V9的公共點(diǎn)V9），則交點(diǎn)數(shù)加1。且該算法適用于帶有空洞的復(fù)雜多邊形 （如圖3多邊形Mb）。

圖5 復(fù)雜多多邊形

本文判斷算法的計(jì)算模型：設(shè)Ci表示初始的交點(diǎn)數(shù)目；Ii表示射線與多邊形邊界的交點(diǎn)；TVs表示位于射線同側(cè)的兩條邊的交點(diǎn)組成的頂點(diǎn)類型，Vs表示同側(cè)的頂點(diǎn)數(shù)目；TVd＝2表示位于射線不同側(cè)的兩條邊的交點(diǎn)組成的頂點(diǎn)類型，Vd1表示不同側(cè)的頂點(diǎn)數(shù)目；TVd≥4表示多邊形中至少四條邊的交點(diǎn)組成的頂點(diǎn)類型，Vd2表示該類型頂點(diǎn)的數(shù)目。V∞表示將射線與邊重合部分看成的一個(gè)頂點(diǎn)，TV∞表示該頂點(diǎn)的類型。射線與邊有重合，則初始化時(shí)重合部分的交點(diǎn)數(shù)為∞。其中Ci＝Ii＋Vs＋Vd1＋Vd2，Vs ＝ NUM（TVs），Vd1＝NUM（TVd＝2），Vd1＝NUM（TVd≥4），Ni＝Ci＋∞ ，Ni，Ci，Ii，Vs，Vd1，Vd2∈ （1，2，...，n），V∞ ＝1。NUM（）是計(jì)算該類頂點(diǎn)數(shù)的函數(shù)

3.3 判斷點(diǎn)與多邊形的位置關(guān)系算法 （JP－ALA）

考慮的文章的篇幅，本文給出了算法的偽代碼：

輸入：組成多邊形S的閉曲線L＜p1，p2，…，pn，p1＞，目標(biāo)點(diǎn)P0（x0，y0）。

輸出：點(diǎn)P0在多邊形內(nèi)部，點(diǎn)P0在多邊形邊界，點(diǎn)P0在多邊形外部。

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

步驟1 初始化以P0為起始點(diǎn)作一條射線l延長至無窮遠(yuǎn)。

步驟2 if射線l與多邊形的某一條邊pipi＋1不重合then計(jì)算射線l與多邊形所有邊的交點(diǎn)個(gè)數(shù)為N。并標(biāo)記所有交點(diǎn) TVi（i＝1，2，…，n）的類型 TVi∈ ｛TVs，TVd＝2，TVd＞＝4｝。

步驟3 if射線l與多邊形的邊界pipi＋1重合then計(jì)算射線l與多邊形所有未重合邊界的交點(diǎn)個(gè)數(shù)為N，將重合的線段看成一個(gè)點(diǎn)，N＝N＋1，并且標(biāo)識該點(diǎn)TVi的類型。

步驟4 if P0在多邊形的邊界上then P0在邊界上；算法結(jié)束。

步驟5 if射線沒有經(jīng)過多邊形的某個(gè)頂點(diǎn)then A1（）else M＝N，執(zhí)行循環(huán)體。

Do

循環(huán)次數(shù)從1開始累加

步驟6 if射線經(jīng)過的點(diǎn)是多邊形相鄰兩條邊的一個(gè)交點(diǎn) （或多邊形頂點(diǎn)）時(shí)then

if連接該頂點(diǎn)的兩條邊在射線的同一側(cè)then N＝N＋1；

if連接該頂點(diǎn)的兩條邊分別在射線的不同側(cè)thenN＝N＋2；

步驟7 if射線經(jīng)過的某一點(diǎn)是由2n（n＝2）條多邊形邊界相交后的一個(gè)交點(diǎn)時(shí)then

if能組成多邊形的任意兩條邊分別位于射線的同一側(cè)時(shí)then N＝N＋1；

if能組成不同多邊形的任意兩條邊分別位于射線的兩側(cè)時(shí)then N＝N＋3；

步驟8 if射線經(jīng)過的某一點(diǎn)是由2n（n＞2）條多邊形邊界相交后的一個(gè)交點(diǎn)時(shí)then

if射線只過頂點(diǎn)不穿過多邊形的某一部分then N＝N＋1；

if射線穿過多邊形的某部分then保留射線穿過的部分多邊形 （如圖5所示三角形V7V8V9和三角形V3V4V9），根據(jù)穿過的多邊形重新標(biāo)記該交點(diǎn)的類型，執(zhí)行步驟9；

步驟9 根據(jù)不同點(diǎn)類型，當(dāng)標(biāo)記為單頂點(diǎn)goto步驟6，標(biāo)記為多條邊相交的頂點(diǎn)，if n＝2 thengoto步驟7 else goto步驟8；

While循環(huán)次數(shù)＜＝M

步驟10 當(dāng)循環(huán)次數(shù)大于M時(shí)，退出循環(huán)，調(diào)用函數(shù)A1（）。

4 4種不同判定算法執(zhí)行結(jié)果對比分析

在圖3中，本文算法分別與文獻(xiàn) ［12］算法、文獻(xiàn)［13］算法和文獻(xiàn) ［7］的算法對比分析見表1。

表1 針對圖3的4種算法的對比分析結(jié)果

（1）L1經(jīng)過3個(gè)頂點(diǎn)a，c，e初始交點(diǎn)數(shù)Ci＝3，并且分別連接這3個(gè)頂點(diǎn)的兩條邊都是位于射線L1的同一側(cè)。文獻(xiàn) ［12］的算法交點(diǎn)數(shù)為3，判斷X1在多邊形的內(nèi)部，與實(shí)際情況不符；文獻(xiàn) ［13］和文獻(xiàn) ［7］的算法交點(diǎn)數(shù)為偶數(shù)，則X1在多邊形的外部；本文的算法，計(jì)算交點(diǎn)數(shù)Cnt＝Ci＋3＊1＝6，則X1在多邊形的外部，與實(shí)際情況相符。

（2）L2與多邊形的有兩個(gè)初始交點(diǎn)d，f，Ci＝2，其中連接頂點(diǎn)d的兩條邊位于射線同側(cè)，連接f的兩條邊位于射線的兩側(cè)。文獻(xiàn) ［12］的算法交點(diǎn)數(shù)為2，則X2在多邊形的外部，與實(shí)際情況不符；文獻(xiàn) ［13］和文獻(xiàn) ［7］的算法判斷X2在多邊形的內(nèi)部；本文的算法，計(jì)算交點(diǎn)數(shù)Cnt＝Ci＋1＊1＋1＊2＝5，判斷X2在內(nèi)部，與實(shí)際相符。

（3）L3與多邊形的邊重合，文獻(xiàn) ［12］和文獻(xiàn) ［7］的算法無法判斷。文獻(xiàn) ［13］算法和本文算法先簡化為一個(gè)交點(diǎn)，本文算法先根據(jù)計(jì)算模型，判斷X3在多邊形內(nèi)部，與實(shí)際相符。

（4）L4與多邊形的初始交點(diǎn)數(shù)Ci＝4，有3個(gè)頂點(diǎn)位于射線的同一側(cè)。文獻(xiàn) ［12］的算法判斷X4在多邊形的外部，與實(shí)際不符；文獻(xiàn) ［13］的算法和文獻(xiàn) ［7］的算法判斷X4在多邊形內(nèi)部，本文的算法計(jì)算交點(diǎn)數(shù)Cnt＝Ci＋3＊1＝7，則X4在多邊形的內(nèi)部，與實(shí)際相符。

（5）L5初始交點(diǎn)數(shù)為6，文獻(xiàn) ［1］算法判斷X5在多邊形的外部，與實(shí)際不符；文獻(xiàn) ［12］的算法和文獻(xiàn) ［7］算法判斷X5在多邊形的內(nèi)部；本文的算法計(jì)算交點(diǎn)數(shù)Cnt＝Ci＋1＊1＋1＊2＝9，判斷X5在多邊形內(nèi)部，與實(shí)際相符。

（6）L6初始交點(diǎn)數(shù)為3，文獻(xiàn) ［12］算法判斷X6在多邊形的內(nèi)部，與實(shí)際不符；文獻(xiàn) ［13］算法和文獻(xiàn) ［7］算法判斷X6在多邊形的外部；本文的算法計(jì)算交點(diǎn)數(shù)Cnt＝Ci＋1＊1＋1＊2＝6，判斷X6在多邊形外部，與實(shí)際相符。

在圖4中，本文算法分別與文獻(xiàn) ［12］算法、文獻(xiàn)［13］的算法和文獻(xiàn) ［7］的算法對比分析見表2。

表2 針對圖4的4種算法的對比分析結(jié)果

（1）L’1初始交點(diǎn)數(shù)為1。文獻(xiàn) ［12］的算法和文獻(xiàn)［7］算法判斷X1在多邊形內(nèi)部，與實(shí)際都不相符；文獻(xiàn)［13］算法判斷X1在多邊形外部；本文算法計(jì)算交點(diǎn)數(shù)Cnt＝Ci＋1＊1＝2，判斷X1在多邊形外部，與實(shí)際相符。

（2）L’2初始交點(diǎn)數(shù)為3。文獻(xiàn) ［12］算法判斷X2在多邊形的內(nèi)部；文獻(xiàn) ［13］算法和文獻(xiàn) ［7］算法判斷X2在多邊形外部，與實(shí)際不相符；本文算法計(jì)算交點(diǎn)Cnt＝Ci＋1＊1＋1＊3＝7，判斷X2在多邊形內(nèi)部，與實(shí)際相符。

在圖5中，本文算法分別與文獻(xiàn) ［12］的算法、文獻(xiàn)［13］的算法和文獻(xiàn) ［7］的算法對比分析見表3。

表3 針對圖5的4種算法的對比分析結(jié)果

L1過公共頂點(diǎn)V9，穿過多邊形為V7V8V9V3V4，可簡化為V7V8V9和V3V4V9兩個(gè)三角形，初始交點(diǎn)Ci＝2，文獻(xiàn) ［12］算法、文獻(xiàn) ［13］算法和文獻(xiàn) ［7］算法判斷P在多邊形的外部，與實(shí)際都不相符；本文的算法按類別 （3）處理，計(jì)算交點(diǎn)數(shù)Cnt＝Ci＋1＊3＝5，判斷P在多邊形的內(nèi)部，與實(shí)際相符。

從以上算法可知，文獻(xiàn) ［1］算法完全不適于圖3的空間分布，文獻(xiàn) ［13］算法可處理重合線段，文獻(xiàn) ［12］和文獻(xiàn) ［7］算法對重合線段無法判斷。針對圖4，文獻(xiàn)［12］、文獻(xiàn) ［13］和文獻(xiàn) ［7］算法都只能正確判斷部分的點(diǎn)與多邊形的位置關(guān)系。針對圖5，文獻(xiàn) ［12］、文獻(xiàn) ［13］和文獻(xiàn) ［7］的算法都判斷錯(cuò)誤。本文的算法能克服文獻(xiàn)［12］算法、文獻(xiàn) ［13］算法和文獻(xiàn) ［7］算法對以上幾種特殊情況判斷錯(cuò)誤而存在的不足，能廣泛的應(yīng)用于各種不同的多邊形。既對簡單多邊形有效，也對復(fù)雜多邊形有效，并且能準(zhǔn)確地判斷出點(diǎn)與多邊形的位置關(guān)系。

5 結(jié)束語

在現(xiàn)有射線法研究的基礎(chǔ)上，本文提出對頂點(diǎn)加1加2和加3運(yùn)算，改進(jìn)并擴(kuò)展了射線法。該方法首先是分析射線與多邊形的邊相交的各種情況，然后采用簡單的加運(yùn)算計(jì)算交點(diǎn)數(shù)以及分析對不同的交點(diǎn)類型進(jìn)行加運(yùn)算，最后使用交點(diǎn)數(shù)的奇偶性來判斷點(diǎn)與多邊形的位置關(guān)系。4種不同算法分析結(jié)果表明，該方法不僅適用簡單的多邊形，也適合各種類型的復(fù)雜多邊形，而且能準(zhǔn)確判斷點(diǎn)與多邊形的位置關(guān)系。雖然該方法的預(yù)處理要花費(fèi)一些時(shí)間，而且預(yù)處理時(shí)間由于與實(shí)驗(yàn)數(shù)據(jù)的質(zhì)量和運(yùn)行環(huán)境有較大關(guān)系，算法的時(shí)間復(fù)雜度難以確定，但預(yù)處理的結(jié)果都會(huì)被作為判斷條件而反復(fù)使用，在應(yīng)用中有利于提高實(shí)際效率，對GIS空間分析和實(shí)際應(yīng)用都有積極的意義，對算法效率的深入研究是下一步的主要工作。

［1］JIANG Ping，LIU Minshi.Improved ray method to judge the relation of point and polygon including simple cure ［J］.Science of Surveying and Mapping，2009，34 （5）：220－222 （in Chinese）.［江平，劉民士.射線法判斷點(diǎn)與包含簡單曲線多邊形關(guān)系的完善 ［J］.測繪科學(xué)，2009，34 （5）：220－222.］

［2］Yang Sheng，Yong Junhai.A point－in－polygon method based on a quasi－closest point ［J］.Computers＆ Geosciences，2010，36 （2）：205－213.

［3］Juan J Jime′nez，F(xiàn)rancison R Feito.A new hierarchical triangle－based point－in－polygon data structure ［J］.Computers ＆Geosciences，2009，35 （9）：1483－1583.

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

［5］Jing Li，Wang Wencheng.Point－in－polygon tests by convex decomposition［J］.Computers ＆ Graphics，2007，31 （4）：636－648.

［6］LI Nan，XIAO Keyan.Improved judgment algorithm of point in－out polygon ［J］.Computer Engineering，2012，33 （5）：30－34（in Chinese）.［李楠，肖克炎.一種改進(jìn)的點(diǎn)在多邊形內(nèi)外判斷算法 ［J］.計(jì)算機(jī)工程，2012，38 （5）：30－34.］

［7］LIU Yabin，LIU Dayou.Reasoning of topology spatial objects in GIS ［J］.Journal of Software，2001，12 （12）：1859－1863 （in Chinese）.［劉亞彬，劉大有.地理信息系統(tǒng)中空間對象間拓?fù)潢P(guān)系的推理 ［J］.軟件學(xué)報(bào)，2001，12 （12）：1859－1863.］

［8］CHEN Shuqiang，CHEN Xuegong.A new method deciding whether a point is in a polygon ［J］.Microelectronics and Computer，2006，23 （8）：194－195 （in Chinese）.［陳樹強(qiáng)，陳學(xué)工.判定檢測點(diǎn)是否在多邊形內(nèi)的新方法 ［J］.微電子學(xué)與計(jì)算機(jī)，2006，23 （8）：194－195.］

［9］Luo Guo，Shihong Du.Global and local indicators of spatial association between points and polygons：A study of land use change ［J］.International Journal of Applied Earth Observation and Geoinformation，2013，21：384－396.

［10］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）.［董秀山，劉潤濤.判斷點(diǎn)與簡單多邊形位置關(guān)系的新算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 （2）：185－186.］

［11］XIA Renbo，LIU Weijun.Method for determing whether a certain point is inside a polygon in plane ［J］.Chinese Journal of Mechanical Engineering，2006，42 （3）：130－135 （in Chinese）.［夏仁波，劉偉軍.點(diǎn)在平面多邊形內(nèi)外的判斷方法［J］.機(jī)械工程學(xué)報(bào)，2006，42 （3）：130－134.］

［12］ZHANG Hong，WEN Yongning.The basic algorithm of geography information system ［M］.Beijing：Science Press，2006：25－30 （in Chinese）.［張宏，溫永寧.地理信息系統(tǒng)算法基礎(chǔ) ［M］.北京：科學(xué)出版社，2006：25－30.］

［13］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.］