不规则形状的碰撞检测

Question

我知道如何检查一个圆是否要与一个正方形相撞，我知道如何检测一个正方形是否要与一个正方形相撞，但是如果一个多边形要与一个正方形相撞，我该如何检测呢？

或者更好的是，当一个多边形将要与另一个多边形碰撞时。

或者更好的是，当由非直线组成的形状与另一个类似的形状(多边形或圆形/矩形)发生冲突时

有什么方法可以得到一个图形可能占用的像素和另一个图形可能占用的像素，并检查它们是否相同？

我希望有一些解决方案不需要大量的形状特定计算。

我使用javascript和html5画布来实现这一点。

Answer 1

最简单的方法是使用边界框，只需找到物体的mins和maxs并从中制作一个框。要做一个多边形到另一个多边形，你需要一种方法来存储多边形的边缘，另一种方法来确定哪些点或边缘与另一个物体发生了碰撞。从这里你可以决定如何对碰撞做出反应。

边界框实现起来很简单，但并不十分精确。使用多边形本身的实际边更精确，但更难处理，速度也慢得多。

Answer 2

这不是一件简单的事情。如果你对一个函数可以判断两个多边形是否正在碰撞（并且你可以回滚它们）感到满意，那么解决方案并不难。你只需要检查多边形的任何两条边是否相互交叉。这可以通过一些数学来完成，对于大形状或大量多边形，它会侵蚀性能。为了解决这个问题，你可以使用空间分区和边界卷。

更新：可以基于此计算线的交点。然后您需要检查该点是否位于两个线段中。为此，可以使用线段的endpoint，如果线段实际包含点，则ua和ub变量将介于0-1之间。