Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 算法 » 

最近点对问题

二维平面上有n个点,怎么寻找距离最近的两个?
本文将实现一种O(nlogn)时间复杂度的分治算法,具体的思想方法参考了编程之美中寻找最近点对一章。

算法思路

最直观的思路是暴力枚举,枚举所有的两个点,计算距离并找出最小的。这种算法的时间复杂度为O(n^2),不够优化。

为了开拓思路,先考虑一维的简单情况:直线上的n个点,找出距离最近的两个。

最直观的方法当然是先排序,然后比较所有相邻的两个点的距离并找出最小的一对,但是这个排序思想比较难推广到二维的情况。

另外还可以使用递归思想。把n个点按照某条分界线分成两半S1和S2,则距离最近的两个点要么都在S1中,要么都在S2中,要么一个在S1一个在S2中。由于S1和S2是两个规模较小的子问题,可以递归求解。那么就剩下一个在S1一个在S2的情况,此时那两个点必定都非常靠近分界线,我们可以考虑分界线左右两边一定范围内的点,然后从中找到距离最近的一对。于是最终可以得到整体上距离最近的点对。这个思路可以扩展到二维情况。

把二维平面上的点根据某条跟x轴垂直的线分成左右两部分S1和S2,每部分可以分别递归求解得到最近点对及对应的距离,剩下的问题是考虑两个点一个在S1一个在S2的情况。同样地,我们考虑分界线左右一定范围内的点,但是这个范围是多少呢?我们可以从左右两个子问题中得到两个最短距离,令d为这两个距离的较小的一个,则我们只需考虑分界线左右至多距离为d的范围内的点即可。因为如果范围再大的话,其中S1和S2中的点的距离肯定大于d,即不可能是最近的点对,我们不需要考虑这些点。

得到分界线左右范围d内的所有点后,由于这里点的数目比总体点的数目应该少了不少,于是可以考虑直接枚举所有可能的组合,然后从中找到最小的。

但是在某些情况下,这个范围内的点的数目可能还是比较多(比如总体点的分布大体跟x轴垂直而且比较长),这时我们还有一个可以用的优化。
如下图所示,中间的竖线是分隔点集的分界线,左右的竖线是与分界线距离为d的边界线,显然在这个大小为d x 2d的矩形框内至多有8个点,否则每个小正方形内的点的最短距离肯定小于d,与最短距离为d相矛盾。于是,对于范围内的每个点,至多只需要枚举与它Y坐标相邻的7个点之间的距离即可。另外,矩形框内的点不一定总是比较密集,这里可以通过一个点跟另一个点的Y坐标的距离来进行判断,具体参考代码。

|       |       |
| - d - | - d - |
|       |       |
d       d       d
|       |       |
| - d - | - d - |
|       |       |

算法实现

以下是最近点对的实现过程,程序开始时输入顶点个数及每个点坐标,得到的结果即为距离最近的两个点及其对应的距离。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int mxsz = 100000 + 10; //最大点数
const double oo = 1e20;       //无穷大距离
struct Point 
{
	double x, y; 
	Point(double a = 0, double b = 0) : x(a), y(b) {}
} v[mxsz], tem[mxsz];     //点集, 中间点集

bool cmpByX (const Point &p1, const Point &p2) { return p1.x < p2.x; }
bool cmpByY (const Point &p1, const Point &p2) { return p1.y < p2.y; }

//计算欧几里得距离
inline double calDis(const Point &p1, const Point &p2)
{
	return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

//寻找下标在[st, ed]之间的最近点对
double closestPair(int st, int ed, int &p1, int &p2)
{
	double dis = oo, temdis;
	if (st >= ed) return dis;

	int mid = st + ((ed - st) >> 1), t1, t2;
	if ((temdis = closestPair(st, mid, t1, t2)) < dis)  //左边
		dis = temdis, p1 = t2, p2 = t2;
	if ((temdis = closestPair(mid+1, ed, t1, t2)) < dis)//右边
		dis = temdis, p1 = t1, p2 = t2;

	//寻找距离中间x坐标小于dis的点,并按Y坐标排序
	int len = 0;
	for (int i = st; i <= ed; i++)
		if (fabs(v[i].x - v[mid].x) < dis)
			tem[len++] = v[i];
	sort(tem, tem + len, cmpByY);

	//考虑每个点附近至多8个点,由距离控制
	for (int i = 0; i < len; i++)
		for (int j = i + 1; j < len && tem[j].y - tem[i].y <= dis; j++)
			if ((temdis = calDis(tem[i], tem[j])) < dis)
				dis = temdis, p1 = i, p2 = j;
	return dis;
}

int main()
{
	//输入n个点,并按X坐标排序
	int n; scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%lf%lf", &v[i].x, &v[i].y);
	sort(v, v + n, cmpByX);	

	int p1, p2;
	double dis = closestPair(0, n - 1, p1, p2);
	printf("Cloest Pair:(%lf,%lf)-(%lf,%lf) %.2lf\n", v[p1].x, v[p1].y, v[p2].x, v[p2].y, dis/2);
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论