我们在平面上有一个n个点的数组，问题是找出数组中最近的一对点。这个问题出现在许多应用中。例如，在空中交通管制中，您可能希望监视靠得太近的飞机，因为这可能表明可能发生碰撞。回想一下两点p和q之间的距离公式。 
我们讨论了一个问题 分而治之的解决方案 对于这个问题。前一篇文章中提供的实现的时间复杂度为O（n（Logn）^2）。在本文中，我们将讨论时间复杂度为O（nLogn）的实现。 下面是前一篇文章中讨论的算法的概述。 1) 我们根据x坐标对所有点进行排序。 2) 将所有点分成两半。 3) 递归地在两个子阵列中找到最小距离。 4) 取两个最小距离中的最小值。让最小值为d。 5) 创建一个数组条[]，存储距离两个集合中间线最多d距离的所有点。 6) 在strip[]中找到最小距离。 7) 返回上述步骤6中计算的最小距离d和最小距离。 上述方法的优点是，如果数组strip[]按照y坐标排序，那么我们可以在O（n）时间内找到strip[]中的最小距离。在前一篇文章中讨论的实现中，假设排序步骤需要O（nLogn）时间，则在每个递归调用中显式地对strip[]进行排序，使时间复杂度为O（n（Logn）^2。 在本文中，我们将讨论一个时间复杂度为O（nLogn）的实现。其思想是根据y坐标对所有点进行预排序。让排序后的数组为Py[]。当我们进行递归调用时，我们还需要根据垂直线划分Py[]的点。我们可以通过简单地处理每个点并将其x坐标与中线的x坐标进行比较来实现这一点。 下面是C++实现的O（nLogn）方法。
CPP
// A divide and conquer program in C++ to find the smallest distance from a // given set of points. #include <iostream> #include <float.h> #include <stdlib.h> #include <math.h> using namespace std; // A structure to represent a Point in 2D plane struct Point { int x, y; }; /* Following two functions are needed for library function qsort(). // Needed to sort array of points according to X coordinate int compareX( const void * a, const void * b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->x != p2->x) ? (p1->x - p2->x) : (p1->y - p2->y); } // Needed to sort array of points according to Y coordinate int compareY( const void * a, const void * b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->y != p2->y) ? (p1->y - p2->y) : (p1->x - p2->x); } // A utility function to find the distance between two points float dist(Point p1, Point p2) { return sqrt ( (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y) ); } // A Brute Force method to return the smallest distance between two points // in P[] of size n float bruteForce(Point P[], int n) { float min = FLT_MAX; for ( int i = 0; i < n; ++i) for ( int j = i+1; j < n; ++j) if (dist(P[i], P[j]) < min) min = dist(P[i], P[j]); return min; } // A utility function to find a minimum of two float values float min( float x, float y) { return (x < y)? x : y; } // A utility function to find the distance between the closest points of // strip of a given size. All points in strip[] are sorted according to // y coordinate. They all have an upper bound on minimum distance as d. // Note that this method seems to be a O(n^2) method, but it's a O(n) // method as the inner loop runs at most 6 times float stripClosest(Point strip[], int size, float d) { float min = d; // Initialize the minimum distance as d // Pick all points one by one and try the next points till the difference // between y coordinates is smaller than d. // This is a proven fact that this loop runs at most 6 times for ( int i = 0; i < size; ++i) for ( int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) if (dist(strip[i],strip[j]) < min) min = dist(strip[i], strip[j]); return min; } // A recursive function to find the smallest distance. The array Px contains // all points sorted according to x coordinates and Py contains all points // sorted according to y coordinates float closestUtil(Point Px[], Point Py[], int n) { // If there are 2 or 3 points, then use brute force if (n <= 3) return bruteForce(Px, n); // Find the middle point int mid = n/2; Point midPoint = Px[mid]; // Divide points in y sorted array around the vertical line. // Assumption: All x coordinates are distinct. Point Pyl[mid]; // y sorted points on left of vertical line Point Pyr[n-mid]; // y sorted points on right of vertical line int li = 0, ri = 0; // indexes of left and right subarrays for ( int i = 0; i < n; i++) { if ((Py[i].x < midPoint.x || (Py[i].x == midPoint.x && Py[i].y < midPoint.y)) && li<mid) Pyl[li++] = Py[i]; else Pyr[ri++] = Py[i]; } // Consider the vertical line passing through the middle point // calculate the smallest distance dl on left of middle point and // dr on right side float dl = closestUtil(Px, Pyl, mid); float dr = closestUtil(Px + mid, Pyr, n-mid); // Find the smaller of two distances float d = min(dl, dr); // Build an array strip[] that contains points close (closer than d) // to the line passing through the middle point Point strip[n]; int j = 0; for ( int i = 0; i < n; i++) if ( abs (Py[i].x - midPoint.x) < d) strip[j] = Py[i], j++; // Find the closest points in strip. Return the minimum of d and closest // distance is strip[] return stripClosest(strip, j, d); } // The main function that finds the smallest distance // This method mainly uses closestUtil() float closest(Point P[], int n) { Point Px[n]; Point Py[n]; for ( int i = 0; i < n; i++) { Px[i] = P[i]; Py[i] = P[i]; } qsort (Px, n, sizeof (Point), compareX); qsort (Py, n, sizeof (Point), compareY); // Use recursive function closestUtil() to find the smallest distance return closestUtil(Px, Py, n); } // Driver program to test above functions int main() { Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}; int n = sizeof (P) / sizeof (P[0]); cout << "The smallest distance is " << closest(P, n); return 0; } |
The smallest distance is 1.41421
时间复杂性： 假设上述算法的时间复杂度为T（n）。假设我们使用O（nLogn）排序算法。上述算法将所有点划分为两个集合，并递归调用两个集合。分割后，它在O（n）时间内找到条带。此外，围绕中垂直线分割Py数组需要O（n）时间。最后在O（n）时间内找到条带中最近的点。所以T（n）可以表示为 T（n）=2T（n/2）+O（n）+O（n）+O（n） T（n）=2T（n/2）+O（n） T（n）=T（nLogn） 参考资料： http://www.cs.umd.edu/class/fall2013/cmsc451/Lects/lect10.pdf http://www.youtube.com/watch?v=vS4Zn1a9KUc http://www.youtube.com/watch?v=T3T7T8Ym20M http://en.wikipedia.org/wiki/Closest_pair_of_points_problem 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
