Khoảng cách gần nhất giữa hai điểm (bộ tách rời)

Question

Vấn đề này là một cặp gần nhất giữa hai bộ phân tách. Hình ảnh bên ngoài được thể hiện vấn đề này. có hai loại bộ phân tách, các chấm màu xanh trong mặt phẳng -x, các chấm đỏ trong mặt phẳng + x.

tôi muốn để tính toán khoảng cách tối thiểu (khoảng cách là | y2-y1 | + | x2 - x1 |) giữa một xanh dot và một chấm đỏ, và tôi nghĩ rằng sử dụng tìm kiếm nhị phân để tìm khoảng cách. Làm thế nào để sử dụng tìm kiếm nhị phân loại vấn đề này? Tôi đấu tranh chỉ trên thể hiện tìm kiếm nhị phân hai bộ phân tách. Tôi đã biết cho một bộ, nhưng tôi không biết trong trường hợp hai bộ phân tách.

++) nó có thể trong thời gian tuyến tính bằng cách sử dụng Triangulation Delaunay? (ah, nó chỉ là sự tò mò của tôi, tôi muốn sử dụng tìm kiếm nhị phân)

bên dưới mã mà tôi đã mã hóa một bộ trường hợp (sử dụng kỹ thuật giải quyết vấn đề, chia và qonquer) và coverting thành hai bộ phân tách. Tôi không hiểu làm thế nào để làm trong hai bộ. Ví dụ, Gợi ý. okay .. xin vui lòng ai đó giúp tôi?

#include <iostream> 
#include <algorithm> 
#include <iomanip> 
#include <cmath> 

/** 
test input 
10 
-16 -4 
-1 -3 
-9 -1 
-4 -10 
-11 -6 
-20 4 
-13 6 
-3 -10 
-19 -1 
-12 -4 
10 
8 2 
10 3 
10 10 
20 -3 
20 3 
16 2 
3 -5 
14 -10 
8 -2 
14 0 

10 
-3 39 
-2 -28 
-1 20 
-3 11 
-3 45 
-2 -44 
-1 -47 
-5 -35 
-5 -19 
-5 -45 
10 
27 5 
28 0 
28 5 
21 5 
2 3 
13 -1 
16 -2 
20 -2 
33 -3 
27 1 
**/ 


using namespace std; 

const int MAX = 10001; 

struct point{ 
    int x,y; 
}; 

bool xCompare(struct point, struct point); 
bool yCompare(struct point, struct point); 
int dis(struct point, struct point); 

int absd(int); 
int trace(int,int,int,int); 

point p[MAX], q[MAX], tmp[MAX]; 

int main(){ 

    int left; 
    int right; 

    scanf("%d\n", &left); 
    memset(p,0,sizeof(p)); 
    memset(q,0,sizeof(q)); 
    memset(tmp,0,sizeof(tmp)); 


    for(int i=0; i<left; i++){ 
     cin >> p[i].x >> p[i].y; 
    } 

    scanf("%d\n", &right); 

    for(int j=0; j<right; j++){ 
     cin >> q[j].x >> q[j].y; 
    } 

    sort(p, p+left, xCompare); 
    sort(q, q+right, xCompare); 

    int min = trace(0,0, left-1, right-1); 

    printf("%d\n", min); 


    /** this is one set case. 
    while(true){ 
     cin >> n; 

     if(n == 0) break; 

     memset(p,0,sizeof(p)); 
     memset(tmp,0,sizeof(tmp)); 

     for(int i= 0;i<n;i++) 
      cin >> p[i].x >> p[i].y; 

     sort(p,p+n,xCompare); 

     int min = trace(0,n-1); 

     if(min < 10000 && n > 1){ 
      cout << fixed; 
      cout << setprecision(4) << min << endl; 
     } 
     else 
      cout << "INFINITY" << endl; 
    } 
    **/ 

    return 0; 
} 

int trace(int low1, int low2, int high1, int high2){ 

    if(high1 - low1 < 3){ 
     int value = dis(p[low1],q[low2+1]); 
     int nextValue; 

     if(high1 - low1 == 2){ 
      nextValue = dis(p[low1],q[low2+2]); 

      if(value > nextValue) 
       value = nextValue; 

      nextValue = dis(p[low1+1],q[low2+2]); 

      if(value > nextValue) 
       value = nextValue; 
     } 
     return value; 
    } 
    else{ 

     /* DIVIDE & QONQUER */ 

     int mid1 = (low1 + high1) >> 1; 
     int mid2 = (low2 + high2) >> 1; 
     int cnt = 0; 

     int leftValue = trace(low1,low2,mid1,mid2);  // left trace 
     int rightValue = trace(mid1+1,mid2+1,high1,high2); // right trace 

     // min value find 
     int value = leftValue < rightValue ? leftValue : rightValue; 

     /* Middle Condition Check : Y Line */ 

     // saving left 
     for(int i = low1;i<=mid1;i++){ 
      if(abs(p[i].x - q[mid2].x) <= value) 
       tmp[cnt++] = p[i]; 
     } 

     // saving right 
     for(int i = mid1+1;i<=high1;i++){ 
      if(absd(p[i].x - q[mid2+1].x) <= value) 
       tmp[cnt++] = p[i]; 
     } 

     sort(tmp,tmp+cnt,yCompare); 

     for(int i = 0;i<cnt;i++){ 
      int count = 0; 

      for(int j = i-3;count < 6 && j < cnt;j++){ 
       if(j >= 0 && i != j){ 
        int distance = dis(tmp[i],tmp[j]); 

        if(value > distance) 
         value = distance; 

        count++; 
       } 
      } 
     } 
     return value; 
    } 
} 

