围栏算法研究与实现

Publish: April 18, 2017 Category: 编程,代码分享 No Comments

实际应用中常用的解决方法。

1.1 方法选择

实现电子围栏的方法选择 判断点是否在电子围栏内/外,用数学来描述就是判断一个点是在多边形内/外部,为 了方便,这里的多边形默认为有向多边形,规定沿多边形的正向,边的左侧为多边形的外侧 域,即多边形边按顺时针方向遍历。比较常见的判断点与多边形关系的算法有射线法、点线判断法、夹角和法等[3],不过只有射线法可以正确用于凹多边形,其他 2 个只可以用于凸多 边形。

点线判断法 把多边形的每条边看作首尾相连的有向线段。如果一个点相对于多边形的每条边(有向 线段)的方向(左侧还是右侧)都相同,那么这个点就在这个多边形内部。这种方法只适用于凸多边形,而不适用于凹多边形。定义点在有向线段的一侧,定义有向线段(x1,y1),(x2,y2), 对于点(x, y)计算:

v = (x2-x1)*(y-y1) - (y2-y1)*(x-x1)

v=0 表示点在线段所在的直线上,v>0 表示点在线段的左侧,v<0 表示点在线段的右侧。 上面的计算式也可以表示比较斜率的大小:

 (y-y1)/(x-x1) > (y2-x1)/(x2-x1) 

射线法 是使用最广泛的算法,相比较其他算法而言,它不但可以正确使用在凹多边形上,而且 不需要考虑精度误差问题。该算法思想是从点水平出发做一条射线,计算该射线与多边形的 边的相交点个数,当点不在多边形边上时,如果是奇数,那么点就一定在多边形内部,否则, 在外部。射线法原理示意图如图所示。

截图.png

如图上所示,射线与多边形的左右交点数分别为 5 和 3,均是奇数,则点 p(红点) 在多边形内;在多边形外部的点与多边形交点数是偶数,则点在多边形外面。以上所述的是射线法算法的基本思想,适合于大多数被判断点和多边形的位置关系,但是也有一些特殊的 位置关系的判断结果是错误的。

以下将列举这些特殊情况:
射线过水平边,如图1.2。显然,根据射线算法基本思想则无法判定点与多边形的位置关系。

射线法特殊情况

射线过顶点,如图 1.3

射线法特殊情况2

在图 1.3 中,多边形中的一个内角刚好接触测试点射线。 在上图中,只有一个侧面(以红色突出显示)产生的测试点的左侧的节点为偶数,在底部也是相同的情况。无论哪种方式, 数目为奇数才能表示测试点在多边形内部,然而测试点将在多边形内部其节点被视为偶数。 显然,根据射线算法基本思想无法判定点与多边形的位置关系。

夹角和法
如图 1.4,在多边形内或外有一点,将这一点与多边形的各个角相连,构成夹角,为 <1、 <2 、<3、<4 、<5 和 <6 ,把这些夹角相加便得到夹角和,为方便起见,记此夹角和为 a。规定正向为顺时针旋转方向,负向为逆时针方向[4]。当 a!=2π 时,则被判断点在多边形 的外部;当 a=2π 时,则被判断点在多边形的内部。

夹角和法原理

若被判断点是多边形的某个顶点,则其中有一个夹角必定等于 0;若被判断点在多边形 的某条边上,则其中有一个夹角必定等于 0 或者 180 度。一般用点积法来求解两条射线的夹 角,具体步骤如下所示: 假设点 P、p1 和 p2 的坐标分别为(x, y)、(xl, yl)和(x2,y2),向量 vl = pl-p,向量 v2 = p2-p。
由点积公式可得:

夹角和法公式

由公式(1-3),可以求得 <1 的夹角,同样可以得到其他角的值,把他们相加得到夹 角和。由以上可知,射线法算法在判定被判断点与多边形位置关系时是存在局限性的。而夹 角和法和点线判断法只可以用于凸多边形,然而围栏形状是多变的,可能是凸多边形也可能 是凹多边形。从解决问题的广度上来说,射线法是最适合的方法。

