【测试】经典分治算法求解最近点对
测试1采集点 100000 个
最近点对距离 = 0.312
分治算法求解最近点对用时: 31 毫秒
测试2
采集点 157011 个
最近点对距离 = 0.028
分治算法求解最近点对用时: 46 毫秒
测试3
采集点 1436160 个
最近点对距离 = 0.003
分治算法求解最近点对用时: 1828 毫秒
// 归并排序的归并操作（对y排序）
static void Merge(AcGePoint3dArray &pts, int nLeft, int nRight)
{
int mid = (nLeft + nRight) / 2;
int i = nLeft;
int j = mid + 1;
AcGePoint3dArray resPts;
while (i <= mid && j <= nRight)
{
if (pts.at(i).y < pts.at(j).y)
resPts.append(pts.at(i++));
else
resPts.append(pts.at(j++));
}
while (i <= mid)
resPts.append(pts.at(i++));
while (j <= nRight)
resPts.append(pts.at(j++));
for (int i = nLeft; i < resPts.length(); i++)
pts.at(i) = resPts.at(i);
}// 计算点对距离
static double distance(const AcGePoint3d& p1, const AcGePoint3d& p2)
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}// 分治法找最近点对
static double mergeMethod(AcGePoint3dArray &pts, int nLeft, int nRight, AcGePoint3d &p1, AcGePoint3d &p2)
{
if (nRight - nLeft <= 1)
return INT_MAX;
else if (nRight - nLeft == 2)
{
Merge(pts, nLeft, nRight);//确保每个小单元的两个点对的y轴是有序的，才能保证后续对y归并排序的复杂度
p1 = pts.at(nLeft);
p2 = pts.at(nRight);
return distance(p1, p2);
}
else
{
AcGePoint3d l1, l2, r1, r2;
int mid = (nLeft + nRight) / 2;
double mindis = INT_MAX;
double middleX = pts.at(mid).x; //中线
double mindis1 = mergeMethod(pts, nLeft, mid, l1, l2); // 左侧最近点对
double mindis2 = mergeMethod(pts, mid + 1, nRight, r1, r2); // 右侧最近点对
if (mindis1 < mindis2)
{
mindis = mindis1;
p1 = l1;
p2 = l2;
}
else
{
mindis = mindis2;
p1 = r1;
p2 = r2;
}
AcGePoint3dArray temp;
Merge(pts, nLeft, nRight); // 按照y排序
for (int i = nLeft; i <= nRight; i++) //找到在中间区域的点
{
if (fabs(pts.at(i).x - middleX) <= mindis)
{
temp.append(pts.at(i));
}
}
double tempDis = INT_MAX;
// 遍历中间数组，每个点最多遍历其他点6次，记录最短距离和点对
for (int i = 0; i < temp.length(); i++)
{
for (int j = i + 1; j < i + 1 + 6 && j < temp.length(); j++)
{
tempDis = distance(temp, temp);
if (tempDis < mindis)
{
mindis = tempDis;
p1 = temp;
p2 = temp;
}
}
}
return mindis;
}
}
距离那个地方使用距离平方也行吧
页:
[1]