陳希

（公安部第一研究所，北京 100048）

點(diǎn)在多邊形內(nèi)的檢測(cè)在模式識(shí)別、計(jì)算機(jī)圖形學(xué)等方面有很廣泛的應(yīng)用。對(duì)于點(diǎn)在多邊形內(nèi)的檢測(cè)，已經(jīng)有大量的研究成果[1-5]，經(jīng)典的算法有叉積判斷法、夾角之和判斷法[1]，有向三角形面積之和的符號(hào)法[2]、射線法[3]，有向回路法和網(wǎng)格法[4]等。其中，使用最為普遍的方法之一就是射線法。射線法適用于大部分場(chǎng)景，但是在交點(diǎn)包含多邊形頂點(diǎn)時(shí)，可能會(huì)造成判斷不準(zhǔn)確的情況。

生活中利用點(diǎn)在多邊形內(nèi)的案例比比皆是，例如如今高德、百度地圖根據(jù)用戶定位自動(dòng)切換室外導(dǎo)航和室內(nèi)導(dǎo)航模式，公安行業(yè)需要按地域管控巡邏力量等。但是生活中的區(qū)域多數(shù)情況下并不是正規(guī)的多邊形，利用射線定理時(shí)，對(duì)選中的射線要求很高，如果從目標(biāo)點(diǎn)引出的射線經(jīng)過多邊形頂點(diǎn)，很有可能會(huì)出現(xiàn)誤判。本文將給出一種普適的射線定理修正算法，并給出理論上的證明。

本文對(duì)射線法從幾何學(xué)角度給出了一種證明方法，基本思想就是將任意多邊形分割為有限個(gè)三角形，然后通過證明點(diǎn)在某一個(gè)分割的三角形內(nèi)，從而證明點(diǎn)在多邊形內(nèi)。

1 基本概念

1.1 多邊形

由在同一平面且不在同一直線上的3條或3條以上的線段首尾順次連接且不相交所組成的封閉圖形叫作“多邊形”。

1.2 凹多邊形

如果在一個(gè)多邊形的所有邊中，有一條邊向兩方無限延長(zhǎng)成為一直線時(shí)，其他各邊不都在此直線的同旁，那么這個(gè)多邊形就叫作“凹多邊形”，其內(nèi)角中至少有一個(gè)鈍角。

1.3 凸多邊形

如果把一個(gè)多邊形的所有邊中，任意一條邊向兩方無限延長(zhǎng)成為一直線，其他各邊都在此直線的同旁，那么這個(gè)多邊形就叫做“凸多邊形”，其內(nèi)角應(yīng)該全不是鈍角，任意兩個(gè)頂點(diǎn)間的線段位于多邊形的內(nèi)部或邊上。

1.4 射線定理

畫一條經(jīng)過待判別點(diǎn)P的直線L，為簡(jiǎn)單起見，L取為平行于X軸的直線。將L與多邊形A的所有交點(diǎn)記錄下來，并以點(diǎn)P為界，分為在點(diǎn)P左側(cè)和點(diǎn)P右側(cè)兩部分。如果兩部分交點(diǎn)的集合中，交點(diǎn)個(gè)數(shù)的數(shù)目都是奇數(shù)，說明點(diǎn)P在多邊形A內(nèi)。由于多邊形的對(duì)稱性（對(duì)于點(diǎn)來說，左邊和右邊沒有區(qū)別），射線定理可以簡(jiǎn)化為，左側(cè)交點(diǎn)個(gè)數(shù)為奇數(shù)，即可證明點(diǎn)P在多邊形A內(nèi)。

1.5 點(diǎn)O在△ABC內(nèi)部的一個(gè)充要條件

2 證明思路

根據(jù)以上定義可以知道，將多邊形分解為有限個(gè)互不重疊的三角形，如果點(diǎn)在多邊形內(nèi)，那么必在某個(gè)三角形內(nèi)。證明射線定理即轉(zhuǎn)化為，如果點(diǎn)在某個(gè)三角形內(nèi)，與滿足射線定理是充要條件即可。

3 點(diǎn)在三角形內(nèi)的檢測(cè)

3.1 交點(diǎn)不經(jīng)過三角形的任意一個(gè)頂點(diǎn)

自定義一個(gè)坐標(biāo)系，使得待檢測(cè)點(diǎn)P（0，0）為坐標(biāo)原點(diǎn)，同時(shí)三角形S的任意一條邊不與X軸和Y軸平行或垂直。經(jīng)過點(diǎn)P，引一條直線y＝0，與三角形S相交于2個(gè)點(diǎn)A1（a，0）和A2（b，0），其中，a＜b.對(duì)于交點(diǎn)，可能出現(xiàn)以下3種情況：①A1和A2在點(diǎn)P的一側(cè)，即a·b＞0；②P與A1或者A2之一重合，即a·b＝0；③A1和A2在點(diǎn)P的兩側(cè)，即a·b＜0.顯然，對(duì)于第2種情況，可以知道點(diǎn)P在三角形S上；對(duì)于第1種情況，假設(shè)A1和A2都在P點(diǎn)右側(cè)，即a＞0且b＞0，示意圖如圖1所示。

