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

1、    基于可縮放矢量圖形計(jì)算興趣點(diǎn)方法研究    李一青摘 要 隨著定位導(dǎo)航需求的不斷發(fā)展，越來(lái)越多人關(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)致無(wú)法真實(shí)地反饋情況或者錯(cuò)誤消息的推送。本論文提出了一種新的利用可縮放矢量圖形來(lái)計(jì)算出定位點(diǎn)所在的興趣點(diǎn)區(qū)域的方法，該方法極大提高了興趣點(diǎn)判斷的準(zhǔn)確度，給定位應(yīng)用分析提供了強(qiáng)有力的保障。關(guān)鍵詞 定位 興趣點(diǎn) 可縮放矢量圖形0引言

2、當(dāng)前我們常常在室外導(dǎo)航應(yīng)用中聽到興趣點(diǎn)（poi）的概念，一般用于地圖搜索某一興趣點(diǎn)，實(shí)時(shí)在地圖上標(biāo)記出來(lái)。這是一種根據(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í)代的來(lái)臨，也給商家們提供了更多的機(jī)會(huì)。如今各大商場(chǎng)都很火熱的大數(shù)據(jù)分析，就是根據(jù)大量顧客數(shù)據(jù)做相關(guān)研究，這里就需要應(yīng)用到根據(jù)定位到的用戶位置獲取其所在的興趣點(diǎn)區(qū)域。而這也是室內(nèi)定位中根據(jù)位置

3、點(diǎn)獲取poi興趣點(diǎn)的眾多應(yīng)用之一了。常用的興趣點(diǎn)poi都有中心坐標(biāo)，我們可以通過(guò)該坐標(biāo)大概判斷出興趣點(diǎn)所在的位置。但是poi區(qū)域有大有小，其形狀也為不固定的不規(guī)則形狀，其中心點(diǎn)坐標(biāo)離邊沿區(qū)域距離也是大小不一，依靠中心點(diǎn)坐標(biāo)來(lái)判斷是否在興趣點(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)參

4、數(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類型中所含的point

5、s元素描述其圖形軌跡，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，

6、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，

7、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+3q = 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，t0，1s = smooth curveto（s x2，y2，endx

8、，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)

9、作為控制點(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的虛

10、坐標(biāo)系即viewbox包含的一個(gè)固定大小及起始點(diǎn)坐標(biāo)，使得各圖形元素的大小和位置都是按viewbox限定的坐標(biāo)來(lái)保存，而生成圖片文件時(shí)，本身還有一個(gè)實(shí)際圖片長(zhǎng)寬的元素，當(dāng)實(shí)際長(zhǎng)寬與viewbox的長(zhǎng)寬不一樣大時(shí)，各圖形元素按照比例縮小放大到實(shí)際大小，而偏移是通過(guò)改變 viewbox的起始點(diǎn)坐標(biāo)來(lái)實(shí)現(xiàn)。通過(guò)各種定位算法得到的終端位置，可轉(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)

11、x= 相對(duì)坐標(biāo)x * vb_width + x0位置svg坐標(biāo)y= 相對(duì)坐標(biāo)y * vb_height + y01.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ù)，則在

12、多邊形內(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ù)的奇偶性來(lái)判斷了，當(dāng)判斷出在某一線段邊上時(shí)，立即給出判斷結(jié)果。在使用射線判別法之前，可提前先求出多邊形的外切矩形，即求多邊形分別在x軸和y軸上的最大最小值；使用矩形判斷法，優(yōu)先判斷是否在多邊形外切矩形上，如果不在，直接認(rèn)為不在該多邊形內(nèi)，如果在，則使用射線判別法繼續(xù)判斷。使用射線判別法，首先檢查是

13、否在多邊形頂點(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，來(lái)與判斷點(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)過(guò)頂點(diǎn)時(shí)，由于作為兩條線段的交叉頂點(diǎn)，會(huì)被重復(fù)計(jì)算，根據(jù)文章2-3中的方法，可加入去重機(jī)制，默認(rèn)每段線段只包含下端點(diǎn)，上端點(diǎn)屬于上一段線

14、段），若不在范圍內(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)無(wú)效，跳到下一個(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

15、（y）并且判斷點(diǎn)也在該水平線段上（p（y） = a（y） &&math.min;（a（x）， b（x） < x && x < p>若上述兩個(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圓形判斷法通過(guò)判斷點(diǎn)到原點(diǎn)的距離和圓的半徑的比較，當(dāng)距離在半徑內(nèi)，認(rèn)為判斷點(diǎn)在圓內(nèi)，不在半徑內(nèi)則認(rèn)為在圓外。1.3.4路徑類型判斷法不規(guī)則路徑一般會(huì)比較復(fù)雜，其中除了線段外

16、還包含了一些曲線，這些曲線一般是貝賽爾曲線，因此判斷起來(lái)較為復(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ù)判斷是否在該曲線的拱

17、形凸起內(nèi)部。經(jīng)過(guò)判斷點(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都只保留01之間的實(shí)根（曲線公式中規(guī)定t值為01之間，y坐標(biāo)值是基于整張圖為坐標(biāo)01，因此有效

18、值只在01之間）。根據(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í)，保持原來(lái)的第一多邊形判斷結(jié)果；在曲線凸起之外時(shí)，對(duì)原來(lái)的第一多邊形判