java - 保证多边形法线的向外方向

Question

我正在尝试用 Java 编写一个使用分离轴定理进行碰撞检测的 2D 游戏。为了解决两个多边形之间的碰撞，我需要知道碰撞的最小平移 vector ，并且我需要知道它相对于多边形指向哪个方向(以便我可以给一个多边形一个沿该方向的惩罚力和另一个相反方向的惩罚力)。作为引用，我正在尝试实现算法 here .

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

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

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

Answer 1

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

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

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