GPS电子围栏算法

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

DEMO

如何判断点在多边形内部

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

解决方案是比较多边形在红色测试点的Y(垂直)坐标的两侧的结点(多边形与测试点水平线所交叉形成的),如果有奇数个结点在测试点的Y坐标两侧,那么它在多边形内,如果有偶数个结点在测试点Y坐标两侧,那么它在多边形外。
上图中,测试点的左侧有5个结点,右侧有3个结点,因此它在多边形内。

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

特殊情况,边a和边b的都有终点在测试点的水平线上,这两条边都形成一个结点吗?显然不是。
产生结点的边的条件,必须有点在测试点的水平线上,必须有终点在测试点的水平线下。
所以a边产生结点,b边不产生,因为边b没有点在测试点的水平线下方。

对于一条边的完全落在测试点的水平线上,如上图的边d. d是不产生结点的,d没有点在测试点水平线下方,所以c产生一个结点,d和e都不产生结点。上图每侧分别产生1个结点,所以在多边形内。

这张图其实按照规则依然形得通。

对于测试点直接落在多边形上这种情况,则上面算法将产生不可预测的结果。

电子围栏算法PHP版

function pointInPolygon($vertexes, $point) {
    $polyCorners = count($vertexes);
    $i = 0;
    $j=$polyCorners-1 ;
    $oddNodes = 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] || $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;
            }
        }
        $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 "在多边形外";
}

Code In GitHub

对于GPS坐标,如果多边形被限制在相对较小的区域,如一个城市,那么这个算法是没有什么问题的。
因为地球不是一个平面,所以如果你的多边形跨了几个洲,可能会有影响,但实际上我们也不会有这种应用。

绘制围栏

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

Leave a Reply

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