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

陳希

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

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

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

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

1 基本概念

1.1 多邊形

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

1.2 凹多邊形

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

1.3 凸多邊形

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

1.4 射線定理

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

1.5 點O在△ABC內部的一個充要條件

2 證明思路

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

3 點在三角形內的檢測

3.1 交點不經過三角形的任意一個頂點

自定義一個坐標系，使得待檢測點P（0，0）為坐標原點，同時三角形S的任意一條邊不與X軸和Y軸平行或垂直。經過點P，引一條直線y＝0，與三角形S相交于2個點A1（a，0）和A2（b，0），其中，a＜b.對于交點，可能出現以下3種情況：①A1和A2在點P的一側，即a·b＞0；②P與A1或者A2之一重合，即a·b＝0；③A1和A2在點P的兩側，即a·b＜0.顯然，對于第2種情況，可以知道點P在三角形S上；對于第1種情況，假設A1和A2都在P點右側，即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左側時，點P也在△ABC外部。對于第3種情況，ab＜0時，由假設可得，b＞0，a點P在三角形內?射線定理對于三角形適用。

3.2 交點經過至少一個頂點

3．2．1 交點經過三角形的一個頂點

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

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

圖2 2個頂點在射線的同一側

圖3 2個頂點在射線的兩側

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

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

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

3．2．2 交點經過三角形的2個頂點

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

4 點在多邊形內的檢測

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

顯然，四邊形可以分解為2個互不重疊的三角形。下面采用歸納法證明命題。假設邊數為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互不重疊。由假設可知，k邊形A1A2…Ak可以分解為m個互不重疊的三角形，所以k+1邊形可以分解為m+1個互不重疊的三角形，命題得證。

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

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

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

證明過程如下：由于ax-1和ax+1在P點同側，如果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，最后的結果都是，可以去除交點ax的統計。

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

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

5 算法實現過程

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

6 射線定理在公安業務中的運用

6.1 越界報警功能

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

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

6.2 區域范圍內查詢地圖圖層

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

［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］周培德.計算幾何——算法設計與分析［M］.第2版.北京：清華大學出版社，2005：20-24.

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

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