李一青

摘 要 隨著定位導(dǎo)航需求的不斷發(fā)展，越來越多人關(guān)注利用興趣點POI將定位結(jié)果轉(zhuǎn)化為更多的服務(wù)應(yīng)用，比如人流分析，數(shù)據(jù)統(tǒng)計，以及服務(wù)消息推送等服務(wù)?；诰珳?zhǔn)定位的前提下，如何根據(jù)當(dāng)前位置正確判斷出所處的興趣點（POI）區(qū)域便也成了服務(wù)優(yōu)質(zhì)的關(guān)鍵因素。POI區(qū)域判斷的失誤，將導(dǎo)致無法真實地反饋情況或者錯誤消息的推送。本論文提出了一種新的利用可縮放矢量圖形來計算出定位點所在的興趣點區(qū)域的方法，該方法極大提高了興趣點判斷的準(zhǔn)確度，給定位應(yīng)用分析提供了強(qiáng)有力的保障。

關(guān)鍵詞 定位 興趣點 可縮放矢量圖形

0引言

當(dāng)前我們常常在室外導(dǎo)航應(yīng)用中聽到興趣點（POI）的概念，一般用于地圖搜索某一興趣點，實時在地圖上標(biāo)記出來。這是一種根據(jù)POI獲取位置點的方式，如果逆向思考，根據(jù)當(dāng)前位置點獲取所在的POI興趣點，那么對應(yīng)的應(yīng)用將能在很多方面上提供更大的便利。比如在外想查找最近的就餐餐館，根據(jù)位置信息計算出最近的興趣點，給用戶推送該興趣點餐館的信息，使用戶節(jié)省了自己查找地圖搜索的時間。諸如此類的應(yīng)用也是有一定的需求的。大數(shù)據(jù)時代的來臨，也給商家們提供了更多的機(jī)會。如今各大商場都很火熱的大數(shù)據(jù)分析，就是根據(jù)大量顧客數(shù)據(jù)做相關(guān)研究，這里就需要應(yīng)用到根據(jù)定位到的用戶位置獲取其所在的興趣點區(qū)域。而這也是室內(nèi)定位中根據(jù)位置點獲取POI興趣點的眾多應(yīng)用之一了。

常用的興趣點POI都有中心坐標(biāo)，我們可以通過該坐標(biāo)大概判斷出興趣點所在的位置。但是POI區(qū)域有大有小，其形狀也為不固定的不規(guī)則形狀，其中心點坐標(biāo)離邊沿區(qū)域距離也是大小不一，依靠中心點坐標(biāo)來判斷是否在興趣點上，其存在的誤差可能影響整個應(yīng)用的可靠性。因此我們采用一種新的根據(jù)位置點及從可縮放矢量圖形中獲取的興趣點POI相關(guān)信息計算出位置點所在的興趣點POI的方法，有效的提高了計算興趣點POI的準(zhǔn)確度。

1計算興趣點的原理與方法

1.1興趣點POI的信息提取方法

根據(jù)所畫的縮放矢量圖形SVG獲取POI相關(guān)的元素信息，所有興趣點POI對應(yīng)的軌跡描述字段和縮放矢量圖形的相關(guān)參數(shù)viewBox元素（viewBox元素描述詳見2.2）。

對POI進(jìn)行分類解析獲取軌跡點。常見類型包括矩形rect，多邊形polygon，不規(guī)則路徑path。各興趣點POI是由各軌跡點相連形成的圖形。

1.1.1矩形rect類

矩形rect類型包括x，y，width，height四個元素，根據(jù)這四個元素形成矩形，四個元素分別代表矩形初始點橫向坐標(biāo)，矩形初始點y向坐標(biāo)，矩形長，矩形寬，根據(jù)這些值可獲取矩形的四個頂點坐標(biāo)，分別為（x，y），（x+width， y），（x+wdith，y+height），（x，y+height）。

1.1.2多邊形polygon類

