判断点是否在多边形内部
判断点是否在多边形内部
前段时间在山寨一个agar.io游戏,用PHP重写了游戏后台逻辑,前端部分修改了websocket部分,保留了所有的业务逻辑。其中用到了2D碰撞检测的一些知识。 原来的复刻版agar.io-clone用的是nodejs里的库,但是PHP里并没有对应的实现。于是只能自己手动翻译成PHP代码,并且提交到了packagist上。这也是我发布的第一个composer包。 但是原版的库中有一个不正确的地方,判断点与多边形的位置关系时使用了错误的方法。我给作者提了一个issue,并且得到了作者的修正(虽然修正方式并不完美)。这里给出一种标准解法。
常用的方法
-
回转数法
将点与多边形的所有顶点连接起来,按顺序回转一圈,计算夹角的角度和。注意这里角度是有正负之分的。当角度和为0时,则表示点在多边形的外面。盗一个图: - 射线法
由点出发做一条射线,为了简单起见,我们可以直接选择水平向左向右。如果射线与多边形交点的个数为奇数,则点在多边形内部,否则在外部。这里射线与定点相交,只计算一次。 再盗一个图:
选择哪一种?
这里选择射线法。虽然角度我们可以通过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是之前定义好的类。并且认为点在边上也算是在多边形内部。这里的多边形可以为任意凹凸多边形。