基于可缩放矢量图形计算兴趣点方法研究

李一青

摘 要 随着定位导航需求的不断发展，越来越多人关注利用兴趣点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.