int absd(int x){ 
    if(x < 0) 
     return -x; 
    return x; 
} 

int dis(struct point a, struct point b){ 
    return (abs(a.x-b.x) + abs(a.y-b.y)); 
} 

bool xCompare(struct point a, struct point b){ 
    return a.x < b.x; 
} 

bool yCompare(struct point a, struct point b){ 
    return a.y < b.y; 
} 

Answer 1

Sự cố này thường được gọi là vấn đề đôi bichromatic gần nhất. Dưới đây là một vài cách tiếp cận.

1. Triangulation tam giác. (Điều này chắc chắn làm việc với L _{2 khoảng cách} (= Euclide), tôi nghĩ rằng các bước tổng quát thành L .) Đối với mỗi triangulation Delaunay (có thể có nhiều hơn một trong trường hợp thoái hóa), có tồn tại một cây bao trùm tối thiểu tất cả các cạnh thuộc về tam giác. Đổi lại, cây bao trùm tối thiểu này có cạnh ngắn nhất cắt ngang giữa các lớp màu.

2. Cấu trúc dữ liệu lân cận gần nhất.

3. Nếu các điểm màu đỏ được phân cách bằng x từ điểm màu xanh, thì bạn có thể điều chỉnh bước hợp nhất O (n) của thuật toán phân chia và conquer Shamos – Hoey cho gần nhất (monochromatic) cặp vấn đề, mô tả here.

Answer 2

Tôi đã làm việc trên một vấn đề tương tự nơi tôi phải tìm một thành viên gần nhất để xác định xem một thành viên thuộc về một cụm trong một cụm. Tôi đã cố gắng xác định các cụm trong các cụm. Đây là mã, Điều này có thể giúp bạn bắt đầu.

/** 
* Find the nearest neighbor based on the distance threshold. 
* TODO: 
* @param currentPoint current point in the memory. 
* @param threshold dynamic distance threshold. 
* @return return the neighbor. 
*/ 

private double nearestNeighbor(double currentPoint) { 

    HashMap<Double, Double> unsorted = new HashMap<Double, Double>(); 
    TreeMap<Double, Double> sorted = null; 
    double foundNeighbor = 0.0; 

    for (int i = 0; i < bigCluster.length; i++) { 
     if (bigCluster[i] != 0.0 && bigCluster[i] != currentPoint) { 
      double shortestDistance = Math.abs(currentPoint - bigCluster[i]); 
      if (shortestDistance <= this.getDistanceThreshold()) 
       unsorted.put(shortestDistance, bigCluster[i]); 
     } 
    } 
    if (!unsorted.isEmpty()) { 
     sorted = new TreeMap<Double, Double>(unsorted); 
     this.setDistanceThreshold(avgDistanceInCluster()); 
     foundNeighbor = sorted.firstEntry().getValue(); 
     return foundNeighbor; 
    } else { 
     return 0.0; 
    } 
} 


/** 
* Method will check if a point belongs to a cluster based on the dynamic 
* threshold. 
*/ 
public void isBelongToCluster() { 


     for (int i=0; i < tempList.size(); i++) { 

      double aPointInCluster = tempList.get(i); 

      cluster.add(aPointInCluster); 
      double newNeighbor = nearestNeighbor(aPointInCluster); 
      if (newNeighbor != 0.0) { 
       cluster.add(newNeighbor); 
       if (i + 1 > tempList.size() && (visited[i] != true)) { 
        isBelongToCluster(); 
       } 
      } 

     } 

    for (int i=0; i < cluster.size(); i++) { 
     if (cluster.get(i) != 0.0) 
      System.out.println("whats in the cluster -> " + cluster.get(i)); 
    } 
} 

Answer 3

Nếu bạn muốn thực hiện tìm kiếm nhị phân trên dữ liệu không gian, bạn có thể sử dụng cấu trúc dữ liệu không gian, chẳng hạn như cây quadtree hoặc k-d.

Answer 4

đây là một giải pháp khác. Những gì nó về cơ bản làm là tải cả hai tập hợp các điểm vào hai trường hợp cây kd (đã xây dựng cơ chế để cắt cây trên trục x và y) và sau đó điều hướng thông qua cả hai cây bằng cách kiểm tra mỗi nút nếu khoảng cách giữa hai ít hơn khoảng cách giữa các nút trước đó, nếu có thì tiếp tục cho đến khi không có hai nút nào có thể được tìm thấy với khoảng cách lẫn nhau ít hơn bất kỳ nút nào khác.

