在集合中查找最近的 Vector2(x,y)

Question

我有一个 bool[,]，给定一个输入 Vector2(x,y)，我想找到最近的 true 的索引。我可以天真地遍历二维数组并检查到输入的距离，但这会给我一个 O(LxW) 的运行时间。我想知道是否有比 O(LxW) 更快的方法找到最近的。我愿意在 Hashset<Vector2> 或排序的 List<Vector2> 或任何其他类型的集合中添加所有真实坐标，如果它能更快地查找的话。

这里性能比代码可读性更重要。

示例：

T, T, F
T, F, T
T, T, T

GetNearestTrue(new Vector2(2, 3)) // returns (1, 2)
GetNearestTrue(new Vector2(1, 1)) // returns (0, 1) or (1, 0) or (1, 2) or (2, 1), since they're equidistant it doesn't matter

Answer 1

是否有比 O(LxW) 更快的查找最近点的方法？

如果 L 和 W 分别是二维数组的长度和宽度，那么答案是否定的。

简单证明：想象一下，您必须证明网格中没有最近的真实值。 IE。网格仅包含错误。在您访问了网格的每个单元格之前，您永远不能说存在 none。这意味着运行时间将始终至少为 O(LxW)。

为了证明节点 (x, y) 最接近 (a, b) 你必须证明在 (a,b) 周围的半径为 |Max(x-a, y-b)| 的圆中只包含 false 并且在最坏的情况下，半径将是 Max(L, W)，这使得最坏的情况下运行时间为 O(LxW)

虽然您可以通过从中心进行 BFS 来进行一些优化，但这会减少运行一些因素的时间，但最坏的情况保持不变。

Answer 2

如果您有大量 'false'，那么还有一种更快的方法。您可以从 O(L*W)=O(nFalse + nTrue) 优化到 about O(log nTrue).

您可以使用 multidim-index（四叉树、kd-tree、R-Plus-Tree、PH-Tree）并为每个 'true' 在 (x,y) 处插入一个点到 multi-坐标为 (x,y) 的暗淡索引。现在，要为点 'p' 找到最近的 'true'，您只需在索引中对点 'p' 进行最近邻搜索。比如this表示有一个算法"that claims guaranteed O(log n) complexity."

虽然 kd-tree 可能是最简单的（参见 here 了解许多索引的 Java 实现），PH-Tree 可能有意义，因为它可以直接使用整数作为坐标，而不是比浮点值。但是，我不知道 PH-Tree 的 C# 版本。

在集合中查找最近的 Vector2(x,y)

Find nearest Vector2(x,y) in collection

c#

search

nearest-neighbor