分离轴定理和Python

这就是我目前正在做的：分离轴定理和Python

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

我然后循环我的4个轴。

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

现在2个列表包含标量而不是向量。我对列表进行排序，以便轻松选择最小值和最大值。如果框B的最小值> =框A的最大值或框B的最大值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如何工作，请告诉我。

来源

2011-05-16 Bruk Habtu

这是什么问题？ – 2011-05-16 06:02:16

对于更一般的凸多边形，我们会考虑与两个多边形的边平行*的潜在分离轴，但由于您具体处理矩形，所以在这种情况下要求垂直于（或正常）轴以边缘。 – hardmath 2011-05-16 09:26:49

我遇到的问题是上面的代码不起作用。即使在没有碰撞的情况下，它也会始终检测到碰撞。对不起，不清楚。我将编辑我写的内容，以便更清楚。 – 2011-05-16 17:15:07

我看到两件事情是错误的。首先，投影应该只是顶点与轴的点积。你所做的事情太复杂了。其次，你得到你的轴的方式是不正确的。你写：

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

来源

2011-05-16 19:22:11 phkahler

感谢回应phkahler。一旦我将投影到这个轴上的角落，找到在任一方向上最远的两个角（每个矩形）就是问题了吗？这可以通过测量2个坐标之间的长度来完成。我想我明白这是如何工作的。当我得到它的工作时，我会发布我的解决方案。 – 2011-05-16 20:47:45

沿着“方式太复杂”的路线行事，我对表示矩形的方式感到不舒服。没有明确表示矩形的旋转角度。相反，表示法似乎是一般四边形的表示法，即四个简单标记为“左上”，“右上”等的点。由此产生的八个坐标过于笼统，因此您必须依靠填充它们的代码让他们一致。更严格的表示（中心，宽度，高度，旋转角度）可以强制定义旋转的矩形。 – hardmath 2011-05-17 01:51:56

@hardmath：是的我同意这是一个普通的四边形，但是他的SAT的实现也计算了所有4边的轴，所以只要它们是凸的就应该工作。 – phkahler 2011-05-17 18:41:28

一般来说，需要执行问题中概述的步骤以确定矩形是否“碰撞”（相交），并注意到OP会尽快断开（以非交叉的结论）作为分离轴被找到。

在提供早期退出机会的意义上，有几种简单的“优化”方法。这些的实际价值取决于正在检查的矩形的分布，但两者都很容易并入现有框架。

（1）外接圆检查

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

（2）的另一

平行于另一个矩形的边缘一个矩形的上轴的顶点的投影内的一个矩形的顶点提供足够的信息来检测何时该顶点是其他矩形内。当后一个矩形已经平移并且未旋转到原点时（这些边与普通轴平行），此检查特别容易。如果碰巧一个矩形的顶点在另一个矩形的内部，矩形显然相交。当然，这是一个交叉点的充分条件，而不是必要条件。但它允许提前结束交集（并且当然没有找到分离轴，因为都不存在）。

来源

2011-05-16 11:11:32 hardmath

分离轴定理和Python

回答

相关问题