问四叉树能准确地确定离点最近的物体吗？

EN

试试“松散的四叉树”。它没有每个节点的固定卷。因此，它可以调整每个节点的边界体积，以适应添加的项目。

如果您不喜欢四叉树的遍历性能，如果您的对象只是点，自适应网格可以执行快速或非常接近O(N)。但是记忆方面，松散的四叉树会更好。

有一个Hjaltason和Samet在他们的论文“空间数据库中的远程浏览”中描述了算法。它可以很容易地应用于四叉树，我有一个实现这里。

基本上，您维护一个已排序的对象列表，该列表按照距离排序(首先是最近的)，对象要么是树中的点(调用坐标)，要么是树中的节点(距离最近的角的距离，如果它们与搜索点重叠，则为distance=0 )。开始添加与搜索点重叠的所有节点，并在这些点中添加所有点和子节点。然后，你只需从列表的顶部返回点，直到你有尽可能多的最接近的点。如果某个节点位于列表的顶部，则将该节点的点数/子节点添加到列表中，并再次检查列表的顶部。重复一遍。

是的，你可以在四叉树中找到最接近的坐标，即使它不是直接在叶子里面。为了做到这一点，您可以执行以下搜索算法：

1. 搜索四叉树内最近的位置。
2. 把它与你的初始位置保持距离
3. 从根节点搜索此边界框中的所有节点。
4. 从这个边界框中的所有节点返回最近的节点。

但是，这是一个非常基本的算法，没有性能优化。除其他外：

如果在2中计算的距离小于到树节点边框的距离，则不需要执行3或4。(或者您可以选择一个不是根节点的节点)

此外，3和4可以简化为一个单一的算法，只在树内搜索，距离最近的节点作为边界框。

您还可以通过首先搜索与您位置最近的节点来对搜索边界框中的节点的方式进行排序。

然而，我还没有进行复杂性计算，但是您应该期望在一个节点上出现一个最坏的情况，如果不是比正常情况更糟糕的话，但是通常您应该在没有错误的情况下得到相当好的速度。