2

我正在尝试用 Java 编写一个使用分离轴定理进行碰撞检测的 2D 游戏。为了解决两个多边形之间的碰撞，我需要知道碰撞的最小平移向量，并且我需要知道它相对于多边形指向哪个方向（这样我就可以给一个多边形沿着那个方向的惩罚力和其他方向相反的惩罚力）。作为参考，我正在尝试在这里实现算法。

我想保证，如果我调用我的碰撞检测函数collide(Polygon polygon1, Polygon polygon2)并且它检测到碰撞，返回的 MTV 将始终指向远离多边形1的多边形 2。为了做到这一点，我需要保证我生成的分离轴，即多边形边缘的法线，总是指向远离生成它们的多边形。（这样，我知道在将它用作 MTV 之前，要否定来自 polygon2 的任何轴）。

不幸的是，似乎我为多边形边缘生成的法线是指向多边形内部还是外部，取决于多边形的点是按顺时针还是逆时针顺序声明的。我正在使用此处描述的算法生成法线，并假设我选择(x, y) => (y, -x)“垂直”方法，如果我以顺时针顺序遍历顶点，则生成的法线只会指向远离多边形。

鉴于我不能强制客户端以顺时针顺序声明多边形的点（我正在使用 java.awt.Polygon，它只为 x 和 y 坐标公开两个数组），是否有一种数学方法可以保证我生成的法线向量的方向是朝向多边形的外部吗？我不太擅长矢量数学，所以我可能缺少一个明显的解决方案。大多数关于 SAT 的 Internet 资源只是假设您始终可以按顺时针顺序遍历多边形的顶点。

4

2 回答 2

2

例如，您可以使用此问题的答案来计算每个多边形的排序方向，然后如果两个多边形具有不同的顺序，则将您的法线乘以 -1。

您还可以再次使用上述算法检查传递给算法的每个多边形以查看其排序是否错误，并在必要时反转顶点顺序。

请注意，在计算顶点顺序时，某些算法适用于所有多边形，而有些算法仅适用于凸多边形。

于 2012-07-18T19:40:59.090 回答
1

我终于想通了，但发布的一个答案不是完整的解决方案，所以我不会接受它。我能够使用此 SO 答案中描述的基本算法来确定多边形的顺序（在 David Norman 的链接中也描述得不太清楚），即：

for each edge in polygon:
    sum += (x2 - x1) * (y2 + y1)

但是，有一个重要的警告，这些答案都没有提到。通常，如果总和为正，您可以决定多边形的顶点是顺时针方向的，如果总和是负的，则决定多边形的顶点是逆时针方向的。但是在 Java 的 2D 图形系统中，这种比较是倒置的，实际上在许多图形系统中，因为正 y 轴指向下方。所以在一个正常的数学坐标系中，你可以说

if sum > 0 then polygon is clockwise

但在带有倒置 y 轴的图形坐标系中，它实际上是

if sum < 0 then polygon is clockwise

我使用 Java 的 Polygon 的实际代码看起来像这样：

//First, find the normals as if the polygon was clockwise

int sum = 0;
for(int i = 0; i < polygon.npoints; i++) {
    int nextI = (i + 1 == polygon.npoints ? 0 : i + 1);
    sum += (polygon.xpoints[nextI] - polygon.xpoints[i]) * 
        (polygon.ypoints[nextI] + polygon.ypoints[i]);
}

if(sum > 0) {
    //reverse all the normals (multiply them by -1)
}
于 2012-07-22T00:08:27.667 回答