algorithm - 二维空间中的最短路径和排序点

Question

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

我想要的是能够确定下一个最接近我的对象在 O(lg(n)) 时间内的位置，然后去它，然后确定下一个最近的点，等等。

简单的优先级队列对此不起作用，因为对象正在改变位置，因此每次移动时都需要重新排列队列。我在想象以某种方式将这些点排序为 BST，但我不确定如何对 (x, y) 进行排序，或者是否有可能。

这感觉就像我可能在不知不觉中试图解决旅行推销员一样，如果是这样，我道歉哈哈。

Answer 1

一种选择是使用像四叉树或 kd 树这样的空间划分树来存储空间中的所有点。这些数据结构有效地（通常在亚线性时间内）支持“离点 p 最近的点是什么？”形式的查询。然后，您可以执行以下操作：

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

希望这可以帮助！