射線定理的證明和在公安中的運用

陳希

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

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

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

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

1 基本概念

1.1 多邊形

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

1.2 凹多邊形

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

1.3 凸多邊形

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

1.4 射線定理

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

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

2 證明思路

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

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

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

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

圖1 第1種情況的示意圖

由式（2）可以得到：

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

3.2 交點經(jīng)過至少一個頂點

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

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

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

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

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

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

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

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

3．2．2 交點經(jīng)過三角形的2個頂點

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

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

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

顯然，四邊形可以分解為2個互不重疊的三角形。下面采用歸納法證明命題。假設(shè)邊數(shù)為k（k＞3）的多邊形A1A2…Ak，可以分解為m個互不重疊的三角形，那么對于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個互不重疊的三角形，所以k+1邊形可以分解為m+1個互不重疊的三角形，命題得證。

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

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

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

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

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

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

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

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

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

6.1 越界報警功能

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

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

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

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

［1］孫家廣，楊長貴.計算機圖形學［M］.北京：清華大學出版社，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］周培德.計算幾何——算法設(shè)計與分析［M］.第2版.北京：清華大學出版社，2005：20-24.

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

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