logo标签列表

如何确定一个二维点是否在多边形内？（涉及IT技术）

performancegraphicscollision-detectionpolygonpoint-in-polygon
605

我正在尝试创建一个快速的2D点在多边形内部算法，用于命中测试（例如Polygon.contains(p:Point)）。欢迎提供有效技巧建议。

您忘了告诉我们关于左右利手的问题您的看法——这也可以被解释为“内部”与“外部”。 - Richard T
17
是的，我现在意识到这个问题留下了许多未指定的细节，但目前我有点想看看各种回答的多样性。 - Scott Evernden
5
一个拥有90个面的多边形被称为九十边形（或称九角形），一个拥有10,000个面的多边形被称为万边形。 - user263678
1
“最优雅”已经不是目标了，因为我一直在寻找一个“能够工作”的算法。我必须自己想出来：https://dev59.com/GmUq5IYBdhLWcg3wEcVZ#18190354 - davidkonrad
这个库已经实现了它，所以你只需要在 Python 中使用 point.within(polygon)，它会返回一个布尔值，表示点是否在多边形内部。 - J Agustin Barrachina
42个回答
0
重心坐标可以用来描述三角形内点的位置。它们表示点与三角形顶点之间距离的比例。
在具有顶点A、B和C的三角形中，任何位于三角形内部的点P都可以用重心坐标（u，v，w）表示，其中u、v和w分别表示点P与顶点A、B和C之间的距离比例。这些坐标必须满足条件u + v + w = 1。
值得注意的是，重心坐标适用于任何多边形，无论其形状如何。
对于凹多边形，点在多边形内部的重心坐标仍然由点与顶点之间的距离比例确定。唯一的区别是，一些重心坐标可能为负，表示点位于多边形外部。在这种情况下，坐标的总和将不等于1。
同样地，对于凸多边形，点在多边形内部的重心坐标将始终为非负，并且总和为1。
无论形状是凹的还是凸的，都不会影响重心坐标的计算。关键是要确保根据点与多边形顶点之间的相对距离正确地计算出坐标。
下面是一个用Matlab实现的四个顶点形状的示例。
function isInside = isPointInsideQuadrilateral(x, y, x1, y1, x2, y2, x3, y3, x4, y4)
    % Calculate barycentric coordinates
    denominator1 = (y2 - y1)*(x4 - x1) + (x1 - x2)*(y4 - y1);
    alpha1 = ((y2 - y1)*(x - x1) + (x1 - x2)*(y - y1)) / denominator1;
    beta1 = ((y1 - y4)*(x - x1) + (x4 - x1)*(y - y1)) / denominator1;
    gamma1 = 1 - alpha1 - beta1;

    denominator2 = (y3 - y2)*(x4 - x2) + (x2 - x3)*(y4 - y2);
    alpha2 = ((y3 - y2)*(x - x2) + (x2 - x3)*(y - y2)) / denominator2;
    beta2 = ((y2 - y4)*(x - x2) + (x4 - x2)*(y - y2)) / denominator2;
    gamma2 = 1 - alpha2 - beta2;

    isInside = (alpha1 >= 0 && beta1 >= 0 && gamma1 >= 0) || (alpha2 >= 0 && beta2 >= 0 && gamma2 >= 0);
end

这种技术非常快速且精确度很高。
-1

这仅适用于凸形状，但Minkowski Portal Refinement和GJK也是测试点是否在多边形中的绝佳选择。您可以使用Minkowski减法将点从多边形中减去，然后运行这些算法以查看多边形是否包含原点。

此外，有趣的是，您可以使用支持函数来更加隐式地描述您的形状，该函数以方向向量作为输入并输出沿该向量最远的点。这使您可以描述任何凸形状..弯曲的，由多边形组成的或混合的。您还可以执行操作以组合简单支持函数的结果以制作更复杂的形状。

更多信息： http://xenocollide.snethen.com/mpr2d.html

此外，游戏编程宝典7讨论了如何在3D中实现此目标（：

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接