在 2D 中查找最近的对象 - 它可以在 O(n) 以下进行优化吗？
Find nearest object in 2D - can it be optimised below O(n)?
想象一个有n个物体的二维平面。选择平面上的任意点并找出距离最近的物体。
显而易见的解决方案是计算所选点到所有n个物体的距离并选择最短的距离但是没有更优的算法吗？像二叉树之类的东西，一些巧妙地将平面划分为区域等的方法？
编辑： 让我们假设那些点 "do not move" 并且我们将不得不多次找到最近的对象。换句话说，如果我们愿意，我们可以在一开始就将对象分类为某种结构。
谢谢
可能有数百种解决方案比 O(n) 更好。
一棵 k-d 树或四叉树是最多的 well-known。也有仅涉及排序列表的解决方案，这些解决方案往往更适用于移动 object，但通常也更简单。
四叉树
四叉树是一种树结构，其中每个节点都是一个有四个 children 的矩形。四个children是原来的细分。假设你只插入点，在每个节点测试将是：
- 这个节点有children吗？如果是这样的话：
- 点在哪个child内？
- 递归到 child。
- 如果不是：
- 在此节点添加点。
- 查看此节点现在存储了多少个点。
- 如果现在太多，则创建 children 并将每个点推送到适当的 child.
可以将节点分成equally-sized children 或尝试近似遵循点的分布，例如取平均x和平均y作为分割位置
如果您要存储整个 object，则样式会有所不同，具体取决于您是否插入与 object 重叠的每个节点以及 children 是否因此相互重叠一点边缘。如果您知道最大 object 大小，那么这通常是可行的方法，因为您在运行时测试的 object 将只需要考虑一个叶节点。否则你将不得不考虑几个节点的联合。
否则搜索意味着找到你的点所在的叶节点，从那里获得最小距离，然后沿着树往回走，直到你的测试点距离相关 child 边界比当前最小距离更远已知。到那时你就知道你肯定找不到更近的东西了。
k-d树
一棵k-d树也是树结构但严格来说是二叉树。每个节点都是一个 1d 跨度和一个分界点。 Child 节点跨度在不同的轴上。
例如一个节点可能知道它包含 [0, 10) 中 x 的所有点。它将记录它的 children 只知道 [0, 7) 中的 x 和 [7, 10) 中的 x 的点。然而，它的两个 children 节点将根据 y 来表达。所以例如左边可能知道它覆盖了 [0, 6) 中的 y，它的 children 覆盖了 [0, 1) 和 [2, 6).
中的 y
插入测试的伪代码因此与上面为四叉树给出的伪代码相同，尽管具体测试不同。在决定拆分位置时，取 x 的平均值或 y 的平均值更为常见。关于允许 children 重叠的相同评论适用。
搜索遵循与四叉树相同的 tree-walking 逻辑。
排序列表
为了论证起见，假设您单独对 x 进行排序。有一个包含所有 object 的列表，按它们的最低 x 范围排序。你知道每个 object.
的宽度
要找出哪个 object 最接近一个点，首先找到 object 将插入列表的索引。它已排序，因此您可以在 O(log n) 时间内完成。
计算出从您的点到该插入索引处的 object 的距离。那就是 object 可以达到的最远上限。该上限决定了您可能需要在列表中向左或向右搜索多远。同时向左和向右移动，更新上限，直到您的迭代器现在在 x 轴上比上限更远。那么上限就是正确答案。
在游戏编程领域，"Space Partitioning" 的思想通常用于优化碰撞检测等代码。
一个非常简单的解释如下。您从 2D space:
中的对象开始
然后你使用算法将 space 划分为 "buckets" 个靠得很近的对象：
现在，当您想要计算 "which object is closest to a point" 时，您只需要测试相邻桶中的那些：
如果您谨慎选择分区算法，这可能会产生重要的影响 speed-up，因为您测试的接近度要少得多。
有很多算法可用于划分 space 对象所在的区域，它们可以基于数组或各种类型的树。我在输入时看到 列出了一些常见的。
互联网上有很多 write-ups 这个概念，因为它是一种相当常用的模式。这是我以前读过的：
想象一个有n个物体的二维平面。选择平面上的任意点并找出距离最近的物体。
显而易见的解决方案是计算所选点到所有n个物体的距离并选择最短的距离但是没有更优的算法吗？像二叉树之类的东西，一些巧妙地将平面划分为区域等的方法？
编辑： 让我们假设那些点 "do not move" 并且我们将不得不多次找到最近的对象。换句话说，如果我们愿意，我们可以在一开始就将对象分类为某种结构。
谢谢
可能有数百种解决方案比 O(n) 更好。
一棵 k-d 树或四叉树是最多的 well-known。也有仅涉及排序列表的解决方案，这些解决方案往往更适用于移动 object，但通常也更简单。
四叉树
四叉树是一种树结构，其中每个节点都是一个有四个 children 的矩形。四个children是原来的细分。假设你只插入点，在每个节点测试将是：
- 这个节点有children吗？如果是这样的话：
- 点在哪个child内？
- 递归到 child。
- 如果不是：
- 在此节点添加点。
- 查看此节点现在存储了多少个点。
- 如果现在太多，则创建 children 并将每个点推送到适当的 child.
可以将节点分成equally-sized children 或尝试近似遵循点的分布，例如取平均x和平均y作为分割位置
如果您要存储整个 object，则样式会有所不同，具体取决于您是否插入与 object 重叠的每个节点以及 children 是否因此相互重叠一点边缘。如果您知道最大 object 大小，那么这通常是可行的方法，因为您在运行时测试的 object 将只需要考虑一个叶节点。否则你将不得不考虑几个节点的联合。
否则搜索意味着找到你的点所在的叶节点，从那里获得最小距离，然后沿着树往回走，直到你的测试点距离相关 child 边界比当前最小距离更远已知。到那时你就知道你肯定找不到更近的东西了。
k-d树
一棵k-d树也是树结构但严格来说是二叉树。每个节点都是一个 1d 跨度和一个分界点。 Child 节点跨度在不同的轴上。
例如一个节点可能知道它包含 [0, 10) 中 x 的所有点。它将记录它的 children 只知道 [0, 7) 中的 x 和 [7, 10) 中的 x 的点。然而，它的两个 children 节点将根据 y 来表达。所以例如左边可能知道它覆盖了 [0, 6) 中的 y，它的 children 覆盖了 [0, 1) 和 [2, 6).
中的 y插入测试的伪代码因此与上面为四叉树给出的伪代码相同，尽管具体测试不同。在决定拆分位置时，取 x 的平均值或 y 的平均值更为常见。关于允许 children 重叠的相同评论适用。
搜索遵循与四叉树相同的 tree-walking 逻辑。
排序列表
为了论证起见，假设您单独对 x 进行排序。有一个包含所有 object 的列表，按它们的最低 x 范围排序。你知道每个 object.
的宽度要找出哪个 object 最接近一个点，首先找到 object 将插入列表的索引。它已排序，因此您可以在 O(log n) 时间内完成。
计算出从您的点到该插入索引处的 object 的距离。那就是 object 可以达到的最远上限。该上限决定了您可能需要在列表中向左或向右搜索多远。同时向左和向右移动，更新上限，直到您的迭代器现在在 x 轴上比上限更远。那么上限就是正确答案。
在游戏编程领域，"Space Partitioning" 的思想通常用于优化碰撞检测等代码。
一个非常简单的解释如下。您从 2D space:
中的对象开始然后你使用算法将 space 划分为 "buckets" 个靠得很近的对象：
现在，当您想要计算 "which object is closest to a point" 时，您只需要测试相邻桶中的那些：
如果您谨慎选择分区算法，这可能会产生重要的影响 speed-up，因为您测试的接近度要少得多。
有很多算法可用于划分 space 对象所在的区域，它们可以基于数组或各种类型的树。我在输入时看到
互联网上有很多 write-ups 这个概念，因为它是一种相当常用的模式。这是我以前读过的：