多邊形polygon類型中所含的points元素描述其圖形軌跡，points元素里的所有點坐標(biāo)即是多邊形的軌跡點。points元素的組成規(guī)則：按照第一個點的x坐標(biāo)，第一個點y坐標(biāo)，第二個點x坐標(biāo)，第二個點y坐標(biāo)，第三個點x坐標(biāo)…依次排列，各個數(shù)中間用逗號或者空格等隔開。

1.1.3圓形circle類

圓形circle類型包含圓心坐標(biāo)cx，cy，以及半徑r三個元素，以此畫圓形成軌跡點。

1.1.4不規(guī)則路徑path類

不規(guī)則路徑path相對比較復(fù)雜，其中包含的d元素里描述其軌跡，d元素包含多條命令，需要先對命令一一拆分，并各個分解。常見的d元素里攜帶的常見命令如下。

M = moveto（M x，y） ：將畫筆移動到指定的坐標(biāo)位置。M命令后跟的x，y一般為興趣點POI圖形的起始點。

L = lineto（L x，y） ：畫直線到指定的坐標(biāo)位置，即從上一個點坐標(biāo)（x0，y0）連線到坐標(biāo)為（x，y）的點。

H = horizontal lineto（H x）：畫水平線到指定的x坐標(biāo)位置，即從上一個點坐標(biāo)（x0，y0）連線到坐標(biāo)為（x，y0）的點，x坐標(biāo)變化，y坐標(biāo)不變。

V = vertical lineto（V y）：畫垂直線到指定的y坐標(biāo)位置，即從上一個點坐標(biāo)（x0，y0）連線到坐標(biāo)為（x0，y）的點，x坐標(biāo)不變，y坐標(biāo)變化。

C = curveto（C x1，y1，x2，y2，endx，endy）：畫三次貝賽曲線，命令前的上一個點坐標(biāo)（x0，y0）作為曲線的起始點P0， （x1，y1）為第一個控制點P1的坐標(biāo)，（x2，y2）為第二個控制點P2的坐標(biāo)，（endx，endy）為結(jié)束點P3的坐標(biāo)。

三次貝塞爾曲線公式：

B（t）=P0（1t）3+3P1t（1t）2+3

Q = quadratic Belzier curve（Q x，y，endx，endy）：畫二次貝賽曲線，命令前的上一個點坐標(biāo)（x0，y0）作為曲線的起始點P0， （x，y）為控制點P1的坐標(biāo)，（endx，endy）為結(jié)束點P2的坐標(biāo)。

二次貝塞爾曲線公式：

B（t）=P0（1t）2+2P1t（1t）+P2t2，t∈[0，1]

S = smooth curveto（S x2，y2，endx，endy） 畫光滑三次貝塞爾曲線，S命令和C命令差不多，S命令一般跟在C命令或者S命令之后，會自動根據(jù)上一個命令的最后一個控制點補(bǔ)出一個對稱的控制點作為第一個控制點P1，命令前的上一個點坐標(biāo)（x0，y0）作為曲線的起始點p0， （x2，y2）為第二個控制點P2的坐標(biāo)，（endx，endy）為結(jié)束點P3的坐標(biāo)。如果S命令之前的命令不是C命令或者S命令，則直接相當(dāng)于Q命令。

T = smooth quadratic Belziercurveto（T endx，endy）：畫光滑二次貝塞爾曲線，T命令和Q命令差不多，T命令一般跟在Q命令或者T命令之后，會自動根據(jù)上一個命令的控制點補(bǔ)出一個對稱的控制點作為控制點P1，命令前的上一個點坐標(biāo)（x0，y0）作為曲線的起始點p0， （endx，endy）為結(jié)束點P2的坐標(biāo)。如果T命令之前的命令不是Q命令或者T命令，則直接相當(dāng)于L命令。

Z = closepath（Z）：關(guān)閉路徑，圖形閉合。