圖1 第1種情況的示意圖

由式（2）可以得到：

將式（3）代入式（1）可得-x＝ma+kb-x（m+k），化簡(jiǎn)后可得0＝ma+kb.由于ab＞0，m+k＝1，且m，k＞0，顯然式（1）和式（2）不能同時(shí)成立，所以點(diǎn)P在△ABC外部。同理可證，當(dāng)A1和A2在點(diǎn)P左側(cè)時(shí)，點(diǎn)P也在△ABC外部。對(duì)于第3種情況，ab＜0時(shí)，由假設(shè)可得，b＞0，a點(diǎn)P在三角形內(nèi)?射線定理對(duì)于三角形適用。

3.2 交點(diǎn)經(jīng)過至少一個(gè)頂點(diǎn)

3．2．1 交點(diǎn)經(jīng)過三角形的一個(gè)頂點(diǎn)

該情況具體可以分為如下2種：

第1種：除去相交的頂點(diǎn)外，其他2個(gè)頂點(diǎn)在射線的同一側(cè)，示意圖如圖2所示。

圖2 2個(gè)頂點(diǎn)在射線的同一側(cè)

圖3 2個(gè)頂點(diǎn)在射線的兩側(cè)

由圖2可知，顯然此時(shí)P與△ABC是不相交的。

第2種：除去相交的頂點(diǎn)外，其他2個(gè)頂點(diǎn)在射線的兩側(cè)，示意圖如圖3所示。

在這種情況下，可以按照第1種情況中給出的方法來判斷點(diǎn)P是否在三角形內(nèi)。

3．2．2 交點(diǎn)經(jīng)過三角形的2個(gè)頂點(diǎn)

假設(shè)在自定義坐標(biāo)系中，點(diǎn)P（0，0）為原點(diǎn)，射線y＝0，x≥0經(jīng)過三角形的2個(gè)頂點(diǎn)B（a，0）、C（b，0），此時(shí)只要判斷B和C是否在點(diǎn)P的兩側(cè)即可，即如果a·b＞0，則P不在三角形內(nèi)；如果a·b≤0，則P在三角形內(nèi)。

4 點(diǎn)在多邊形內(nèi)的檢測(cè)

4.1 任意多邊形可分解為有限個(gè)互不重疊的三角形

顯然，四邊形可以分解為2個(gè)互不重疊的三角形。下面采用歸納法證明命題。假設(shè)邊數(shù)為k（k＞3）的多邊形A1A2…Ak，可以分解為m個(gè)互不重疊的三角形，那么對(duì)于k+1邊形A1A2…AkAk+1，將Ak+1與k邊形A1A2…Ak中距離Ak+1最近的一條邊AxAy（x，y∈[1，k]，且x≠y)相連接，得到△AxAyAk+1，顯然k+1邊形可以分解為k邊形A1A2…Ak和△AxAyAk+1，且△AxAyAk+1與k邊形A1A2…Ak互不重疊。由假設(shè)可知，k邊形A1A2…Ak可以分解為m個(gè)互不重疊的三角形，所以k+1邊形可以分解為m+1個(gè)互不重疊的三角形，命題得證。

4.2 射線定理在多邊形上成立

由點(diǎn)a1，a2，…，am組成的多邊形S，做一條起點(diǎn)為P，平行于X軸的射線L，與多邊形S交點(diǎn)分別為b1，b2，…，bk，以多邊形S的各邊為劃分依據(jù)（即盡量讓所有三角形都至少有一條邊在多邊形S的邊上），將S分解為互不重合的三角形集合S1，S2，…，Sn.在射線L不經(jīng)過多邊形S頂點(diǎn)的情況下，如果P在某一三角形Sx內(nèi)，那么L與這些三角形集合在點(diǎn)P右側(cè)的交點(diǎn)個(gè)數(shù)總和一定為奇數(shù)。下面討論L與在Sx右側(cè)的三角形交點(diǎn)為S頂點(diǎn)的情況。

假設(shè)交點(diǎn)為ax（1≤x≤m),獲取ax的前后2個(gè)點(diǎn)ax-1和ax+1，判斷ax-1和ax+1是否在點(diǎn)P垂直方向的兩側(cè).如果ax-1和ax+1在點(diǎn)P垂直方向的兩側(cè)，那么該交點(diǎn)算入與L交點(diǎn)的個(gè)數(shù)之中；否則，舍棄該交點(diǎn)。

