如何知道矩形是否碰到这种形状？

Question

我有一个矩形，我想知道是否有碰撞的形状像这样：http://i.stack.imgur.com/8RMQZ.png

我见过的算法，比如这个：

function intersectRect(r1, r2) { 
    return !(r2.left > r1.right || 
      r2.right < r1.left || 
      r2.top > r1.bottom || 
      r2.bottom < r1.top); 
} 

但是，只有当两者都是矩形作品。那么我怎么弄出一个矩形和那个形状。

Answer 1

我不这样做往往，但你可以这样来做：

• 检查是否有4个矩形的是多边形内部
• 检查任何的（10？多边形的）点位于矩形

所以这可能是沦为“point in polygon”的问题里面。同样，可能有更好的解决方案。

Answer 2

你应该看看基于“分离轴定理”的算法。它几乎是快速二维碰撞检测的标准，因为它（你可能已经猜到了）速度非常快（根本不涉及像sin/cos/sqrt/exp这样的任何分割或昂贵的操作），也适用于任何可能的凸面形状（甚至是圆圈）。

这里有一个很好的教程解释它：http://www.codezealot.org/archives/55

一件事，使得它如此之快是算法具有“早期输出”的场景，在这里你测试一个轴，如果它不返回预期的结果，你可以退出整个算法，知道形状不会相互碰撞。

该文章的一个不错的副作用是它吐出了需要将碰撞形状分开的最小可能位移矢量。