基于減治的點(diǎn)與凸多邊形位置關(guān)系判定算法

張 浩， 沈 華,2， 諶 剛

(1湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院， 湖北 武漢 430068；2 桂林電子科技大學(xué)廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

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

為了減少算法的計(jì)算開(kāi)銷，本文運(yùn)用了減治思想，通過(guò)減少問(wèn)題求解過(guò)程中與點(diǎn)進(jìn)行位置關(guān)系判斷的邊的條數(shù)來(lái)達(dá)到提高問(wèn)題求解效率的目標(biāo)?；谠撍悸?，本文提出了一種輕量級(jí)點(diǎn)與凸多邊形位置關(guān)系判定算法(稱為L(zhǎng)RDA)。算法LRDA首先提取凸多邊形的四個(gè)特征頂點(diǎn)，根據(jù)這四個(gè)特征頂點(diǎn)對(duì)凸多邊形進(jìn)行區(qū)域劃分，通過(guò)判斷給定點(diǎn)落在哪個(gè)分區(qū)內(nèi)將原問(wèn)題的判斷范圍從凸多邊形縮小到凸多邊形的局部區(qū)域，然后調(diào)用該分區(qū)對(duì)應(yīng)的判斷條件對(duì)給定點(diǎn)進(jìn)行位置判定，最終得到點(diǎn)與凸多邊形的位置關(guān)系。

1 算法闡述

1.1 問(wèn)題描述

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

1.2 算法設(shè)計(jì)

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

圖1 凸多邊形示意圖

圖2 凸多邊形劃分示意圖

1.2.2點(diǎn)的區(qū)域判斷這里分別給出點(diǎn)P落入上述5個(gè)區(qū)域的判斷條件。

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

圖3 點(diǎn)P落入空白區(qū)域示意圖

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

(a)點(diǎn)在區(qū)域Ⅰ的凸多邊形內(nèi)

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

判斷條件3：點(diǎn)落入陰影區(qū)域Ⅱ。如果xi≤xp≤xd且yd≤yp

(a)點(diǎn)在區(qū)域Ⅱ的凸多邊形內(nèi)

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

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

(a)點(diǎn)在區(qū)域Ⅲ的凸多邊形內(nèi)

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

判斷條件5：點(diǎn)落入陰影區(qū)域Ⅳ。如果x1≤xp≤xr且yr≤yp≤y1，那么點(diǎn)P(xp,yp)落入?yún)^(qū)域Ⅳ(圖7)。

(a)點(diǎn)在區(qū)域Ⅳ的凸多邊形內(nèi)

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

1.2.3點(diǎn)的位置關(guān)系判斷根據(jù)點(diǎn)落入不同的區(qū)域?qū)c(diǎn)與凸多邊形的位置關(guān)系進(jìn)行判斷。

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

情況2：如果判斷條件2成立，則調(diào)用子算法1。子算法1：點(diǎn)的位置關(guān)系判斷(陰影區(qū)域Ⅰ)。

輸入：凸多邊形頂點(diǎn){P1,P2,…,Pl}和點(diǎn)P。

輸出：點(diǎn)P與凸多邊形的位置關(guān)系。

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

Step2.計(jì)算過(guò)頂點(diǎn)Pi和Pi+1的直線，用符號(hào)f1(x)表示該直線；

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

子算法2：點(diǎn)的位置關(guān)系判斷(陰影區(qū)域Ⅱ)

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

輸出：點(diǎn)P與凸多邊形的位置關(guān)系

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

Step2.計(jì)算過(guò)頂點(diǎn)Pi和Pi+1的直線，用符號(hào)f2(x)表示該直線；

Step3.如果yp≥f2(xp)(對(duì)應(yīng)圖5a所示情況)，則點(diǎn)P位于凸多邊形L的內(nèi)部，否則(對(duì)應(yīng)圖5b所示情況)點(diǎn)P位于凸多邊形L的外部。

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

活性炭的吸附性能在很大程度上取決于孔結(jié)構(gòu)特征。根據(jù)用途和應(yīng)用領(lǐng)域的要求對(duì)活性炭的孔結(jié)構(gòu)進(jìn)行調(diào)控，定向制備活性炭，已成為目前活性炭領(lǐng)域研究的熱點(diǎn)。

子算法3：點(diǎn)的位置關(guān)系判斷(陰影區(qū)域Ⅲ)

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

