基于減治的點與凸多邊形位置關系判定算法

張 浩， 沈 華,2， 諶 剛

(1湖北工業大學計算機學院， 湖北 武漢 430068；2 桂林電子科技大學廣西可信軟件重點實驗室，廣西 桂林 541004)

隨著位置感知移動終端的普及，基于位置的服務(Location-Based Service, LBS)給人們的生活帶來了極大的便利[1]。近年來，幾何范圍查詢在LBS應用中被廣泛應用。判斷點與凸多邊形的位置關系是幾何范圍查詢的一種基本操作。例如LBS的典型應用——近鄰檢測服務，該服務允許用戶在地圖上選擇一個特定的幾何范圍，然后詢問他的朋友是否在這個范圍內。通常將用戶選定的幾何范圍抽象為凸多邊形，將用戶朋友的位置抽象為一個點，通過判斷點與凸多邊形的位置關系來解決近鄰檢測問題。目前判斷點與凸多邊形位置關系的方法有：計算點的方位[2]、射線法[3]、夾角法[4]、面積法[5]等。相關工作見文獻[6-17]。但這些方法普遍存在計算效率不高的問題。目前，人們通常通過移動設備(如智能手機、平板電腦、手環等)去請求LBS，移動設備存在資源受限的特點，因此，上述方法都不適合直接應用于LBS。在射線法中，通過給定點引出一條射線，計算該射線與凸多邊形的交點數，若交點的數為奇數，則坐標點在凸多邊形內部，否則坐標點在凸多邊形外。但當給定點位于凸多邊形邊上時，該方法存在誤判的可能性。因此，設計輕量級算法正確求解點與凸多邊形位置關系判定問題是一個值得研究的問題。

為了減少算法的計算開銷，本文運用了減治思想，通過減少問題求解過程中與點進行位置關系判斷的邊的條數來達到提高問題求解效率的目標。基于該思路，本文提出了一種輕量級點與凸多邊形位置關系判定算法(稱為LRDA)。算法LRDA首先提取凸多邊形的四個特征頂點，根據這四個特征頂點對凸多邊形進行區域劃分，通過判斷給定點落在哪個分區內將原問題的判斷范圍從凸多邊形縮小到凸多邊形的局部區域，然后調用該分區對應的判斷條件對給定點進行位置判定，最終得到點與凸多邊形的位置關系。

1 算法闡述

1.1 問題描述

假設給定的凸多邊形L具有n個頂點，從縱坐標最大的頂點開始依次進行逆時針編號，假設為{P1,P2,…,Pn}，其坐標分別為(xi,yi)，i=1,2,…,n，并給定一個點P(xp,yp)，判斷點P與該凸多邊形之間的位置關系，即判斷點P是位于凸多邊形外部還是位于凸多邊形內部。點P位于凸多邊形內部包括點P在凸多邊形邊上的情況。

1.2 算法設計

1.2.1凸多邊形區域劃分首先找出凸多邊形L的最上頂點、最左頂點、最下頂點、最右頂點四個特征頂點，分別表示為P1、Pl、Pd、Pr(圖1)。根據問題描述中的頂點編號規則可知1≤l≤d≤r≤n。然后，過最左頂點Pl(xl,yl)和最右頂點Pr(xr,yr)作與X軸平行的直線，過最上頂點P1(x1,y1)和最下頂點Pd(xd,yd)作與Y軸平行的直線，將凸多邊形L劃分為圖2所示的5個區域。第1個分區對應于圖2中的空白區域，如果點P落入這個區域，則說明點P在凸多邊形的外部。第2個分區對應于圖2中標注為Ⅰ的陰影區域、第3個分區對應于圖2中標注為Ⅱ的陰影區域、第4個分區對應于圖2中標注為Ⅲ的陰影區域、第5個分區對應于圖2中標注為Ⅳ的陰影區域，如果點P落入這些區域，則需要進一步判斷點P與凸多邊形的位置關系。

圖1 凸多邊形示意圖

圖2 凸多邊形劃分示意圖

1.2.2點的區域判斷這里分別給出點P落入上述5個區域的判斷條件。

判斷條件1：點落入空白區域。如果ypy1或者xpxr，那么點P(xp,yp)落入空白區域(圖3)。

圖3 點P落入空白區域示意圖

判斷條件2：點落入陰影區域Ⅰ。如果xi≤xp≤x1且yl≤yp≤yi，那么點P(xp,yp)落入陰影區域Ⅰ(圖4)。

(a)點在區域Ⅰ的凸多邊形內

(b)點在區域Ⅰ的凸多邊形外圖4 點P落入陰影區域Ⅰ示意圖

判斷條件3：點落入陰影區域Ⅱ。如果xi≤xp≤xd且yd≤yp

(a)點在區域Ⅱ的凸多邊形內

(b)點在區域Ⅱ的凸多邊形外圖5 點P落入陰影區域Ⅱ示意圖

判斷條件4：點落入陰影區域Ⅲ。如果xd≤xp≤xr，即點P(xp,yp)落入陰影區域Ⅲ(圖6)。

(a)點在區域Ⅲ的凸多邊形內

(b)點在區域Ⅲ的凸多邊形外圖6 點P落入陰影區域Ⅲ示意圖

判斷條件5：點落入陰影區域Ⅳ。如果x1≤xp≤xr且yr≤yp≤y1，那么點P(xp,yp)落入區域Ⅳ(圖7)。

(a)點在區域Ⅳ的凸多邊形內

(b)點在區域Ⅳ的凸多邊形外圖7 點P落入陰影區域Ⅳ示意圖

1.2.3點的位置關系判斷根據點落入不同的區域對點與凸多邊形的位置關系進行判斷。

情況1：如果判斷條件1成立，則說明給點P位于凸多邊形L的外部。

