[Title]
Given n points on the plane, find a pair of points such that the distance between the point pairs is the smallest among all pairs of n points.
In two dimensions, for two two-dimensional points A = (x1, y1), B = (x2, y2), the Euclidean distance between them is
The problem is easily solved if the two points closest to the pair are both in Q or both in R. However, if these two points are in Q and R respectively, the problem is not so simple. Next let us explore how to specifically solve this problem
[Problem Analysis]
Adopt a divide-and-conquer strategy
For an out-of-order point set P, we first need to sort x and y respectively to obtain Px and P y.
【Divide】
Step 1: Split
For any point set P, the number of points ∣ P ∣ = n, similar to the one-dimensional case, can be divided into Q from the coordinates of the ? n / 2 ? point in Px (denoted as x?) Area and R area.
Step 2: Maintain ordered array
For Q area and R area, we want to maintain 4 ordered arrays: Qx, Qy, Rx, Ry sorted by x or y. Among them, the arrays sorted by x , Qx and Rx , can be separated by index. Qy and R y need to create new arrays, sequentially traverse Py and determine the subordinate areas to construct.
Now the original problem becomes two identical sub-problems. When there are only less than or equal to 3 points in the end, you can directly compare each point pair to get the answer.
【Merge】
Assume that the local nearest point { q1 , q2 } is found in the Q area, and the distance is δ1. Similarly, { r1 , r2 } is found in the R area, and the distance is δ2. And among all point pairs separated by dividing lines, that is, all point pairs { pi , p j } and pi ∈ Q ∧ pj ∈ R, there is a minimum distance δ3.
Now there are three situations for the solution to the original problem:
1. The point pair with the minimum distance is in the set of point pairs separated by the dividing line, that is, δ3 is the smallest, and the corresponding separated point pair should be returned.
2. The point pair found in the Q area has the smallest distance, and { q1 , q2 } should be returned.
3. The point pair found in the R area has the smallest distance, and { r1 , r2 } should be returned.
The key to solving the problem is to find δ3!
We only need to find pairs of points that may be closer than the local nearest in Q and R. If δ = min (δ1, δ2), and the area with width δ on the left and right of x? is recorded as S area, then we only need to check the points in this area.
If all points are concentrated in this area, then it is still inevitable to check all pairs of points.
Suppose we want to check point s, which belongs to region Q. Taking it as the starting point, take out a region with a height of δ in the S region. Then as shown in the figure above, we can divide this δ × 2 δ area into 8 boxes. The farthest distance within a box is the diagonal distance δ/√2< δ, which means that there is at most one point in each box. Then according to the Pigeonhole Principle, for point s, you only need to check the distance between it and 7 points slightly larger than it. After exceeding 7 points, the distance will definitely exceed the height δ of this area, so it does not need to be considered.
specific methods:
Traverse the ordered Py from small to large. If the point is within the area from x? less than δ, then add it to S, so that S is also ordered. Traverse S, each time only comparing the distance between the current point and the 7 points above it.
[C++ code implementation]
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<conio.h>
#include<graphics.h>
#define MIN(a,b) ((a.dis)>(b.dis)?(b):(a))
#define fabs(a) ((a)<(0)?(-(a)):(a))
//two-dimensional point
struct point
{
int x, y;
};
//Find the two-dimensional distance function
double Distance(point a, point b){
return sqrt((double)((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)));
}
//divide
int Partition(point P[], int first, int end){
//Initialize the interval to be divided
int i = first, j = end;
while (i<j)
{
//Scan on the right
while (i<j & amp; & amp;P[i].y <= P[j].y)
{
j--;
}
//Move smaller records to the front
if (i<j)
{
int temp = P[i].y;
P[i].y = P[j].y;
P[j].y = temp;
i + + ;
}
while (i<j & amp; & amp;P[i].y <= P[j].y)
{
i + + ;
}
if (i<j)
{
int temp = P[i].y;
P[i].y = P[j].y;
P[j].y = temp;
j--;
}
}
return i;
}
//Quick sort
void QuickSort(point P[], int first, int end){
int pivot;
if (first<end)
{
pivot = Partition(P, first, end);
QuickSort(P, first, pivot - 1);
QuickSort(P, pivot + 1, end);
}
}
//Find the nearest point pair in two dimensions
double Closest(point S[], int low, int high, point & amp; a, point & amp; b){
double d1, d2, d3, d;
int mid, i, j, index;
//Storage point sets P1 and P2
point P[30];
//Only two points
if (high-low==1)
{
//printf("<%d,%d><%d,%d>\
", S[low].x, S[low].y, S[high].x, S[high].y );
a = S[low];
b = S[high];
return Distance(S[low], S[high]);
}
//Only three points
if (high-low==2)
{
d1 = Distance(S[low], S[low + 1]);
d2 = Distance(S[low + 1], S[high]);
d3 = Distance(S[low], S[high]);
if ((d1 < d2) & amp; & amp; (d1 < d3)){
a = S[low];
b = S[low + 1];
//printf("<%d,%d><%d,%d>\
", S[low].x, S[low].y, S[low + 1].x, S[low + 1].y);
return d1;
}
\t\t\t
else if (d2 < d3){
a = S[low + 1];
b = S[high];
//printf("<%d,%d><%d,%d>\
", S[low + 1].x, S[low + 1].y, S[high].x, S[ high].y);
return d2;
}
\t\t\t
else{
//printf("<%d,%d><%d,%d>\
", S[low].x, S[low].y, S[high].x, S[high].y );
a = S[low];
b = S[high];
return d3;
}
\t\t\t
}
//Now the points are starting to increase
mid = (low + high) / 2;
//Recursively solve sub-problem 1
d1 = Closest(S, low, mid,a,b);
//Recursively solve sub-problem 2
point ar, br;
d2 = Closest(S, mid + 1, high,ar,br);
if (d1<d2)
{
d = d1;
}
else
{
a = ar;
b = br;
d = d2;
}
index = 0;
//Create set P1
for (i = mid; (i >= low) & amp; & amp; ((S[mid].x - S[i].x) < d); i--){
P[index + + ] = S[i];
}
//Create set P2
for (i = mid + 1; (i <= high) & amp; & amp; ((S[i].x - S[mid].x) < d); i + + ){
P[index + + ] = S[i];
}
// Sort the contents of the two collections in ascending order on the Y axis
QuickSort(P, 0, index - 1);
for (i = 0; i < index; i + + ){
for (j = i + 1; j < index; j + + ){
if ((P[j].y-P[i].y)>=d)
{
break;
}
else
{
d3 = Distance(P[i], P[j]);
//printf("<%d,%d><%d,%d>\
", S[i].x, S[i].y, S[j].x, S[j].y );
if (d3<d)
{
a = P[i];
b = P[j];
d = d3;
}
}
}
}
return d;
}
//Bubble sorting method for structures
void BubbleSort(point *P, int len){
point temp;
for (int i = 0; i < len - 1; i + + )
{
for (int j = 0; j < len - i - 1; j + + )
{
if ((P + j)->x>(P + j + 1)->x)
{
temp = *(P + j);
*(P + j) = *(P + j + 1);
*(P + j + 1) = temp;
}
}
}
}
//Generate 30 points in the main function
int main()
{
//two-dimensional case
//Define member variables
int x[30], y[30];
int i,j,count=0;
point P[30];
//Randomly generate x,y coordinates
srand(time(NULL));
for ( i = 0; i < 30; i + + )
{
x[i] = 1 + (rand() % 100);
y[i] = 1 + (rand() % 100);
}
//Assign values to the structure array
for ( i = 0; i < 30; i + + )
{
P[i].x = x[i];
P[i].y = y[i];
}
BubbleSort(P, 30);
printf("The sorted random point pairs are:\
");
for (i = 0; i < 30; i + + )
{
printf("<%d,%d>\t", P[i].x, P[i].y);
count + + ;
if (count % 5 == 0)
{
printf("\
");
}
}
point a, b;
double length = Closest(P, 0, 29,a,b);
printf("The distance between the nearest point pair <%d,%d> and <%d,%d> is: %f\
", a.x,a.y,b.x,b.y,length);
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 55721 people are learning the system