判断点是否在多边形内部

前段时间在山寨一个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是之前定义好的类。并且认为点在边上也算是在多边形内部。这里的多边形可以为任意凹凸多边形。