GPS电子围栏算法

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

DEMO

如何判断点在多边形内部

参考论文 Point-In-Polygon Algorithm — Determining Whether A Point Is Inside A Complex Polygon
例如我们要判断下图中这个红点是否在这个多边形内

解决方案是在红色测试点上引一条射线,看射线与多边形有多少个交点,如果有奇数个交点则测试点在多边形内,如果是偶数个则测试点在多边形外。还有些特殊情况,下面会提到。
上图中,测试点的左侧水平射线有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来避免错误。

绘制围栏

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

Leave a Reply

Your email address will not be published.