1、问题:
求平面中距离最近的两个点
2、解析:
可以通过枚举两两顶点来得到结果,但是时间复杂度来到了 O ( n 2 ) O(n^2) O(n2),显然是很慢的,所以我们采用分治的策略来分析这个问题。
这里的分治算法的主要思路是将平面上的n个点分为两个子集S1,S2。每个子集中有n/2个点,然后递归的在每个子集中求解最近点对。
算法步骤:
- 把所有的点按照横坐标排序
- 将所有点分成左右两部分
- 递归分别算出左右部分的最近点对,设为d1和d2
- 求出一个点在左部分,一个点在右部分的最近点对,设为d3
- 结果就是min(d1, d2, d3)
3、设计(核心伪代码):
void Closest_Pair(int left, int right, int flag) { //最近点对距离 先对x排序,flag表示禁用的点
if(left == right) return ; //只剩1个点
if(left + 1 == right){
if(P[left].id != flag && P[right].id != flag){
if(dis > Dist(P[left], P[right])){
dis = Dist(P[left], P[right]);
if(flag == -1){
pos[0] = P[left].id;
pos[1] = P[right].id;
}
}
}
return ;
}
int mid = (left + right) / 2; //分治
Closest_Pair(left, mid, flag); // 求s1(集合)中的最近点对
Closest_Pair(mid + 1, right, flag); //求s2中的最近点对
int k = 0;
for(int i = left; i <= right; i++){ //在s1和s2中间附近找可能的最近点对
if(abs(P[mid].x - P[i].x) <= dis && P[i].id != flag) //按x坐标来找
tmp_P[k++] = P[i];
}
sort(tmp_P, tmp_P + k, cmpy); //对y排序 用于剪枝
for(int i = 0; i < k; i++){
for(int j = i + 1; j < k && tmp_P[j].y - tmp_P[i].y < dis; j++){
if(dis > Dist(tmp_P[i], tmp_P[j])){
if(flag == -1){
pos[0] = tmp_P[i].id;
pos[1] = tmp_P[j].id;
}
dis = Dist(tmp_P[i], tmp_P[j]);
}
}
}
}
4、分析:
时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
5、源码:
平面最近点对源码