分离轴定理与Python

Question

我现在正在做的事情是：

创建4个轴，这些轴与2个矩形的4条边垂直。因为它们是矩形，所以我不需要为每条边生成一个轴（法线）。

然后我会遍历这4个轴。

对于每个轴： 我会计算矩形每个角落在这个轴上的投影。 有两个列表（数组）来存放这些投影，每个矩形一个列表。 接着，我会计算每个投影和轴的点积。这个计算会返回一个标量值， 可以用来确定最小值和最大值。

现在这两个列表里存的是标量，而不是向量。我会对这些列表进行排序，这样就能轻松找到最小值和最大值。如果矩形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

一般来说，我们需要按照问题中提到的步骤来判断两个矩形是否“碰撞”（相交）。正如提问者所说，只要找到一个可以分开的轴，我们就可以得出不相交的结论，直接结束检查。

有几种简单的方法可以“优化”这个过程，让我们更早地得出结果。这些方法的实际效果取决于被检查的矩形的分布情况，但都很容易加入到现有的框架中。

(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] 是不重叠的，因为后者的最小值大于前者的最大值。第二个比较是针对输入集合交换的情况。