使用[染色法]快速判断分区相邻
问题
对于地图上任意形状的两个分区(已使用不同颜色标记)，如何快速判断他们是否相邻
建模
对于两个点集A, B,
判断是否存在这样的两个点:
- 点Pa, Pa属于A
- 点Pb, Pb属于B
- Pa到Pb的距离小于阀值k(k>=1, k<=10)
过程
- 定义A的染色集Sa = new Set<Int>(),
- 遍历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
}
}
}
- 遍历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为点数
