假设我有 N 架不同的飞机在大小为 400 公里 x 400 公里的二维矩形平面上飞行(即,就好像所有飞机都在同一高度飞行)。假设每架飞机都有一个随机生成的起点和终点。此外,假设飞机可以有不同的速度。我们假设两架飞机如果相距不到 10 公里就会“相撞”。根据这些信息,我如何有效地确定哪对飞机将不可避免地发生碰撞?
更新:据我所知,它需要类似于线段相交算法的东西,但不是一条宽度为零的线,它的厚度为 20 公里。我只是不确定如何将时间动态纳入检测算法。我想我可以在每个(小)时间步使用多边形交点来确定它们是否发生碰撞,但我想看看是否有更有效的方法来检测它,而无需在每个时间步通过成对的多边形交点。