分离轴定理和Python
分离轴定理和Python
我目前正在做的是：
创建与2个矩形的4条边垂直的4个轴。由于它们是矩形，我不需要为每条边生成一个轴（法线）。
然后我循环遍历我的4个轴。
对于每个轴：
我将每个矩形的每个角投影到轴上。
有两个包含这些投影的列表（数组），一个用于每个矩形。
然后我得到每个投影和轴的点积。这返回一个标量值，可用于确定最小值和最大值。
现在这两个列表包含的是标量而不是向量。我对列表进行排序，以便轻松选择最小值和最大值。如果盒子B的最小值> =盒子A的最大值或盒子B的最大值<=盒子A的最小值，则在该轴上没有碰撞，对象之间没有碰撞。
此时函数结束并跳出循环。
如果所有轴都不满足这些条件，则发生碰撞。
希望这是正确的做法。
Python代码本身可以在这里找到：http://pastebin.com/vNFP3mAb
另外：
我遇到的问题是上述代码不起作用。它总是检测到碰撞，即使没有碰撞。我所输入的正是代码所做的事情。如果我漏掉了任何步骤或者对SAT工作原理的理解有误，请告诉我。
分离轴定理和Python的问题出现的原因是代码中存在错误。首先，投影应该只是一个顶点与轴的点积，而不是像你现在做的那样过于复杂。其次，获取轴的方法是错误的。你写的代码是这样的：
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的回答。一旦我将角落投影到轴上，就可以找到在任一方向上最远的两个角落（每个矩形）。这可以通过测量两个坐标之间的距离来完成。我现在明白了这个原理。当我解决问题后，我会发布我的解决方案。
关于“过于复杂”的问题，我对矩形的表示方式感到不舒服。没有明确地表示矩形的旋转角度。相反，表示似乎是一个一般的四边形，即四个点只是简单地标记为“左上角”，“右上角”等等。结果的八个坐标太一般化了，所以你必须依赖于填充它们的代码来使它们保持一致。一个更严格的表示（中心、宽度、高度、旋转角度）可以强制执行定义旋转矩形的约束。
：是的，我同意这是一个一般的四边形，但他的SAT实现也计算了所有4个边的轴，所以只要它们是凸的，它应该工作。
@Bruk Habtu: 你仍然希望查找最小值和最大值，就像你现在做的一样。不要担心点积是有符号的，或者没有特定的顶点在零点附近 - 这是相对的。
我遵循了你的建议。但是即使物体彼此之间根本没有接触，代码仍然检测到它们发生了碰撞。一旦我有了所有角落的投影，我通过检查每个点之间的长度来确定最小值和最大值。我确定这是我遗漏的一个小细节。[pastebin链接](http://pastebin.com/7yGWF5AG)
Habtu: 在你的min/max测试中发现了另一个错误。请参考更新。
分离轴定理（Separating Axis Theorem）是一种用于判断两个矩形是否相交的方法。在实际应用中，为了提高效率，可以采用一些优化方法。
首先，可以通过检查两个矩形的外接圆是否相交来快速判断它们是否相交。矩形的外接圆是以矩形的对角线中点为圆心，对角线长度为直径的圆。如果两个矩形的中心点之间的距离大于两个圆的半径之和，那么它们的外接圆不相交，因此矩形也不会相交。这种方法可以提前结束判断，避免进行后续的复杂计算。
另一种优化方法是检查一个矩形的顶点是否在另一个矩形内部。将一个矩形平移到原点，并将其边与坐标轴平行，这样就可以通过在与另一个矩形的边平行的轴上投影一个矩形的顶点来判断它是否在另一个矩形内部。如果发现一个矩形的顶点在另一个矩形内部，那么这两个矩形显然相交。虽然这只是一个充分条件而不是必要条件，但它可以提前结束判断，得出相交的结论，而不需要找到分离轴。
分离轴定理可以通过优化方法来提高判断两个矩形是否相交的效率。通过检查矩形的外接圆是否相交和检查一个矩形的顶点是否在另一个矩形内部，可以提前结束判断，避免进行不必要的计算，从而提高程序的执行效率。