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

Question

我遇到了一个面试问题

许多不规则形状的物体正向随机方向移动。提供一种用于检测冲突的数据结构和算法。记住，对象的数量是以百万计的。

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

有什么建议吗？

Answer 1

我想看看平面扫描算法或本特利-奥特曼算法。它使用平面扫描在O(n log(n))时间(和O(n)空间)确定欧几里得平面上直线的交点。

Answer 2

很可能你想要的是用空间填充曲线细分平面，比如z曲线或希尔伯特曲线，从而将二维问题的复杂性降低为一维问题。找四叉树。

链接：order.html

Answer 3

这个问题有很多解决办法。首先:使用包围框或圆圈(3D中的球)。如果边界框不相交，则不需要进一步的测试。第二:细分空间。您不必针对所有其他对象(即O(n^2))测试每个对象。四叉树的平均复杂度为O(n)。