基于可縮放矢量圖形計(jì)算興趣點(diǎn)方法研究

李一青

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

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

0引言

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

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

1計(jì)算興趣點(diǎn)的原理與方法

1.1興趣點(diǎn)POI的信息提取方法

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

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

1.1.1矩形rect類

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

1.1.2多邊形polygon類

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

1.1.3圓形circle類

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

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

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

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

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

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

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

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

三次貝塞爾曲線公式：

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

Q = quadratic Belzier curve（Q x，y，endx，endy）：畫二次貝賽曲線，命令前的上一個(gè)點(diǎn)坐標(biāo)（x0，y0）作為曲線的起始點(diǎn)P0， （x，y）為控制點(diǎn)P1的坐標(biāo)，（endx，endy）為結(jié)束點(diǎn)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命令之后，會(huì)自動(dòng)根據(jù)上一個(gè)命令的最后一個(gè)控制點(diǎn)補(bǔ)出一個(gè)對(duì)稱的控制點(diǎn)作為第一個(gè)控制點(diǎn)P1，命令前的上一個(gè)點(diǎn)坐標(biāo)（x0，y0）作為曲線的起始點(diǎn)p0， （x2，y2）為第二個(gè)控制點(diǎn)P2的坐標(biāo)，（endx，endy）為結(jié)束點(diǎn)P3的坐標(biāo)。如果S命令之前的命令不是C命令或者S命令，則直接相當(dāng)于Q命令。

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

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

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

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

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

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

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

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

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

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

1.3興趣點(diǎn)POI判斷

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

1.3.1矩形判斷法

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

1.3.2多邊形判斷法

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

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

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

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

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

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

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

判斷交點(diǎn)步驟：

步驟一：判斷點(diǎn)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)過頂點(diǎn)時(shí)，由于作為兩條線段的交叉頂點(diǎn)，會(huì)被重復(fù)計(jì)算，根據(jù)文章[2-3]中的方法，可加入去重機(jī)制，默認(rèn)每段線段只包含下端點(diǎn)，上端點(diǎn)屬于上一段線段），若不在范圍內(nèi)繼續(xù)步驟二的判斷；因?yàn)槭窍騒軸的負(fù)方向做射線，排除掉在P點(diǎn)右側(cè)的線段，即只保留P（x）大于A（x）或者B（x）的線段，計(jì)算出射線或射線反方向延長(zhǎng)線與線段的交點(diǎn)P'位置，若交點(diǎn)與判斷點(diǎn)重合（交點(diǎn)P'（x）等于判斷點(diǎn)P（x）），則判斷為在線段上，結(jié)束判斷；若交點(diǎn)P'（x）大于判斷點(diǎn)P（x），線段在判斷點(diǎn)右側(cè)，該交點(diǎn)是射線反向延長(zhǎng)線與線段的交點(diǎn)，該交點(diǎn)無效，跳到下一個(gè)線段繼續(xù)從步驟一判斷；若交點(diǎn)P'（x）小于判斷點(diǎn)P（x），線段在左側(cè)，該交點(diǎn)是射線與線段的交點(diǎn)，有效交點(diǎn)，交點(diǎn)數(shù)加一，跳到下一個(gè)線段繼續(xù)從步驟一判斷。

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

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

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

1.3.3圓形判斷法

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

1.3.4路徑類型判斷法

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

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

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

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

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

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

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

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

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

2方案優(yōu)化

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

3結(jié)束語

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

參考文獻(xiàn)

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

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

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