1.2 射线法的改进

改进的射线法[5]主要体现在以下几个方面:
(1)射线穿越一条线段需要线段两个端点分别在射线两侧。只要想通这一点,顶点穿 越的问题就解决了。这样一来,我们只需要在算法的代码里规定被射线穿越的线段的两个端 点算作射线两侧。
(2)点和多边形顶点重合的情况,这种情况可以直接比较点坐标和多边形顶点的坐标 是否相同就行了。

如果有射线连续经过的两个顶点显然都位于射线一侧这种情况,根据上面的假设,这种 情况可以看作没有发生穿越,射线上的这两个顶点不算在内。由于第(1)点的解决方案实 际上已经覆盖到这种特例,因此不需要再做特别的处理。下面给出算法实现的核心代码:

/** 
* 射线法判断点是否在多边形内部 
    * @param {Object} p 待判断的点,格式:{ x: X 坐标, y: Y 坐标 } 
    * @param {Array} poly 多边形顶点,数组成员的格式同 p 
    * @return {boolean} 点 p 和多边形 poly 的几何关系,如果是在内部,则为 true,否则为 false 
    */ 
    Boolean isInLine(p, poly) { 
    String px = p.x;
    String py = p.y;
    boolean flag = false; 
    for(int i = 0, i = poly.length, j = l - 1; i < l; j = i, i++) { 
    String sx = poly[i].x, 
    String sy = poly[i].y, 
    String tx = poly[j].x,
    String ty = poly[j].y
    
    // 点与多边形顶点重合 
    if((sx === px && sy === py) || (tx === px && ty === py)) { return true; }
    
    // 判断线段两端点是否在射线两侧 
    if((sy < py && ty >= py) || (sy >= py && ty < py)) { 
    // 线段上与射线 Y 坐标相同的点的 X 坐标 
    String x = sx + (py - sy) * (tx - sx) / (ty - sy); 
    // 点在多边形的边上
    if(x === px) { return true; } 
    // 射线穿过多边形的边界 
    if(x > px) {flag = !flag; } 
    } 
    } 
    // 射线穿过多边形边界的次数为奇数时点在多边形内
    return flag ? true : false; 
}

PHP实现

<?php
/**
 * 判断是位置是否在围栏内
 * @param array $point
 * @param array $poly
 * @return bool
 */
function is_inline($point = array(), $poly = array())
{
    $point_x = $point[0];
    $point_y = $point[1];

    $in_line = false;
    for ($i = 0, $L = count($poly), $j = $L - 1;
         $i < $L;
         $j = $i, $i++) {

        $sx = $poly$i;
        $sy = $poly$i;
        $tx = $poly$j;
        $ty = $poly$j;

        // 点与多边形顶点重合
        if (($sx === $point_x && $sy === $point_y) || ($tx === $point_x && $ty === $point_y)) {
            return true;
        }

        // 判断线段两端点是否在射线两侧
        if (($sy < $point_y && $ty >= $point_y) || ($sy >= $point_y && $ty < $point_y)) {
            // 线段上与射线 Y 坐标相同的点的 X 坐标
            $x = $sx + ($point_y - $sy) * ($tx - $sx) / ($ty - $sy);

            // 点在多边形的边上
            if ($x === $point_x) {
                return true;
            }

            // 射线穿过多边形的边界
            if ($x > $point_x) {
                $in_line = !$in_line;
            }
        }
    }

    return $in_line;
}

Demo: 下图是一个测试说明

构建如下数据:


<?php
//图数据
$poly_data =[
[3,2],
[6,1],
[8,2],
[8,8],
[6,6],
[3,8],
[1,5],
[6,3],
];
//点数据
$point_a = [2, 3];
$point_b = [5,5];

var_dump( is_inline($point_a, $poly_data) );
var_dump( is_inline($point_b, $poly_data) );

输出结果如下:

bool(false)
bool(true)

参考:基于 GPS 的电子围栏设计 朱安里,杜谦

Tags: 围栏算法, php围栏研究

Related Posts:

Leave a Comment