mã bên dưới in khoảng cách được tìm thấy trong khi điều hướng giữa các nút và in chúng. Cả hai tập hợp các điểm cũng được hiển thị để xem tính chính xác của thuật toán.

Mã này một cách chính xác có thể tìm thấy các nút gần bất kể một bộ được lồng nhau, ở bên phải, sang trái, lên hoặc xuống của người kia,

#include <iostream> 

using namespace std; 

int const k=2; // the number of dimensions 
double min_distance = 10000; // set a large default value, in this example all distance will be shorter than this. 

double distance(int arr[], int arr2[]) 
{ 
return sqrt(pow(arr2[0] - arr[0], 2) + pow(arr2[1] - arr[1], 2)); 

} 

struct Node { 
int point[k]; 
Node *left, *right; 
Node() 
{ 
    left = right = NULL; 

} 
}; 

// A method to create a node of K D tree 
struct Node* newNode(int arr[]) 
{ 
struct Node* temp = new Node; 

for (int i = 0; i<k; i++) temp->point[i] = arr[i]; 

return temp; 
} 

Node * insertNode(Node * node, int arr[], int d) 
{ 
if (node == NULL) 
    return newNode(arr); 

int dim = d%k; 


if (node->point[dim] > arr[dim]) 
{ 


    node->left = insertNode(node->left, arr, dim + 1); 
} 
else 
{ 

    node->right = insertNode(node->right, arr, dim + 1); 
} 

return node; 
} 
Node * Nearest=NULL; 

Node * FindnearestNode(Node * head1, int arr[], int d) 
{ 
// if empty tree, return 
if (head1 == NULL) 
    return NULL; 

// check for each tree. 
    if (min_distance > distance(head1->point, arr)) 
{ 
    min_distance = distance(head1->point, arr); 
    Nearest = head1; 
} 

if (head1->left == NULL && head1->right == NULL) 
    return head1; 

// findout current dimension, in this case it either x or y i.e. 0 or 1 
int dim = d%k; 

// navigate through the tree as if inserting to a new member (to remain to the nearest member in closeness). in the path for insert it will find the nearest member. 
if (head1->right && head1->point[dim] < arr[dim]) return FindnearestNode(head1->right, arr, d+1); 
else if(head1->left && head1->point[dim] > arr[dim]) 
    return FindnearestNode(head1->left, arr, d+1); 

return Nearest; 
} 


int main() 
{ 
int const an = 10; 
int const bn = 10; 

int ax[an] = { 34,55,11,79,77,65,3,9,5,66 }; 
int ay[an] = { 5, 6, 7, 9, 32,3,15,7,10,35 }; 

int bx[bn] = { 5,35,4,41,32,64,41,54,87,3 }; 
int by[bn] = { 23,33,17,15,32,22,33,23,21,32 }; 



Node * head1=NULL; 
Node * head2 = NULL; 



double Final_Min_Distance = min_distance; 

// fill the K-D trees with the two dimensional data in two trees. 
for (int i = 0; i < an; i++) 
{ 
    int temp[k]; 
    temp[0] = ax[i]; 
    temp[1] = ay[i]; 

    head1=insertNode(head1, temp, 0); 
    temp[0] = bx[i]; 
    temp[1] = by[i]; 

    head2=insertNode(head2, temp, 0); 


} 
Node * AnearB=NULL; 

Node * BnearA = NULL; 



min_distance = 1000; 
    Final_Min_Distance = min_distance; 
for (int i = 0; i < an; i++) { int temp[k]; temp[0] = bx[i]; temp[1] = by[i]; Node * Nearer2 = FindnearestNode(head1, temp, 0); if (Final_Min_Distance > min_distance) 
    { 
    BnearA = Nearer2; 
    Final_Min_Distance = min_distance; 
    } 
    cout << " distance of B (" << temp[0] << "," << temp[1] << ") to nearest A (" << BnearA->point[0] << "," << BnearA->point[1] << ") distance:" << Final_Min_Distance << endl; 
    min_distance = 1000; 


} 
cout << "Minimum Distance is " << Final_Min_Distance<<endl<<endl; 


min_distance = 1000; 
Final_Min_Distance = min_distance; 
for (int i = 0; i < an; i++) { int temp[k]; temp[0] = ax[i]; temp[1] = ay[i]; Node * Nearer2 = FindnearestNode(head2, temp, 0); if (Final_Min_Distance > min_distance) 
    { 
    AnearB = Nearer2; 
    Final_Min_Distance = min_distance; 
    } 
    cout << " distance of A (" << temp[0] << "," << temp[1] << ") to nearest B (" << AnearB->point[0] << "," << AnearB->point[1] << ") distance:" << Final_Min_Distance << endl; 
    min_distance = 1000; 


} 
cout << "Minimum Distance is " << Final_Min_Distance; 



system("pause"); 

} 

https://tahirnaeem.net/finding-closest-pair-of-points-in-two-disjoint-sets-of-points