[原创] 使用[染色法]快速判断地图上任意两个分区是否相邻

使用[染色法]快速判断分区相邻

问题

对于地图上任意形状的两个分区(已使用不同颜色标记)，如何快速判断他们是否相邻

建模

对于两个点集A, B,
判断是否存在这样的两个点:

• 点Pa, Pa属于A
• 点Pb, Pb属于B
• Pa到Pb的距离小于阀值k(k>=1, k<=10)

过程

1. 定义A的染色集Sa = new Set<Int>(),
2. 遍历A的所有点, 并加入染色集:

const k = 1; // 相邻阀值
var Sa = new Set<Int>()
for(p in A) {
    for(x in (p.x - k)..(p.x + k)) {
      for(y in (p.y - k) .. (p.y+k)) {
        Sa.put (x << 16 | y)  // 这里假设x, y都小于65536
      }
    }
}

3. 遍历B, 判断是否存在Pb, Pb in Sa:

fn isNeighbour(B, Sa) : bool {
    for(p in B) {
        for(x in (p.x - k)..(p.x + k)) {
          for(y in (p.y - k) .. (p.y+k)) {
            if (Sa.has (x << 16 | y)) {
                // 命中, 相邻
                return true;
            }
          }
      } 
    }

  // 不相邻
  return false;
}

复杂度分析

最坏情况:
两个分区不相邻(任意点距大于k): (2k+1)^2 * (Na + Nb), k为距离阀值, N为点数

最好情况:
两个分区相邻, 且Pb第一个点命中: (2k+1)^2 * min(Na, Nb), k为距离阀值, N为点数