在二维空间中，最短路径和点的排序

Question

假设我有一个在二维空间中的对象，以及一组需要该对象访问的点。可以随时添加点，但不能删除。

我想要的是能够在O(lg(n))时间内确定距离我的对象最近的下一个点，然后去到它，然后确定下一个最近的点，以此类推。

简单的优先队列对此无效，因为对象的位置正在改变，因此每次移动时都需要重新排列队列。我想象将点按某种方式排序为BST，但我不确定如何按（x，y）进行排序，或者是否可能。

这感觉就像我可能正在尝试解决旅行商问题，如果是这样，我很抱歉哈哈。

- Ryan Haining

Answer 1

一种选择是使用空间分区树，例如四叉树或k-d树来存储所有点的位置。这些数据结构高效地（通常在次线性时间内）支持查询“离点p最近的点是什么？”您可以按照以下步骤进行操作：

1. 为空间中的点构建空间分区树。
2. 使用树找到最接近起始点的点p。
3. 重复以下步骤：
   1. 移动到点p。
   2. 从树中删除p。
   3. 将p设置为当前位置最接近的点。

希望这能帮助您！

- templatetypedef

---

@Phpdna 他想要一个移动的物体。他可以通过支持高效计算放置对象的任何点发生的情况来实现这一点。 - btilly

是的。但是当它改变时，在树中插入它是移动和昂贵的。此外，有任何东西都没有。黑白通常是一样的。 - Micromega

@Phphdna 我不确定这是否是你的意思，但我只需要计算到达目的地后下一个要去的地方，而不是在移动时改变方向。 - Ryan Haining

@Phpdna，我希望你是故意在搞笑，否则你的评论就没有任何意义。向四叉树中插入/删除数据很便宜，查找邻域内所有点也很便宜。而且在这种情况下，移动的点甚至不需要在树中。你只需要那些尚未访问过的点。 - btilly