分离轴定理和 Python

Question

这就是我目前正在做的事情：

创建垂直于 2 个矩形的 4 个边的 4 个轴。由于它们是矩形，我不需要为每个边生成一个轴（法线）。

然后我循环我的 4 个轴。

因此对于每个轴： 我得到了矩形每个角在轴上的投影。 有 2 个列表（数组）包含这些投影。每个矩形一个。 然后我得到每个投影和轴的点积。这返回一个标量值 可用于确定最小值和最大值。

现在这两个列表包含标量而不是向量。我对列表进行排序，以便可以轻松选择最小值和最大值。如果框 B 的最小值 >= 框 A 的最大值或框 B 的最大值 <= 框 A 的最小值，则该轴上不存在碰撞，并且对象之间也不存在碰撞。

此时函数结束并且循环中断。

如果所有轴都不满足这些条件，那么我们就会发生碰撞，

我希望这是正确的方法。

python 代码本身可以在这里找到 http://pastebin.com/vNFP3mAb

另外： http://www.gamedev.net/page/reference/index.html/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604

问题我的问题是上面的代码不起作用。即使没有碰撞，它也始终会检测到碰撞。我输入的正是代码正在做的事情。如果我遗漏了任何步骤或者只是不明白 SAT 的工作原理，请告诉我。

Answer 1

一般来说，有必要执行问题中概述的步骤来确定矩形是否“碰撞”（相交），请注意，正如OP所做的那样，一旦分离轴我们就可以打破（得出不相交的结论）被发现。

有几种简单的方法可以“优化”，为提前退出提供机会。这些的实用价值取决于所检查的矩形的分布，但两者都很容易合并到现有框架中。

(1) 边界圆检查

证明不相交的一种快速方法是显示两个矩形的边界圆不相交。矩形的外接圆共享其中心，即任一对角线的中点，并且直径等于任一对角线的长度。如果两个圆心之间的距离超过两个圆的半径之和，则两个圆不相交。因此矩形也不能相交。如果目的是找到分离轴，那么我们还没有实现。但是，如果我们只想知道矩形是否“碰撞”，则可以提前退出。

(2) 一个矩形在另一个矩形内部的顶点

一个矩形的顶点在与另一个矩形边缘平行的轴上的投影提供了足够的信息来检测该顶点何时在另一个矩形内部。当后一个矩形已平移且未旋转到原点（边缘平行于普通轴）时，此检查尤其容易。如果一个矩形的顶点恰好在另一个矩形的内部，则这些矩形显然是相交的。当然，这是相交的充分条件，而不是必要条件。但它允许提前退出并得出交叉点（当然，无需找到分离轴，因为不存在任何分离轴）。

Answer 2

我发现有两件事是错误的。首先，投影应该只是顶点与轴的点积。你正在做的事情太复杂了。其次，您获取轴的方式不正确。你写：

Axis1 = [  -(A_TR[0] - A_TL[0]),
             A_TR[1] - A_TL[1] ]

应该读到的地方：

Axis1 = [  -(A_TR[1] - A_TL[1]),
             A_TR[0] - A_TL[0] ]

区别在于坐标确实给了你一个向量，但要获得垂直线，你需要交换 x 和 y 值并对其中之一求负。

希望有帮助。

发现了另一个错误

编辑在这段代码中

if not ( B_Scalars[0] <= A_Scalars[3] or B_Scalars[3] >= A_Scalars[0] ):
            #no overlap so no collision
            return 0

：应该是：

if not ( B_Scalars[3] <= A_Scalars[0] or A_Scalars[3] <= B_Scalars[0] ):

排序为您提供了一个价值不断增加的列表。因此 [1,2,3,4] 和 [10,11,12,13] 不重叠，因为后者的最小值大于前者的最大值。第二个比较是交换输入集时的比较。