Trong bài toán này, tập hợp n điểm được cho trên mặt phẳng 2D. Trong bài toán này, chúng ta phải tìm cặp điểm có khoảng cách là nhỏ nhất.
Để giải quyết vấn đề này, chúng ta phải chia các điểm thành hai nửa, sau đó khoảng cách nhỏ nhất giữa hai điểm được tính theo cách đệ quy. Sử dụng khoảng cách từ đường giữa, các điểm được tách thành một số dải. Chúng tôi sẽ tìm khoảng cách nhỏ nhất từ mảng dải. Lúc đầu, hai danh sách được tạo bằng các điểm dữ liệu, một danh sách sẽ chứa các điểm được sắp xếp theo giá trị x, danh sách khác sẽ chứa các điểm dữ liệu, được sắp xếp theo giá trị y.
Độ phức tạp về thời gian của thuật toán này sẽ là O (n log n).
Đầu vào và Đầu ra
Input: A set of different points are given. (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4) Output: Find the minimum distance from each pair of given points. Here the minimum distance is: 1.41421 unit
Thuật toán
findMinDist (pointsList, n)
Đầu vào: Đã cho danh sách điểm và số điểm trong danh sách.
Đầu ra - Tìm khoảng cách tối thiểu từ hai điểm.
Begin min := ∞ for all items i in the pointsList, do for j := i+1 to n-1, do if distance between pointList[i] and pointList[j] < min, then min = distance of pointList[i] and pointList[j] done done return min End
stripClose (dải, kích thước, dist)
Đầu vào - Các điểm khác nhau trên dải, số điểm, khoảng cách từ đường giữa.
Đầu ra - Khoảng cách gần nhất từ hai điểm trong một dải.
Begin for all items i in the strip, do for j := i+1 to size-1 and (y difference of ithand jth points) <min, do if distance between strip[i] and strip [j] < min, then min = distance of strip [i] and strip [j] done done return min End
findClosest (xSorted, ySorted, n)
Đầu vào - Điểm được sắp xếp theo giá trị x và điểm được sắp xếp theo giá trị y, số điểm.
Đầu ra - Tìm khoảng cách tối thiểu từ tổng số điểm.
Begin if n <= 3, then call findMinDist(xSorted, n) return the result mid := n/2 midpoint := xSorted[mid] define two sub lists of points to separate points along vertical line. the sub lists are, ySortedLeft and ySortedRight leftDist := findClosest(xSorted, ySortedLeft, mid) //find left distance rightDist := findClosest(xSorted, ySortedRight, n - mid) //find right distance dist := minimum of leftDist and rightDist make strip of points j := 0 for i := 0 to n-1, do if difference of ySorted[i].x and midPoint.x<dist, then strip[j] := ySorted[i] j := j+1 done close := stripClose(strip, j, dist) return minimum of close and dist End
Ví dụ
#include <iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct point {
int x, y;
};
intcmpX(point p1, point p2) { //to sort according to x value
return (p1.x < p2.x);
}
intcmpY(point p1, point p2) { //to sort according to y value
return (p1.y < p2.y);
}
float dist(point p1, point p2) { //find distance between p1 and p2
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
float findMinDist(point pts[], int n) { //find minimum distance between two points in a set
float min = 9999;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(pts[i], pts[j]) < min)
min = dist(pts[i], pts[j]);
return min;
}
float min(float a, float b) {
return (a < b)? a : b;
}
float stripClose(point strip[], int size, float d) { //find closest distance of two points in a strip
float min = d;
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;
}
float findClosest(point xSorted[], point ySorted[], int n){
if (n <= 3)
return findMinDist(xSorted, n);
int mid = n/2;
point midPoint = xSorted[mid];
point ySortedLeft[mid+1]; // y sorted points in the left side
point ySortedRight[n-mid-1]; // y sorted points in the right side
intleftIndex = 0, rightIndex = 0;
for (int i = 0; i < n; i++) { //separate y sorted points to left and right
if (ySorted[i].x <= midPoint.x)
ySortedLeft[leftIndex++] = ySorted[i];
else
ySortedRight[rightIndex++] = ySorted[i];
}
float leftDist = findClosest(xSorted, ySortedLeft, mid);
float rightDist = findClosest(ySorted + mid, ySortedRight, n-mid);
float dist = min(leftDist, rightDist);
point strip[n]; //hold points closer to the vertical line
int j = 0;
for (int i = 0; i < n; i++)
if (abs(ySorted[i].x - midPoint.x) <dist) {
strip[j] = ySorted[i];
j++;
}
return min(dist, stripClose(strip, j, dist)); //find minimum using dist and closest pair in strip
}
float closestPair(point pts[], int n) { //find distance of closest pair in a set of points
point xSorted[n];
point ySorted[n];
for (int i = 0; i < n; i++) {
xSorted[i] = pts[i];
ySorted[i] = pts[i];
}
sort(xSorted, xSorted+n, cmpX);
sort(ySorted, ySorted+n, cmpY);
return findClosest(xSorted, ySorted, n);
}
int main() {
point P[] ={{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
int n = 6;
cout<< "The minimum distance is " <<closestPair(P, n);
} Đầu ra
The minimum distance is 1.41421