輸出：點(diǎn)P與凸多邊形的位置關(guān)系

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

Step2.計(jì)算過(guò)頂點(diǎn)Pi和Pi+1的直線，用符號(hào)f3(x)表示該直線；

Step3.如果yp≥f3(xp)(對(duì)應(yīng)圖6a所示情況)，則點(diǎn)P位于凸多邊形L的內(nèi)部，否則(對(duì)應(yīng)圖6b所示情況)點(diǎn)P位于凸多邊形L的外部。

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

子算法4：點(diǎn)的位置關(guān)系判斷(陰影區(qū)域Ⅳ)

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

輸出：點(diǎn)P與凸多邊形的位置關(guān)系

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

Step2.若選中的頂點(diǎn)為Pn和P1，則計(jì)算過(guò)頂點(diǎn)Pn和P1的直線，否則計(jì)算過(guò)頂點(diǎn)Pi和Pi+1的直線，用符號(hào)f4(x)表示計(jì)算得到的直線；

Step3.如果yp≤f4(xp)(對(duì)應(yīng)圖7a所示情況)，則點(diǎn)P位于凸多邊形L的內(nèi)部，否則(對(duì)應(yīng)圖7b所示情況)點(diǎn)P位于凸多邊形L的外部。

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

算法LRDA：(點(diǎn)與凸多邊形的位置關(guān)系判斷)

輸入：具有n個(gè)頂點(diǎn)的凸多邊形和點(diǎn)P

輸出：點(diǎn)P與凸多邊形的位置關(guān)系

Step1.對(duì)給定凸多邊形進(jìn)行區(qū)域劃分；

Step2.判斷點(diǎn)落在哪個(gè)區(qū)域；

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

2 算法分析

本小節(jié)給出算法LRDA的時(shí)間復(fù)雜度分析。算法LRDA中Step1的時(shí)間開(kāi)銷主要花費(fèi)在找最上頂點(diǎn)、最下頂點(diǎn)、最左頂點(diǎn)和最右頂點(diǎn)上?？梢韵葘⑺许旤c(diǎn)按照x坐標(biāo)和y坐標(biāo)分別進(jìn)行排序，此過(guò)程可以在O(nlogn)時(shí)間內(nèi)容完成；然后，我們可以在O(1)時(shí)間內(nèi)找到上述四個(gè)特征頂點(diǎn)。因此，算法LRDA中Step1的時(shí)間復(fù)雜度為O(nlogn)。顯然，算法LRDA中Step2的時(shí)間開(kāi)銷為O(1)。算法LRDA中Step3的時(shí)間開(kāi)銷分析需要考慮點(diǎn)落到5個(gè)分區(qū)的概率分布。用E1表示點(diǎn)落在空白區(qū)域(即圖2中的空白區(qū)域)的事件，用E2表示點(diǎn)落在非空白區(qū)域(即圖2中的4個(gè)陰影區(qū)域)的事件，則有:

3 算法實(shí)施

實(shí)施場(chǎng)景1：基于位置服務(wù)中的近鄰好友判斷。

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

實(shí)施場(chǎng)景2：移動(dòng)服務(wù)站最佳運(yùn)營(yíng)路線。

場(chǎng)景描述：服務(wù)型公司C為了更好地服務(wù)于其客戶，決定設(shè)置移動(dòng)服務(wù)站點(diǎn)。為了充分發(fā)揮移動(dòng)服務(wù)站的作用，需要給出移動(dòng)服務(wù)站每個(gè)時(shí)間段的最佳服務(wù)地點(diǎn)。公司C可以通過(guò)執(zhí)行算法LRDA獲得移動(dòng)服務(wù)站的最佳運(yùn)營(yíng)路線。首先，公司C確定時(shí)間段和選出幾個(gè)候選區(qū)域范圍；然后，公司C通過(guò)執(zhí)行算法LRDA統(tǒng)計(jì)出不同時(shí)間段出現(xiàn)在候選區(qū)域內(nèi)的客戶人數(shù)；最后根據(jù)統(tǒng)計(jì)結(jié)果得到移動(dòng)服務(wù)站的最佳運(yùn)營(yíng)路線。此場(chǎng)景下，公司C執(zhí)行在給定的時(shí)間段內(nèi)執(zhí)行算法LRDA，算法的輸入分別為公司C選定的候選區(qū)域和客戶的當(dāng)前位置。

4 結(jié)束語(yǔ)