情況2：如果判斷條件2成立，則調用子算法1。子算法1：點的位置關系判斷(陰影區域Ⅰ)。

輸入：凸多邊形頂點{P1,P2,…,Pl}和點P。

輸出：點P與凸多邊形的位置關系。

Step1.在頂點{P1,P2,…,Pl}中找到相鄰的兩個頂點Pi和Pi+1，使得xi+1≤xp≤xi，其中1≤i≤l-1；

Step2.計算過頂點Pi和Pi+1的直線，用符號f1(x)表示該直線；

情況3：如果判斷條件3成立，則調用子算法2。

子算法2：點的位置關系判斷(陰影區域Ⅱ)

輸入：凸多邊形頂點{Pl,Pl+1,Pl+2,…,Pd}和點P。

輸出：點P與凸多邊形的位置關系

Step1.在頂點{Pi,Pl+1,Pl+2,…,Pd}中找到相鄰的兩個頂點Pi和Pi+1，使得xi≤xp≤xi+1，其中l≤i≤d-1；

Step2.計算過頂點Pi和Pi+1的直線，用符號f2(x)表示該直線；

Step3.如果yp≥f2(xp)(對應圖5a所示情況)，則點P位于凸多邊形L的內部，否則(對應圖5b所示情況)點P位于凸多邊形L的外部。

情況4：如果判斷條件4成立，則調用子算法3。

活性炭的吸附性能在很大程度上取決于孔結構特征。根據用途和應用領域的要求對活性炭的孔結構進行調控，定向制備活性炭，已成為目前活性炭領域研究的熱點。

子算法3：點的位置關系判斷(陰影區域Ⅲ)

輸入：凸多邊形頂點{Pd,Pd+1,Pd+2,…,Pr}和點P

輸出：點P與凸多邊形的位置關系

Step1.在頂點{Pd,Pd+1,Pd+2,…,Pr}中找到相鄰的兩個頂點Pi和Pi+1，使得xi≤xp≤xi+1，其中d≤i≤r-1。

Step2.計算過頂點Pi和Pi+1的直線，用符號f3(x)表示該直線；

Step3.如果yp≥f3(xp)(對應圖6a所示情況)，則點P位于凸多邊形L的內部，否則(對應圖6b所示情況)點P位于凸多邊形L的外部。

情況5：如果判斷條件5成立，則調用子算法4。

子算法4：點的位置關系判斷(陰影區域Ⅳ)

輸入：凸多邊形頂點{Pr,Pr+1,Pr+2,…,Pn,P1}和點P

輸出：點P與凸多邊形的位置關系

Step1.若x1≤xp≤xn，則選中頂點Pn和P1，否則在頂點{Pr,Pr+1,Pr+2,…,Pn}中找到相鄰的兩個頂點Pi和Pi+1，使得xi+1≤xp≤xi，其中r≤i≤n-1；

Step2.若選中的頂點為Pn和P1，則計算過頂點Pn和P1的直線，否則計算過頂點Pi和Pi+1的直線，用符號f4(x)表示計算得到的直線；

Step3.如果yp≤f4(xp)(對應圖7a所示情況)，則點P位于凸多邊形L的內部，否則(對應圖7b所示情況)點P位于凸多邊形L的外部。

1.2.4算法描述所提出的基于減治思想的點與凸多邊形位置判定算法描述如下。

算法LRDA：(點與凸多邊形的位置關系判斷)

輸入：具有n個頂點的凸多邊形和點P

輸出：點P與凸多邊形的位置關系

Step1.對給定凸多邊形進行區域劃分；

Step2.判斷點落在哪個區域；

Step3.如果點落在空白區域，則立即返回點P位于凸多邊形外部；如果點P落在陰影區域Ⅰ，則調用子算法1；如果點P落在陰影區域Ⅱ，則調用子算法2；如果點P落在陰影區域Ⅲ，則調用子算法3；如果點P落在陰影區域Ⅳ，則調用子算法4。

2 算法分析

本小節給出算法LRDA的時間復雜度分析。算法LRDA中Step1的時間開銷主要花費在找最上頂點、最下頂點、最左頂點和最右頂點上。可以先將所有頂點按照x坐標和y坐標分別進行排序，此過程可以在O(nlogn)時間內容完成；然后，我們可以在O(1)時間內找到上述四個特征頂點。因此，算法LRDA中Step1的時間復雜度為O(nlogn)。顯然，算法LRDA中Step2的時間開銷為O(1)。算法LRDA中Step3的時間開銷分析需要考慮點落到5個分區的概率分布。用E1表示點落在空白區域(即圖2中的空白區域)的事件，用E2表示點落在非空白區域(即圖2中的4個陰影區域)的事件，則有:

3 算法實施

實施場景1：基于位置服務中的近鄰好友判斷。

場景描述：用戶A在某商圈逛街，想知道其好友B是否也在該商圈范圍內。此場景下，算法LRDA在位置服務器上運行，算法的輸入分別來自用戶A和用戶B，其中用戶A的輸入被抽象為一個凸多邊形，用戶B的輸入被抽象為一個點。

實施場景2：移動服務站最佳運營路線。

場景描述：服務型公司C為了更好地服務于其客戶，決定設置移動服務站點。為了充分發揮移動服務站的作用，需要給出移動服務站每個時間段的最佳服務地點。公司C可以通過執行算法LRDA獲得移動服務站的最佳運營路線。首先，公司C確定時間段和選出幾個候選區域范圍；然后，公司C通過執行算法LRDA統計出不同時間段出現在候選區域內的客戶人數；最后根據統計結果得到移動服務站的最佳運營路線。此場景下，公司C執行在給定的時間段內執行算法LRDA，算法的輸入分別為公司C選定的候選區域和客戶的當前位置。

4 結束語