大量设备节点的距离计算

大量设备/节点的距离计算

（为简化说明，我省略了有关每个设备仅在逻辑上连接到M〜= 10个其他设备的详细信息。）

在空间上划分设备位置。如果您只对间隔小于100米的设备感兴趣，请考虑以下两种算法。

1. 对于i = 1..N，j = 1..N，i！= j，计算设备i和j之间的距离。

2. 对于i = 1..N，计算设备i所在的经度和纬度所在的网格单元，其中网格单元为100米见方。现在，对于所有非空网格单元，仅将该单元中的设备与同一单元或八个相邻单元之一中的设备进行比较。

这种方法的数据结构基本上是从网格单元索引（s，t）到该网格单元中的设备列表的映射M。

第一种方法是幼稚的，将花费Θ（N 2）。假设存在“恒定的最大设备密度”，第二种方法在实践中将更接近Θ（N）。100米半径 是 相当小的。

第二种方法的伪代码如下所示。

M = {}for i = 1..N  (s,t) = compute_grid_cell(i)  if ((s,t) not in M)    M[(s,t)] = []  M[(s,t)].push(i)for i = 1..N  (s,t) = compute_grid_cell(i)  for s' in [s-1, s, s+1]    for t' in [t-1, t, t+1]      if (s',t') in M        for j in M[(s',t')]          if i != j and distance(i, j) < 100 report (i,j) as a pair of devices that are "close"