以上所有命令，當(dāng)命令為小寫時，代表命令后面的坐標(biāo)為相對坐標(biāo)，相對于命令前一個點的坐標(biāo)，當(dāng)命令為大寫時，代表命令后面的坐標(biāo)為絕對坐標(biāo)。

1.1.5橢圓形類（不常見類型）

橢圓ellipse類型包含橢圓心坐標(biāo)cx，cy，以及水平半徑rx，垂直半徑ry四個元素，以此畫橢圓形成軌跡點。

1.2位置坐標(biāo)轉(zhuǎn)化

地圖SVG文件為可縮放矢量圖形，其可縮放的原理在于，畫圖的時候使用SVG的虛坐標(biāo)系即viewBox包含的一個固定大小及起始點坐標(biāo)，使得各圖形元素的大小和位置都是按viewBox限定的坐標(biāo)來保存，而生成圖片文件時，本身還有一個實際圖片長寬的元素，當(dāng)實際長寬與viewBox的長寬不一樣大時，各圖形元素按照比例縮小放大到實際大小，而偏移是通過改變 viewBox的起始點坐標(biāo)來實現(xiàn)。

通過各種定位算法得到的終端位置，可轉(zhuǎn)化成其在地圖上的相對位置，但還需要轉(zhuǎn)化成SVG的虛坐標(biāo)系里的坐標(biāo)，才能與上面得到的軌跡點進(jìn)行分析匹配。viewBox元素起始點坐標(biāo)為x0，y0，以及固定長寬vb_width和vb_height，使用以下公式進(jìn)行轉(zhuǎn)換。（相對坐標(biāo)是基于整張圖為坐標(biāo)1）

位置SVG坐標(biāo)x= 相對坐標(biāo)x * vb_width + x0

位置SVG坐標(biāo)y= 相對坐標(biāo)y * vb_height + y0

1.3興趣點POI判斷

根據(jù)上面得到的位置SVG坐標(biāo)，我們代入各個興趣點POI內(nèi)判斷，不同類型的興趣點使用不同的判斷方法。

1.3.1矩形判斷法

使用四個頂點作為軌跡點坐標(biāo)，根據(jù)位置x，y是否同時大于四個頂點的最小值并且小于最大值作為判斷依據(jù)，適用于矩形。

1.3.2多邊形判斷法

多邊形判斷主要使用射線法，射線法的基本思想是：從待判斷的點向四個方向（X軸正方向，X軸負(fù)方向，y軸正方向，y軸負(fù)方向）中的任一個方向引射線，計算和多邊形交點的個數(shù)，如果個數(shù)是偶數(shù)或者0則點在多邊形外，如果是奇數(shù)，則在多邊形內(nèi)。

這個只是最基本的判別情況，還有一些復(fù)雜的情況需要特殊處理：

第一種特殊情況：判斷點在多邊形頂點上。這種情況可直接在使用射線判斷法前排除，即優(yōu)先判斷是是否在各個頂點上，判斷為不在頂點時再使用射線判別法，這樣當(dāng)判斷點為頂點時也能更快得出判斷的結(jié)果。

第二種特殊情況：點在邊上。這種情況也不能用交點個數(shù)的奇偶性來判斷了，當(dāng)判斷出在某一線段邊上時，立即給出判斷結(jié)果。

在使用射線判別法之前，可提前先求出多邊形的外切矩形，即求多邊形分別在x軸和y軸上的最大最小值；使用矩形判斷法，優(yōu)先判斷是否在多邊形外切矩形上，如果不在，直接認(rèn)為不在該多邊形內(nèi)，如果在，則使用射線判別法繼續(xù)判斷。

使用射線判別法，首先檢查是否在多邊形頂點上，依次將位置判斷點與多邊形的各頂點，即上步驟中從points里獲取的各軌跡點進(jìn)行比較，相同認(rèn)為位置點剛好置于多邊形的頂點上，可認(rèn)為是在該多邊形內(nèi)。

