BeWithYou

胡搞的技术博客

  1. 首页
  2. 数据结构/实用算法/知识
  3. 判断点是否在多边形内部

判断点是否在多边形内部


判断点是否在多边形内部

前段时间在山寨一个agar.io游戏,用PHP重写了游戏后台逻辑,前端部分修改了websocket部分,保留了所有的业务逻辑。其中用到了2D碰撞检测的一些知识。 原来的复刻版agar.io-clone用的是nodejs里的库,但是PHP里并没有对应的实现。于是只能自己手动翻译成PHP代码,并且提交到了packagist上。这也是我发布的第一个composer包。 但是原版的库中有一个不正确的地方,判断点与多边形的位置关系时使用了错误的方法。我给作者提了一个issue,并且得到了作者的修正(虽然修正方式并不完美)。这里给出一种标准解法。

常用的方法

  1. 回转数法
    将点与多边形的所有顶点连接起来,按顺序回转一圈,计算夹角的角度和。注意这里角度是有正负之分的。当角度和为0时,则表示点在多边形的外面。盗一个图: 示例图

  2. 射线法
    由点出发做一条射线,为了简单起见,我们可以直接选择水平向左向右。如果射线与多边形交点的个数为奇数,则点在多边形内部,否则在外部。这里射线与定点相交,只计算一次。 再盗一个图: 示例图

选择哪一种?

这里选择射线法。虽然角度我们可以通过atan2方法获取到,但毕竟不精确,求角度和的话也可能存在偏差。直观的来看,还是选择射线法。

代码实现

这里贴上我的SAT库里的判断代码

/**
 * Check if a point is inside a convex polygon.
 * @param Vector $point
 * @param Polygon $poly
 * @return mixed
 */
public static function pointInPolygon(Vector $point, Polygon $poly)
{
    $len = count($poly->calcPoints);
    $p = clone $point;
    $p->sub($poly->pos);
    $j = $len - 1;
    $flag = false;
    for ($i = 0; $i < $len; $i++) {
        $p1 = $poly->calcPoints[$i];
        $p2 = $poly->calcPoints[$j];
        if ($p1->x == $p->x && $p1->y == $p->y) {
            return true;
        }
        if ($p2->x == $p->x && $p2->y == $p->y) {
            return true;
        }
        // 判断线段两端点是否在射线两侧
        if (($p1->y < $p->y && $p2->y >= $p->y) || ($p1->y >= $p->y && $p2->y < $p->y)) {
            // 线段上与射线 Y 坐标相同的点的 X 坐标
            $x = $p1->x + ($p->y - $p1->y) * ($p2->x - $p1->x) / ($p2->y - $p1->y);
            // 点在多边形的边上
            if ($x === $p->x) {
                return true;
            }
            // 射线穿过多边形的边界
            if ($x > $p->x) {
                $flag = !$flag;
            }
        }
        $j = $i;
    }
    return $flag;
}

其中Vector和Polygon是之前定义好的类。并且认为点在边上也算是在多边形内部。这里的多边形可以为任意凹凸多边形。

回到顶部