728x90

Brute-force : O(n^2),

Optimal: O(n log(n))

참고: people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf

참고: arxiv.org/pdf/1911.01973.pdf

//  points should be sorted in order of increasing x-component.
//
#define DIST2(p, q) ((p).x-(q).x)*((p).x-(q).x) + ((p).y-(q).y)*((p).y-(q).y)
// 수정: index range -> [idx1, idx2]; ClosestPair(points, 0, points.size()-1, closest);
int ClosestPair(CPoint points[], int idx1, int idx2, int closest[2]) {
    if (idx2 - idx1 >= 3) {
        int lpair[2], rpair[2], min_dist2;
        int idx12 = idx1 + (idx2 - idx1) / 2;                    // half index;
        int dist1 = ClosestPair(points, idx1, idx12, lpair);     // left side;
        int dist2 = ClosestPair(points, idx12 + 1, idx2, rpair); // right side;
        if (dist1 < dist2) {
            closest[0] = lpair[0]; closest[1] = lpair[1];
            min_dist2 = dist1;
        } else {
            closest[0] = rpair[0]; closest[1] = rpair[1];
            min_dist2 = dist2;
        }
        // find points which lies near center strip(2d-strip);
        // Note our distance is the squar of actual distance;
        int width = int(sqrt(double(min_dist2))+0.5);
        int ll = idx1;
        while (points[ll].x < (points[idx12].x - width - 1)) ll++;
        int rr = idx2;
        while (points[rr].x > (points[idx12 + 1].x + width + 1)) rr--;
        for (int i = ll; i < rr; i++) {
            for (int j = i + 1; j <= rr; j++) {
                int dist2 = DIST2(points[i], points[j]);
                if (min_dist2 > dist2) {
                    min_dist2 = dist2;
                    closest[0] = i; closest[1] = j;
                }
            }
        }
        return min_dist2;
    } 
    else if (idx2 == idx1 + 2) {
        return ClosestPair3(points, idx1, closest);
    }
    else if (idx2 == idx1 + 1) {
        closest[0] = idx1; closest[1] = idx2;
        return DIST2(points[idx1], points[idx2]);
    }
    else return INT_MAX;
};

'Computational Geometry' 카테고리의 다른 글

Data Fitting with B-Spline Curves  (0) 2021.04.30
Closest Pair of Points  (0) 2021.04.27
DDA Algorithm  (0) 2021.04.25
B-Spline  (0) 2021.04.25
Bezier Curve Smoothing  (0) 2021.04.23
Flatness of Cubic Bezier Curve  (0) 2021.04.23
Posted by helloktk

댓글을 달아 주세요