基于可縮放矢量圖形計算興趣點方法研究

1、    基于可縮放矢量圖形計算興趣點方法研究    李一青摘 要 隨著定位導(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)用分析提供了強有力的保障。關(guān)鍵詞 定位 興趣點 可縮放矢量圖形0引言

2、當(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ù)時代的來臨，也給商家們提供了更多的機會。如今各大商場都很火熱的大數(shù)據(jù)分析，就是根據(jù)大量顧客數(shù)據(jù)做相關(guān)研究，這里就需要應(yīng)用到根據(jù)定位到的用戶位置獲取其所在的興趣點區(qū)域。而這也是室內(nèi)定位中根據(jù)位置

3、點獲取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)參

4、數(shù)viewbox元素（viewbox元素描述詳見2.2）。對poi進行分類解析獲取軌跡點。常見類型包括矩形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類型中所含的point

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

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

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

8、，endy） 畫光滑三次貝塞爾曲線，s命令和c命令差不多，s命令一般跟在c命令或者s命令之后，會自動根據(jù)上一個命令的最后一個控制點補出一個對稱的控制點作為第一個控制點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ù)上一個命令的控制點補出一個對稱的控制點

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

10、坐標(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)，才能與上面得到的軌跡點進行分析匹配。viewbox元素起始點坐標(biāo)為x0，y0，以及固定長寬vb_width和vb_height，使用以下公式進行轉(zhuǎn)換。（相對坐標(biāo)是基于整張圖為坐標(biāo)1）位置svg坐標(biāo)

11、x= 相對坐標(biāo)x * vb_width + x0位置svg坐標(biāo)y= 相對坐標(biāo)y * vb_height + y01.3興趣點poi判斷根據(jù)上面得到的位置svg坐標(biāo)，我們代入各個興趣點poi內(nèi)判斷，不同類型的興趣點使用不同的判斷方法。1.3.1矩形判斷法使用四個頂點作為軌跡點坐標(biāo)，根據(jù)位置x，y是否同時大于四個頂點的最小值并且小于最大值作為判斷依據(jù)，適用于矩形。1.3.2多邊形判斷法多邊形判斷主要使用射線法，射線法的基本思想是：從待判斷的點向四個方向（x軸正方向，x軸負方向，y軸正方向，y軸負方向）中的任一個方向引射線，計算和多邊形交點的個數(shù)，如果個數(shù)是偶數(shù)或者0則點在多邊形外，如果是奇數(shù)，則在

12、多邊形內(nèi)。這個只是最基本的判別情況，還有一些復(fù)雜的情況需要特殊處理：第一種特殊情況：判斷點在多邊形頂點上。這種情況可直接在使用射線判斷法前排除，即優(yōu)先判斷是是否在各個頂點上，判斷為不在頂點時再使用射線判別法，這樣當(dāng)判斷點為頂點時也能更快得出判斷的結(jié)果。第二種特殊情況：點在邊上。這種情況也不能用交點個數(shù)的奇偶性來判斷了，當(dāng)判斷出在某一線段邊上時，立即給出判斷結(jié)果。在使用射線判別法之前，可提前先求出多邊形的外切矩形，即求多邊形分別在x軸和y軸上的最大最小值；使用矩形判斷法，優(yōu)先判斷是否在多邊形外切矩形上，如果不在，直接認為不在該多邊形內(nèi)，如果在，則使用射線判別法繼續(xù)判斷。使用射線判別法，首先檢查是

13、否在多邊形頂點上，依次將位置判斷點與多邊形的各頂點，即上步驟中從points里獲取的各軌跡點進行比較，相同認為位置點剛好置于多邊形的頂點上，可認為是在該多邊形內(nèi)。當(dāng)排除判斷點為非頂點時，假設(shè)選擇x軸負方向引射線，如圖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中的方法，可加入去重機制，默認每段線段只包含下端點，上端點屬于上一段線

14、段），若不在范圍內(nèi)繼續(xù)步驟二的判斷；因為是向x軸的負方向做射線，排除掉在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

15、（y）并且判斷點也在該水平線段上（p（y） = a（y） &&math.min;（a（x）， b（x） < x && x < p>若上述兩個步驟的條件都不符合，判斷點的射線與該線段不可能有交點，跳到下一個線段繼續(xù)從步驟一判斷。所有該多邊形內(nèi)的線段都判斷完畢，根據(jù)判斷點射線與所有線段的交點數(shù)做出判斷，交點數(shù)為奇數(shù)，認為判斷點在多邊形內(nèi)，交點數(shù)為偶數(shù)則判斷點在多邊形外。1.3.3圓形判斷法通過判斷點到原點的距離和圓的半徑的比較，當(dāng)距離在半徑內(nèi)，認為判斷點在圓內(nèi)，不在半徑內(nèi)則認為在圓外。1.3.4路徑類型判斷法不規(guī)則路徑一般會比較復(fù)雜，其中除了線段外

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

17、形凸起內(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都只保留01之間的實根（曲線公式中規(guī)定t值為01之間，y坐標(biāo)值是基于整張圖為坐標(biāo)01，因此有效

18、值只在01之間）。根據(jù)實根情況判斷，如果有兩個符合條件的實根，為兩個交點的情況，根據(jù)判斷點坐標(biāo)y是否在兩個交點之間判斷是否在曲線凸起之內(nèi)，若是判斷為在曲線凸起之內(nèi)，否則為凸起之外。如果只有一個符合條件的實根，和判斷點p的坐標(biāo)y值比較，相等則認為該點在貝賽爾曲線之上，返回最終結(jié)果為在興趣點區(qū)域線；不相等下需要結(jié)合曲線的兩種情況分析，當(dāng)曲線拱形向上凸起，判斷點p的y坐標(biāo)大于交點坐標(biāo)y，認為判斷點在曲線拱形凸起之內(nèi)，當(dāng)曲線拱形向下凸起，判斷結(jié)果剛好相反。根據(jù)上面方法得出判斷點是否在曲線拱形凸起之內(nèi)，結(jié)合路徑的第一多邊形的判斷結(jié)果，可得出最終的判斷結(jié)果：當(dāng)在曲線凸起之內(nèi)時，保持原來的第一多邊形判斷結(jié)果；在曲線凸起之外時，對原來的第一多邊形判