查找 2D 平面上的 2 个物体是否会发生碰撞的算法
我试图根据以下信息确定 Object1 是否会与 Object2 发生碰撞：
1) 对象的边界框（使用边界框碰撞检测）
2) 对象的速度
3) 对象的当前位置（x, y 坐标）
4) 对象' 方向（上、下、左或右）
对于一些图像，想象一下物体在 2D 网格上移动，它们只能在该网格的线上移动。
因此，鉴于上述信息，我需要一种高效且可读的算法来确定这些对象是否会发生碰撞。我所说的高效是指恒定的时间，并且最小化计算所花费的时间。伪代码或链接都可以。
I'm trying to determine whether Object1 will collide with Object2 given the following information:
1) Objects' bounding boxes (uses bounded-box collision detection)
2) Objects' speeds
3) Object's current locations (x, y coordinate)
4) Objects' directions (Up, Down, Left, or Right)
For a bit of imagery, imagine the objects traveling on a 2D grid, and they can only move on the lines of that grid.
So given the above information, I need an efficient, but readable algorithm to determine whether those objects will collide. By efficient I mean constant time with time spent on computations minimized. Psuedocode or a link is fine.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先，找到框在 X 轴上重叠的时间间隔。
其次，找出方框在 Y 轴上重叠的时间间隔。
最后，检查两个时间间隔是否重叠。如果是这样，则两个间隔中的最早时间点就是它们将要碰撞的时刻。
First, find the time interval during which the boxes will overlap on the X axis.
Second, find the time interval during which the boxes will overlap on the Y axis.
Finally, check if the two time intervals overlap. If so, the earliest point in time that is in both intervals is the moment they are going to collide.
您正在寻找的称为“移动凸物体的分离轴测试”。
以下是解释详细信息的 Google 图书链接：
http://books.google.de/books?id=WGpL6Sk9qNAC&pg=PA219&lpg=PA219&dq=separating+axis+test+movement&源=bl&ots=Pl5MmM1bfQ&sig=_1VXYm5WFaV9AFj0ws63SAPtjck&hl=de&ei=coVVTML3BtGVOI26oJ8O&sa=X&oi=book_result&ct=结果&resnum=3&ved=0CCIQ6AEwAg#v=onepage& q=分离%20轴% 20test%20movement&f=false
（抱歉链接太大 - 这不是我的主意）
What you are looking for is called "Separating Axis test for moving convex Objects".
Here is a link to google books that explains the details:
http://books.google.de/books?id=WGpL6Sk9qNAC&pg=PA219&lpg=PA219&dq=separating+axis+test+movement&source=bl&ots=Pl5MmM1bfQ&sig=_1VXYm5WFaV9AFj0ws63SAPtjck&hl=de&ei=coVVTML3BtGVOI26oJ8O&sa=X&oi=book_result&ct=result&resnum=3&ved=0CCIQ6AEwAg#v=onepage&q=separating%20axis%20test%20movement&f=false
(sorry for the large link - it wasn't my idea)
最好的方法是计算出：
然后测试两个时间范围是否重叠相交。这将作为额外的奖励给你碰撞时间。
总体而言，这将是一个简单的恒定时间操作。
Your best approach is to work out:
And then test if the two time ranges intersect. This will as an added bonus give you the collision time.
This will be a simple constant time operation overall.