algorithm - 检测不规则形状运动物体碰撞的数据结构和算法

Question

我遇到了这个面试题

Many irregularly shaped objects are moving in random directions. Provide a data structure and algorithm to detect collisions. Remember that the number of objects is in the millions.

我假设每个对象都有一个 x 和 y 坐标。其他假设是最受欢迎的。我想也应该使用某种树，但我对算法一无所知。

有什么建议吗？

Answer 1

我会看看 Plane Sweep Algorithm或 Bently-Ottmann Algorithm .它使用平面扫描在 O(n log(n)) 时间(和 O(n) 空间)内确定欧几里得平面上的线的交点。