當(dāng)排除判斷點為非頂點時，假設(shè)選擇X軸負(fù)方向引射線，如圖1。判斷時，依次取各線段的兩端頂點A，B，來與判斷點P作比較，計算出交點數(shù)總和。

判斷交點步驟：

步驟一：判斷點P（y）是否在線段所覆蓋的y向坐標(biāo)的范圍內(nèi)，即在Math.min（A（y）， B（y））～Math.max（A（y）， B（y））范圍內(nèi)（當(dāng)射線經(jīng)過頂點時，由于作為兩條線段的交叉頂點，會被重復(fù)計算，根據(jù)文章[2-3]中的方法，可加入去重機(jī)制，默認(rèn)每段線段只包含下端點，上端點屬于上一段線段），若不在范圍內(nèi)繼續(xù)步驟二的判斷；因為是向X軸的負(fù)方向做射線，排除掉在P點右側(cè)的線段，即只保留P（x）大于A（x）或者B（x）的線段，計算出射線或射線反方向延長線與線段的交點P'位置，若交點與判斷點重合（交點P'（x）等于判斷點P（x）），則判斷為在線段上，結(jié)束判斷；若交點P'（x）大于判斷點P（x），線段在判斷點右側(cè)，該交點是射線反向延長線與線段的交點，該交點無效，跳到下一個線段繼續(xù)從步驟一判斷；若交點P'（x）小于判斷點P（x），線段在左側(cè)，該交點是射線與線段的交點，有效交點，交點數(shù)加一，跳到下一個線段繼續(xù)從步驟一判斷。

步驟二：線段為水平線（A（y） == B（y））并且判斷點也在該水平線段上（P（y） == A（y） &&Math.min;（A（x）， B（x）） < x && x

若上述兩個步驟的條件都不符合，判斷點的射線與該線段不可能有交點，跳到下一個線段繼續(xù)從步驟一判斷。

所有該多邊形內(nèi)的線段都判斷完畢，根據(jù)判斷點射線與所有線段的交點數(shù)做出判斷，交點數(shù)為奇數(shù)，認(rèn)為判斷點在多邊形內(nèi)，交點數(shù)為偶數(shù)則判斷點在多邊形外。

1.3.3圓形判斷法

通過判斷點到原點的距離和圓的半徑的比較，當(dāng)距離在半徑內(nèi)，認(rèn)為判斷點在圓內(nèi)，不在半徑內(nèi)則認(rèn)為在圓外。

1.3.4路徑類型判斷法

不規(guī)則路徑一般會比較復(fù)雜，其中除了線段外還包含了一些曲線，這些曲線一般是貝賽爾曲線，因此判斷起來較為復(fù)雜。

首先利用多邊形判斷法，可先粗判斷出結(jié)果。不規(guī)則路徑中包含的貝賽爾曲線部分暫時先使用其起始點，結(jié)束點和控制點所形成的多邊形代替，代替后將路徑里所有點連接在一起組成一個第一多邊形（如圖2），而各個貝賽爾曲線四點或三點組成的小多邊形形成了第二多邊形（如圖2）。使用多邊形法判斷，判斷判斷點是否在第一多邊形內(nèi)，然后再依次判斷是否在第二多邊形內(nèi)并返回所在的貝賽爾曲線命令，若不在第二多邊形內(nèi)，可直接返回第一多邊形的判斷結(jié)果作為不規(guī)則路徑的判斷結(jié)果。若在第二多邊形內(nèi)，需要再進(jìn)行下一步的精細(xì)判斷。

用返回的貝賽爾曲線命令開始繼續(xù)判斷是否在該曲線的拱形凸起內(nèi)部。經(jīng)過判斷點P做垂直線，垂直線與曲線形成的交點P'，根據(jù)交點與判斷點P的位置關(guān)系可得出是否在曲線拱形凸起之內(nèi)。

