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

李一青

摘 要 隨著定位導航需求的不斷發展，越來越多人關注利用興趣點POI將定位結果轉化為更多的服務應用，比如人流分析，數據統計，以及服務消息推送等服務。基于精準定位的前提下，如何根據當前位置正確判斷出所處的興趣點（POI）區域便也成了服務優質的關鍵因素。POI區域判斷的失誤，將導致無法真實地反饋情況或者錯誤消息的推送。本論文提出了一種新的利用可縮放矢量圖形來計算出定位點所在的興趣點區域的方法，該方法極大提高了興趣點判斷的準確度，給定位應用分析提供了強有力的保障。

關鍵詞 定位 興趣點 可縮放矢量圖形

0引言

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

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

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

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

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

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

1.1.1矩形rect類

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

1.1.2多邊形polygon類

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

1.1.3圓形circle類

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

1.1.4不規則路徑path類

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

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

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

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

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

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

三次貝塞爾曲線公式：

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

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

二次貝塞爾曲線公式：

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

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

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

Z = closepath（Z）：關閉路徑，圖形閉合。

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

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

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

1.2位置坐標轉化

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

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

位置SVG坐標x= 相對坐標x * vb_width + x0

位置SVG坐標y= 相對坐標y * vb_height + y0

1.3興趣點POI判斷

根據上面得到的位置SVG坐標，我們代入各個興趣點POI內判斷，不同類型的興趣點使用不同的判斷方法。

1.3.1矩形判斷法

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

1.3.2多邊形判斷法

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

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

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

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

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

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

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

判斷交點步驟：

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

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

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

所有該多邊形內的線段都判斷完畢，根據判斷點射線與所有線段的交點數做出判斷，交點數為奇數，認為判斷點在多邊形內，交點數為偶數則判斷點在多邊形外。

1.3.3圓形判斷法

通過判斷點到原點的距離和圓的半徑的比較，當距離在半徑內，認為判斷點在圓內，不在半徑內則認為在圓外。

1.3.4路徑類型判斷法

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

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

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

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

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

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

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

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

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

2方案優化

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

3結束語

使用該獲取興趣點方法，應用于大數據分析中的人流區域分布統計及熱敏圖中，經測試發現與實際的人流分布情況基本吻合，可見該方法準確度可信。該方法將來可使用于更多的應用中，提供更多的便利服務。

參考文獻

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

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

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