用向量分而治之的最近点对

Question

所以我决定实现一个基于向量的算法来解决最近点对问题（2D）。它似乎适用于像

这样简单的情况

1.2 4.5

2.4 1.2

3.3 1.1

4.4 4.4

7.7 1.1

1.1 2.1

8.6 1.9

3.3 9.0

并且输出是正确的（在本例中为 0.90554），但是有人检查了我的代码并说某处存在无效的内存引用。我一直在为这段代码苦苦挣扎，但我放弃了，没有办法找到问题所在（因为我尝试的案例有效！）。如果有人能启发我，我将不胜感激！提前致谢！

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

struct Point { double x, y; };
bool compareX (Point p, Point q) { return p.x < q.x; }
bool compareY (Point p, Point q) { return p.y < q.y; }
float dist(Point p1, Point p2) {
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

double min_dist (vector<Point> pointsX, vector<Point> pointsY, int n) {
     // BASE CASE.
    if (n <= 3) {
        double min = __DBL_MAX__;
        for (int i = 0; i < n; ++i)
            for (int j = i +1 ; j < n; ++j)
                if (dist(pointsX[i], pointsX[j]) < min)
                    min = dist(pointsX[i], pointsX[j]);
        return min;
    }

    // Step 1: Find the middle point.
    int mid = n/2;
    Point mid_point = pointsX[mid];

    // Step 2: Divide the set in two equal-sized parts (left and right).
    vector<Point> pointsY_left;
    vector<Point> pointsY_right;
    vector<Point> pointsX_left;
    vector<Point> pointsX_right;

    for (int i = 0; i < n; ++i) {
        if (i < mid  and pointsY[i].x <= mid_point.x)  pointsY_left.push_back(pointsY[i]);
        else pointsY_right.push_back(pointsY[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (i < mid and pointsX[i].x <= mid_point.x) pointsX_left.push_back(pointsX[i]);
        else pointsX_right.push_back(pointsX[i]);
    }

    // Step 3: Calculate the smaller distance at left and right parts recursively.
    double d_left = min_dist(pointsX_left, pointsY_left, mid);
    double d_right = min_dist(pointsX_right , pointsY_right, n - mid);

    // Let d be the minimal of the 2 distances.
    double d = min (d_left, d_right);

   // Eliminate points that are farther than d <=> Create a strip that contains
   // points closer than d.
   vector<Point> strip;
   for (int i = 0; i < n; ++i) if (abs(pointsY[i].x - mid_point.x) < d) strip.push_back(pointsY[i]);

   // Scan the points from the strip and compute the dstances of each point to its 7 neighbours.
   // Pick all points one by one and try the next points until the difference
   // between y coordinates is smaller than d.
   for (int i = 0; i < int(strip.size()); ++i)
        for (int j = i + 1; j < int(strip.size()) and (strip[j].y - strip[i].y) < d; ++j)
             if (dist (strip[i], strip[j]) < d)
             d = dist(strip[i], strip[j]);

     return d;
}

double closest(const vector<Point>& points) {
    // Initial step: sort points accroding to their coordinates.
    vector<Point> pointsX, pointsY;
    pointsX = pointsY = points;
    sort(pointsX.begin(), pointsX.end(), compareX);
    sort(pointsY.begin(), pointsY.end(), compareY);

    return min_dist (pointsX, pointsY, int(points.size()));
}

int main() {
    cout.setf(ios::fixed);
    cout.precision(5);

    vector<Point> points;
    double x, y;
    while (cin >> x >> y) {
        Point p = {x, y};
        points.push_back(p);
    }

    cout << closest (points) << endl;
}

Answer 1

看来问题出在 Step 2。您有两个不同的条件 i < mid and pointsY[i].x <= mid_point.x 和 i < mid and pointsX[i].x <= mid_point.x，但是 在下面的代码中您假设这些条件相等 。也许你应该用 i < mid.

替换这些条件

// Step 1: Find the middle point.
int mid = n/2;
Point mid_point = pointsX[mid];

// Step 2: Divide the set in two equal-sized parts (left and right).
vector<Point> pointsY_left;
vector<Point> pointsY_right;
vector<Point> pointsX_left;
vector<Point> pointsX_right;

for (int i = 0; i < n; ++i) {
    if (i < mid  and pointsY[i].x <= mid_point.x)  pointsY_left.push_back(pointsY[i]);
    else pointsY_right.push_back(pointsY[i]);
}
for (int i = 0; i < n; ++i) {
    if (i < mid and pointsX[i].x <= mid_point.x) pointsX_left.push_back(pointsX[i]);
    else pointsX_right.push_back(pointsX[i]);
}

P.S。您可以简单地使用向量的构造函数：

vector<Point> pointsY_left( pointsY.cbegin(), pointsY.cbegin() + mid );
vector<Point> pointsY_right( pointsY.cbegin() + mid, pointsY.cend() );
vector<Point> pointsX_left( pointsX.cbegin(), pointsX.cbegin() + mid );
vector<Point> pointsX_right( pointsX.cbegin() + mid, pointsX.cend() );

用向量分而治之的最近点对

Closest pair of points Divide&Conquer with vectors

c++

point

vector

divide-and-conquer

closest-points