GPS电子围栏算法

地理围栏是LBS(基于位置的服务)的一种应用,当设备进入、离开某个特定地理区域,或在该区域内活动时,手机可以接收自动通知和警告,车载屏广告圈发等,再比如深圳的绿色的士一旦驶入关内,会收到警告。地理围栏的主要问题就是判断设备是否落在某多边形围栏内部。

地理围栏是一种基于位置服务(LBS)的创新应用。当设备进入、离开特定地理区域,或在该区域内活动时,用户的手机可以接收自动通知和警告。例如,车载屏幕广告圈发,或深圳的绿色的士一旦驶入关内会收到警告。实现地理围栏的的一个问题是如何准确判断设备是否位于某个多边形围栏内部。

如何判断点在多边形内部

例如我们要判断下图中这个红点是否在这个多边形内

解决方案是在红色测试点上引一条射线,看射线与多边形有多少个交点,如果有奇数个交点则测试点在多边形内,如果是偶数个则测试点在多边形外。还有些特殊情况,下面会提到。
上图中,测试点的左侧水平射线有5个交点,右侧水平射线有3个交点,都是奇数个,因此它在多边形内。

对于各种复杂的多边形,算法依然成立,上图都是偶数个交点在两侧,所以在多边形外。

换成算法,我们比较的是测试点与多边形各个点的X/Y坐标值

我们遍历每个边,如果边上其中一个点的Y坐标值大于等于测试点Y坐标值,并且边上另一个点的Y坐标值小于测试点Y坐标值,并且边上其中至少有一个点的X坐标值小于测试点的X坐标值(只统计一侧的水平射线),并且测试点不在这条边上,我们就计一次交点,最终奇数个交点则测试点在多边形内,偶数则测试点在多边形外。

上图是左侧射线与边a 和边b 的夹角相交,属于特殊情况,边a 和边b 都有一个点在测试点的水平射线上,这算是有2个交点吗?显然不是。边a 满足一个点的Y坐标值大于或等于测试点Y坐标值并且另一个点的Y坐标值小于测试点的Y坐标值,算是一个交点,但边b 不产生,因为它没有一个点小于测试点的Y坐标值。

上图的边d 完全落在测试点的水平射线上,但边d 是不产生交点的,边e 也不产生交点,因为这两个边都没有一个点的Y坐标值小于测试点的Y坐标值。而c 产生一个交点,因为它满足一个点的Y坐标值大于或等于测试点Y坐标值并且另一个点的Y坐标值小于测试点的Y坐标值。上图每侧分别产生1个交点,所以测试点在多边形内。

这张图其实按照规则依然形得通。上图射线只产生1个交点,下图射线是产生3个交点。

对于测试点直接落在多边形上这种情况,是另一种特殊情况,结果是不可预知的,要按实际情况。

点是否在多边形内算法PHP版

<?php
// 参考 http://alienryderflex.com/polygon/
// $vertexes 多边形的坐标数组(多边形按顺时针或逆时针方向绘制不影响结果)
// $point 测试点坐标

function pointInPolygon($vertexes, $point) {
    $polyCorners = count($vertexes);
    $i = 0;
    $j = $polyCorners-1;
    $oddNodes = false; // 奇数个交点为false - 初始偶数个交点
    for ($i=0; $i<$polyCorners; $i++) {
        if (($vertexes[$i][1]<$point[1] && $vertexes[$j][1]>=$point[1] || $vertexes[$j][1]<$point[1] && $vertexes[$i][1]>=$point[1]) && ($vertexes[$i][0] <= $point[0] || $vertexes[$j][0] <= $point[0])) {
            if ($vertexes[$i][0] + ($point[1]-$vertexes[$i][1])/($vertexes[$j][1]-$vertexes[$i][1])*($vertexes[$j][0]-$vertexes[$i][0]) < $point[0]) { // < 改成 != 也行,前面的逻辑已经过滤了>的情况
                $oddNodes=!$oddNodes;
            } else {
                return false; // 测试点落在多边形上,结果按实际情况决定
            }
        }
        $j = $i;
    }
    return $oddNodes;
}
// 使用
$vertexes = array(array(116,90),array(83,244),array(188,213),array(366,318),array(424,29),array(235,13));
$point = array(127,205);
if(pointInPolygon($vertexes, $point)){
    echo "在多边形内";
} else {
    echo "在多边形外";
}

对于GPS坐标,如果多边形被限制在相对较小的区域,如一个城市,那么这个算法是没有什么问题的。
因为地球不是一个平面,所以如果你的多边形角上的地理坐标数据跨了变更线(360度和-360度的重合),就可能会出现问题,就可能需要在某些角的数据上增加或减少 360来避免错误。

参考论文 Point-In-Polygon Algorithm — Determining Whether A Point Is Inside A Complex Polygon

绘制围栏

绘制围栏可以用HTML 5的Canvas来做,我的实现 预览

Leave a Reply

Your email address will not be published. Required fields are marked *