分离轴定理和Python

Question

这是我当前正在做的事情：

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

然后我循环遍历我的4个轴。

所以对于每个轴： 我获取矩形的每个角落在轴上的投影。 有两个列表（数组），其中包含这些投影。每个矩形各一个。 然后我得到每个投影和轴的点积。这返回一个标量值， 可用于确定最小值和最大值。

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

此时函数完成并且循环中断。

如果所有轴都不满足这些条件，则存在碰撞

希望这是正确的方法。

这里可以找到Python代码http://pastebin.com/vNFP3mAb

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

我遇到的问题是上面的代码不起作用。它总是检测到碰撞，即使没有碰撞。我所输入的正是代码所执行的内容。如果我漏掉了任何步骤或者对SAT算法的工作原理有误解，请告诉我。

- Bruk Habtu

---

什么问题？ - user97370

对于更一般的凸多边形，我们会考虑与两个多边形的边缘平行的潜在分离轴，但由于您特别处理矩形，因此在这种情况下等同于要求垂直（或法线）于边缘的轴。 - hardmath

我遇到的问题是上面的代码不起作用。即使没有碰撞，它也总是检测到碰撞。抱歉表述不够清晰。我会编辑我写的内容，使其更加明确。 - Bruk Habtu

@hardmath。分离线将与边平行。分离轴是您投影点进行测试的方向向量，并且垂直于多边形的边缘。在三维中，分离轴垂直于面（即它是面法线）或每个对象的边缘的叉积 - 再次垂直于边缘。 - phkahler

@phkahler：你说得对，“超平面”对应于法向量，后者“轴”作为投影的目标是有意义的。 “超平面”的方程可以理解为将方向向量与未知数的向量点乘得到某个常数，如果适当归一化，则为方程的“正规形式”。 - hardmath

Answer 1

通常情况下，需要按照问题中提出的步骤确定矩形是否“碰撞”（相交），正如 OP 所述，一旦发现一个分离轴，就可以打断（得出不相交的结论）。

有几种简单的方法可以“优化”，以便提供更早的退出机会。这些方法的实际价值取决于要检查的矩形的分布，但两种方法都可以轻松地纳入现有框架中。

（1）外接圆检查

一种快速证明非交叉的方法是显示两个矩形的外接圆不相交。矩形的外接圆与其对角线的中点重合，并具有等于任意对角线长度的直径。如果两个中心之间的距离大于两个圆的半径之和，则圆不相交。因此，矩形也不可能相交。如果目的是找到分离轴，我们还没有完成。但是，如果我们只想知道矩形是否“碰撞”，这将允许提前退出。

（2）一个矩形的顶点在另一个矩形内部

将一个矩形的顶点投影到平行于另一个矩形边的轴上，就可以提供足够的信息来检测该顶点是否在另一个矩形内部。当后一个矩形被平移和旋转到原点（边与普通轴平行）时，这种检查特别容易。如果发现一个矩形的顶点在另一个矩形内部，那么这两个矩形显然相交。当然，这是一种充分条件而不是必要条件。但它允许提前退出并得出相交的结论（当然，不会找到分离轴，因为不存在）。

- hardmath

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

- phkahler

---

感谢您的回复，phkahler。一旦我将角落投影到轴上，就只需要找到在任何方向上最远的2个角（每个矩形）。这可以通过测量两个坐标之间的长度来完成。我现在认为我理解了这个过程。当我让它正常工作时，我会发布我的解决方案。 - Bruk Habtu

沿着“过于复杂”的思路，我对矩形的表示方式感到不舒服。没有明确地表示一个矩形旋转的角度。相反，表示似乎是一种普通的四边形，即仅标记为“左上角”，“右上角”等四个点。得到的八个坐标太笼统了，所以您必须依赖填充它们的代码来保持它们一致。更严格的表示（中心，宽度，高度，旋转角度）可以强制定义旋转的矩形。 - hardmath

@hardmath：是的，我同意这是一个普通的四边形，但他的SAT实现也为所有4条边计算一个轴，所以只要它们是凸形的，它就应该有效。 - phkahler

@ Bruk Habtu：你仍然想要像你现在这样寻找最小值和最大值。不用担心点积是带符号的或者没有特定的顶点在零点 - 这都是相对的。 - phkahler

@phkahler 我按照你的建议做了，但代码仍然会检测到即使彼此远离的物体碰撞。一旦我得到了所有角落的投影，我检查哪些是最小和最大值，方法是检查每个点之间的距离长度。我相信我错过了一些小细节。 http://pastebin.com/7yGWF5AG - Bruk Habtu

@Bruk Habtu：在你的最小/最大值测试中发现另一个错误。请查看更新。 - phkahler