我环顾四周，发现了十亿个问题、文章、研究、论文等，但我无法真正弄清楚或找到这个问题的答案。
基本上，我只是想知道从 1 像素到屏幕本身大小的对象之间的空间分区/冲突检测的最佳算法是什么。目前，我倾向于松散的四叉树。
首先，看看这里。
这取决于您的要求。四叉树非常适合高达 100K 个条目左右的中小型数据集。如果这符合您的要求，则无需进一步阅读。
但是，普通四叉树往往难以处理非常大或强聚类(某些区域的高点密度(数据集。它们也不是那么容易实现，因为对于较大的树，您可能会遇到精度问题(如果您深入树并且您的象限开始重叠或它们之间有间隙，则将数字除以 2 30 倍(。否则，它们相对容易实现。
我发现我的PH树非常有用，它有点类似于四叉树，但没有精度问题，并且本质上深度有限。根据我的经验，它非常快，特别是如果您使用较小的结果集执行窗口查询(这基本上就是您在冲突检测中所做的(。不幸的是，这并不容易实现。上面的链接引用了我自己的 Java 实现，但该文档还包含指向C++版本的链接。
你也可以在这里尝试"qthypercube2"，它是一个四叉树，带有一些PH树的导航技术。当前的 1.6 版本对于极端数据集有一些精度问题，但您会发现它非常快，并且精度问题的解决方案已经在酝酿中。