證明過程如下：由于ax-1和ax+1在P點(diǎn)同側(cè)，如果ax-1和ax+1中沒有任意一個(gè)與P點(diǎn)縱坐標(biāo)相同，由第3部分證明可知，點(diǎn)P一定不在△ax-1axax+1之中，所以如果△ax-1axax+1在S之中，那么去掉也不會(huì)影響點(diǎn)P在S中的存在性。同理，如果△ax-1axax+1不在S中，那么將△ax-1axax+1加入S也不會(huì)影響點(diǎn)P在S中的存在性。不管添加或者刪除△ax-1axax+1，最后的結(jié)果都是，可以去除交點(diǎn)ax的統(tǒng)計(jì)。

如果ax-1和ax+1中有一個(gè)與點(diǎn)P的縱坐標(biāo)相同，假設(shè)ax+1與點(diǎn)P的縱坐標(biāo)相同，由第3部分證明可知，只需比較

ax和ax+1與點(diǎn)P的橫坐標(biāo)，即可知點(diǎn)P是否在△ax-1axax+1內(nèi)。如果點(diǎn)P不在△ax-1axax+1內(nèi)，那么去除交點(diǎn)ax的統(tǒng)計(jì)。

5 算法實(shí)現(xiàn)過程

假設(shè)點(diǎn)P坐標(biāo)為（x，y）：①將n邊形各頂點(diǎn)坐標(biāo)按順序排列，各頂點(diǎn)坐標(biāo)為 Ai（ai，bi），i∈[1，n]，其中，A1的前置坐標(biāo)為An，An的后置坐標(biāo)為A1.②初始化交點(diǎn)計(jì)數(shù)器count為 0.③從第一個(gè)頂點(diǎn)開始依次比較Ai（ai，bi）、Ai+1（ai+1，bi+1）與 P（x0，y0）。④判斷ai和 ai+1是否都小于x0.如果是，直接進(jìn)入下一次循環(huán)。⑤判斷y0與bk是否相等（k＝i或者i+1）。如果相等，那么判斷y0是否在bk-1和bk+1之間，如果是，count加1；如果不相等，判斷bi和bi+1是否在y0的一側(cè)，如果不是，計(jì)算射線y＝y(tǒng)0，x≥x0與線段AiAi+1的交點(diǎn)。如果有交點(diǎn)，count加1.⑥循環(huán)進(jìn)行第4步和第5步，直到遍歷完所有的頂點(diǎn)。此時(shí)，count如果為奇數(shù)，那么點(diǎn)P在多邊形內(nèi)；否則，點(diǎn)P在多邊形外。

6 射線定理在公安業(yè)務(wù)中的運(yùn)用

6.1 越界報(bào)警功能

新疆公安系統(tǒng)中有轄區(qū)的概念，即任意一個(gè)公安局或者派出所都有自己的責(zé)任范圍。公安局和派出所每天會(huì)安排部分警力在自己的轄區(qū)內(nèi)進(jìn)行巡邏，巡邏警力身上會(huì)佩戴定位設(shè)備，實(shí)時(shí)回傳當(dāng)前的位置信息。

在新疆一體化指揮調(diào)度系統(tǒng)中，加入了越界報(bào)警功能，即實(shí)時(shí)判斷當(dāng)前設(shè)備所在的位置（點(diǎn)），是否在所屬公安局或派出所的轄區(qū)范圍（多邊形）內(nèi)，一旦越界，將在后臺(tái)進(jìn)行記錄，同時(shí)平臺(tái)將發(fā)送提醒信息給越界的設(shè)備。

6.2 區(qū)域范圍內(nèi)查詢地圖圖層

新疆PGIS平臺(tái)中可以查詢指定區(qū)域中的圖層信息，并將查詢結(jié)果展示在地圖上。其實(shí)現(xiàn)過程是，將查詢出的帶位置信息的圖層實(shí)例與指定區(qū)域進(jìn)行比對(duì)，如果圖層實(shí)例在指定區(qū)域中，則在地圖上顯示出來。

［1］孫家廣，楊長(zhǎng)貴.計(jì)算機(jī)圖形學(xué)［M］.北京：清華大學(xué)出版社，1995：388-393.

［2］Feito F，Torres J C，Urena A.Orientation，simplicity，and inclusion test for planar polygons.Computers&Graphics，1995，19（4）：595-600.

［3］周培德.計(jì)算幾何——算法設(shè)計(jì)與分析［M］.第2版.北京：清華大學(xué)出版社，2005：20-24.

［4］郭雷，王洵，王曉蒲.有向回路法和網(wǎng)格法：多邊形內(nèi)外點(diǎn)判別的新算法［J］.計(jì)算機(jī)工程與應(yīng)用，2002（19）：119-122.

［5］易正紅.點(diǎn)在三角形區(qū)域中的一個(gè)充要條件及應(yīng)用［J］.福建中學(xué)數(shù)學(xué)，2012（9）：40-41.