寻找可通过短中间跳数到达的 2D 点

Question

我有一个列表 allNodes，其中包含大约 60,000 个对应于二维点的节点。我正在构建一个邻接列表

for(i in allNodes)
  for(j in allNodes)
    if(distance(i, j) <= 10) addEdge between i and j

然后从一组 sourceNodes 中执行深度优先搜索以找到从 sourceNodes 可到达的节点集。我怎样才能使它比二次方更快？我正在使用 C++。

Answer 1

简单的方法是将平面划分为 d-by-d，其中 d > 10 个箱子，并将每个点放入由 floor(x/d)、floor(y/d) 索引的箱子中.然后，不是遍历所有点对，

for bin1 in bins:
   for i in bin1:
      for bin2 in bins neighboring bin in nine directions (including bin):
         for j in bin2:
            if(distance(i, j) <= 10) addEdge between i and j

如果点分布得很好，这将使事情变得更快，但最坏的情况仍然是二次的。

对于有保证的 O(n log n) 时间算法，计算 Delaunay 三角剖分并丢弃长于 10 的边。这可能会删除距离小于或等于 10 的节点之间的一些直接连接，但它们仍将间接连接。

Answer 2

如果您希望点均匀分布，这不是您指定的属性数据，则 David Eisenstat 的回答建议的分箱方法有效。此外，如前所述，Delaunay triangulation 仍然需要在导出图上进行局部搜索，以确保找到指定距离内的所有节点。

获得保证性能的一种方法是使用 kd-tree。您可以在 O(2n log n) 时间内构建一个（如果您不太关心保证并使用随机化，则可以更快）并使用它来执行总时间的范围搜索O(2n√n).

我不清楚 Delaunay 三角剖分或 kd-tree 在实践中是否会更快，但在我看来，找到并使用合适的 kd-tree 库将是一个快速而简单的解决方案, 如果你担心开发时间。

寻找可通过短中间跳数到达的 2D 点

Finding 2D points reachable with short intermediate hops

algorithm

graph

depth-first-search

path-finding

adjacency-list