algorithm - 对从小到大的物体进行空间分区/碰撞检测的最佳算法？

Question

我环顾四周，发现了十亿个问题、文章、研究、论文等，但我无法真正弄清楚或找到这个问题的答案。

基本上，我只是想知道从 1 像素到屏幕本身大小的对象之间的空间分区/碰撞检测的最佳算法是什么。目前，我倾向于松散的四叉树。

Answer 1

首先，看看这里。

这取决于您的要求。四叉树非常适合多达 100K 条目左右的中小型数据集。如果这符合您的要求，则无需进一步阅读。

然而，正常的四叉树往往难以处理非常大或强聚类（某些区域中的点密度高）的数据集。它们也不是那么直接实施，因为对于较大的树，您可能会遇到精度问题（如果您深入一棵树并且您的象限开始重叠或它们之间有间隙，则将一个数字除以 2 30 倍）。否则，它们相对容易实现。

我发现我的PH-Tree非常有用，它有点类似于四叉树，但没有精度问题，而且深度有限。根据我的经验，它非常快，特别是如果您使用小结果集进行窗口查询（这基本上就是您在碰撞检测中所做的）。不幸的是，实现起来并不容易。上面的链接引用了我自己的 Java 实现，但该文档还包含指向 C++ 版本的链接。

您也可以在这里尝试“qthypercube2” ，它是一个四叉树，带有一些 PH-Tree 的导航技术。当前的 1.6 版本对于极端数据集存在一些精度问题，但您会发现它非常快，并且精度问题的解决方案已经在酝酿中。