判斷點與多邊形拓?fù)潢P(guān)系的改進(jìn)算法

向 俊，王 靜，夏幼明

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

0 引 言

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

1 基本概念

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

2 射線算法基本原理

2.1 射線算法基本思想

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

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

圖1 簡單多邊形

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

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

3.1 判斷射線是否與邊界有交點的方法

方法1：如果邊界的兩個端點分別位于射線的上下兩側(cè)，也同時位于判斷點的右側(cè)，則射線與該邊界有交點［13］。在圖1中，out1點與邊界bc；設(shè)判斷點為P0（x0，y0），邊 界 的 兩 個 端 點 為 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：如果邊界的兩個端點分別位于射線的上下兩側(cè)，并分別位于判斷點的左右兩側(cè)，則射線與邊界點可能有交點也可能沒有交點。在圖1中如in1點與邊界bc和cd的關(guān)系。如果判斷點與邊界點的下側(cè)端點連線的斜率小于該邊界的斜率，即邊在判斷點的左側(cè)，則無交點［13］。如果判斷點與邊界點的下側(cè)端點連線的斜率大于該邊界的斜率，即邊在判斷點的右側(cè)，則有交點［13］。

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

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

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

在圖2（a）中，多邊形P0IPi＋1的面積為S1，多邊形P0IBPi的面積S2，最小邊界矩形APiBPi＋1的面積為S。如果S／2＜ （S1＋S2），則射線與多邊形邊界有交點。如果S／2＝ （S1＋S2），則射線起始點在多邊形邊界上 （在圖2（a）中，如C為射線的起始點的情況）。如果S／2＞ （S1＋S2），則射線與多邊形邊界無交點，如圖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)過的頂點類型的方法

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

類型1：向量 （Pi＋1－Pi）× （Pi－Pi－1）≠0，并且經(jīng)過頂點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)過頂點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個點，其中E，G，H，J為頂點。當(dāng)向量 （E－F）× （F－H）＝0并且（G－F）× （F－J）＝0時，此時F是線段EH和JG的交點，而不是多邊形的頂點。

類型4：圖4中當(dāng)C和F是多邊形KCDEFJ的頂點時，并且射線L’2經(jīng)過的頂點與其余的頂點組成多多邊形。如：ABC、KCDEFJ、GFH等多邊形。設(shè)頂點的坐標(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）），起始點 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）。

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

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

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

圖3 復(fù)雜多邊形

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

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

圖4 多多邊形

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

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

本文判斷算法的計算模型：設(shè)Ci表示初始的交點數(shù)目；Ii表示射線與多邊形邊界的交點；TVs表示位于射線同側(cè)的兩條邊的交點組成的頂點類型，Vs表示同側(cè)的頂點數(shù)目；TVd＝2表示位于射線不同側(cè)的兩條邊的交點組成的頂點類型，Vd1表示不同側(cè)的頂點數(shù)目；TVd≥4表示多邊形中至少四條邊的交點組成的頂點類型，Vd2表示該類型頂點的數(shù)目。V∞表示將射線與邊重合部分看成的一個頂點，TV∞表示該頂點的類型。射線與邊有重合，則初始化時重合部分的交點數(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（）是計算該類頂點數(shù)的函數(shù)

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

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

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

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

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

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

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

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

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

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

Do

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

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

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

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

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

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

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

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

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

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

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

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

步驟10 當(dāng)循環(huán)次數(shù)大于M時，退出循環(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個頂點a，c，e初始交點數(shù)Ci＝3，并且分別連接這3個頂點的兩條邊都是位于射線L1的同一側(cè)。文獻(xiàn) ［12］的算法交點數(shù)為3，判斷X1在多邊形的內(nèi)部，與實際情況不符；文獻(xiàn) ［13］和文獻(xiàn) ［7］的算法交點數(shù)為偶數(shù)，則X1在多邊形的外部；本文的算法，計算交點數(shù)Cnt＝Ci＋3＊1＝6，則X1在多邊形的外部，與實際情況相符。

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

在現(xiàn)有射線法研究的基礎(chǔ)上，本文提出對頂點加1加2和加3運(yùn)算，改進(jìn)并擴(kuò)展了射線法。該方法首先是分析射線與多邊形的邊相交的各種情況，然后采用簡單的加運(yùn)算計算交點數(shù)以及分析對不同的交點類型進(jìn)行加運(yùn)算，最后使用交點數(shù)的奇偶性來判斷點與多邊形的位置關(guān)系。4種不同算法分析結(jié)果表明，該方法不僅適用簡單的多邊形，也適合各種類型的復(fù)雜多邊形，而且能準(zhǔn)確判斷點與多邊形的位置關(guān)系。雖然該方法的預(yù)處理要花費一些時間，而且預(yù)處理時間由于與實驗數(shù)據(jù)的質(zhì)量和運(yùn)行環(huán)境有較大關(guān)系，算法的時間復(fù)雜度難以確定，但預(yù)處理的結(jié)果都會被作為判斷條件而反復(fù)使用，在應(yīng)用中有利于提高實際效率，對GIS空間分析和實際應(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）.［江平，劉民士.射線法判斷點與包含簡單曲線多邊形關(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）. ［劉梁.點、多邊形拓?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)的點在多邊形內(nèi)外判斷算法 ［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é)報，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é)工.判定檢測點是否在多邊形內(nèi)的新方法 ［J］.微電子學(xué)與計算機(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）.［董秀山，劉潤濤.判斷點與簡單多邊形位置關(guān)系的新算法 ［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）.［夏仁波，劉偉軍.點在平面多邊形內(nèi)外的判斷方法［J］.機(jī)械工程學(xué)報，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）.［陳瑞卿，周健，虞烈.一種判斷點與多邊形關(guān)系的快速算法 ［J］.西安交通大學(xué)學(xué)報，2007，41 （1）：59－63.］