不同方向的貝賽爾曲線，會形成的不同交點情況，當(dāng)貝賽爾曲線向左右兩側(cè)拱形凸起時，會有兩個交點。計算交點位置，將判斷點P坐標(biāo)x代入三次貝賽爾曲線（二次貝塞爾曲線）的方程中，并轉(zhuǎn)化成一元三次（一元二次）方程，使用一元三次（一元二次）方程求y解（將已知的起始點，終止點和控制點x，y坐標(biāo)分別代入x和y的貝賽爾曲線方程中作為系數(shù)，用x求出t，在將t代入y的貝賽爾曲線方程中求出y），t和y都只保留0～1之間的實根（曲線公式中規(guī)定t值為0～1之間，y坐標(biāo)值是基于整張圖為坐標(biāo)0～1，因此有效值只在0～1之間）。

根據(jù)實根情況判斷，如果有兩個符合條件的實根，為兩個交點的情況，根據(jù)判斷點坐標(biāo)y是否在兩個交點之間判斷是否在曲線凸起之內(nèi)，若是判斷為在曲線凸起之內(nèi)，否則為凸起之外。如果只有一個符合條件的實根，和判斷點P的坐標(biāo)y值比較，相等則認(rèn)為該點在貝賽爾曲線之上，返回最終結(jié)果為在興趣點區(qū)域線；不相等下需要結(jié)合曲線的兩種情況分析，當(dāng)曲線拱形向上凸起，判斷點P的y坐標(biāo)大于交點坐標(biāo)y，認(rèn)為判斷點在曲線拱形凸起之內(nèi)，當(dāng)曲線拱形向下凸起，判斷結(jié)果剛好相反。

根據(jù)上面方法得出判斷點是否在曲線拱形凸起之內(nèi)，結(jié)合路徑的第一多邊形的判斷結(jié)果，可得出最終的判斷結(jié)果：當(dāng)在曲線凸起之內(nèi)時，保持原來的第一多邊形判斷結(jié)果；在曲線凸起之外時，對原來的第一多邊形判斷結(jié)果取反。

1.3.5橢圓類型判斷法（不常見類型）

橢圓類型為不常見類型，判斷方法與圓類似，因此此處不做詳細(xì)方法展開。

我們根據(jù)上述的方法按照興趣點POI的各種類型，分別代入判斷，當(dāng)判斷出在某一個POI時可退出判斷，返回該興趣點POI的信息，如若不是繼續(xù)下一個興趣點的判斷直至完全判斷結(jié)束。

2方案優(yōu)化

使用這種興趣點方法判斷，判斷準(zhǔn)確度高，但是有個缺陷就是耗時可能會相對多些。因此可進(jìn)一步改進(jìn)，與柵格結(jié)合使用，可優(yōu)先使用柵格法大概判斷出所在的POI。導(dǎo)入興趣點POI時，將地圖橫豎各劃分成n等分，形成n*n個柵格，根據(jù)柵格范圍及POI的大概范圍，將覆蓋該柵格的POI都存儲其下。定位計算興趣點POI時，將定位結(jié)果先對應(yīng)到柵格位置，再將柵格里的POI進(jìn)行遍歷判斷，這樣可以減少了許多多余的判斷，提高了效率。

3結(jié)束語

使用該獲取興趣點方法，應(yīng)用于大數(shù)據(jù)分析中的人流區(qū)域分布統(tǒng)計及熱敏圖中，經(jīng)測試發(fā)現(xiàn)與實際的人流分布情況基本吻合，可見該方法準(zhǔn)確度可信。該方法將來可使用于更多的應(yīng)用中，提供更多的便利服務(wù)。

參考文獻(xiàn)

[1] 唐澤圣.計算機(jī)圖形學(xué)[M].北京：清華大學(xué)出版社，2002.

[2] 王燕平，劉永和.射線法判斷平面中的點在多邊形內(nèi)外的算法[J].山西建筑，2007，33（33）：364-365.

[3] 王澤根.射線法判定點與多變形包含關(guān)系的改進(jìn)[J].解放軍測繪學(xué)院學(xué)報，1999，16（02）：130-132.