最近距離（分離集）

Question

此問題是一種兩個不相交的集合之間接近的對。 Upperside圖片表達了這個問題。有兩種不相交的集合，-x平面中的藍色點，+ x平面中的紅色點。

我要計算最小距離（距離| Y2-Y1 | + | X2 - X1 |）一一之間藍點和紅點，我認爲使用二進制搜索查找距離。如何使用二進制搜索這種問題？ 我只在表達二分查找兩個不相交的集合。我已經知道一套，但我不知道情況下，兩個不相交的集合。

++）它可以在線性時間使用Delaunay三角剖分嗎？ （啊，這只是我的好奇心，我想用二進制搜索）

下面的代碼，我已經編碼一組案例（使用問題解決技術，分裂和qonquer）和轉換爲兩個不相交的集合。我不明白如何做兩套。 示例，提示。好的..請有人幫我？

#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

此問題通常被稱爲最接近的雙色對問題。這裏有幾種方法。

1. Delaunay三角。 （這當然適用於L （= Euclidean）距離;我認爲這些步驟概括爲L 。）對於每個Delaunay三角測量（在退化情況下可以有多於一個），存在一個最小生成樹，邊緣都屬於三角測量。反過來，這個最小生成樹包含跨越顏色類之間的切割的最短邊。

2. 最近的鄰居數據結構。

3. 如果給出紅點與x點分開，那麼您可以調整Shamos-Hoey分而治之算法的O（n）合併步驟，使其最接近（單色）對問題，描述爲here。

Answer 2

我曾在一個類似的問題，我必須找到確定是否一個成員屬於一個集羣內的簇最近的成員。我試圖確定羣集內的羣集。這是代碼，這可能會幫助你開始。

/** 
* 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

如果你想要做的空間數據的二進制搜索，你可以使用一個空間數據結構，如四叉樹或K-d樹。

Answer 4

這裏有一個更多的解決方案。它基本上做的是將兩個點集合加載到兩個kd樹實例中（它們已經構建了在x軸和y軸上切片樹的機制），然後通過檢查每個節點來檢查兩個樹之間的距離是否通過兩個樹進行導航小於先前節點之間的距離，如果是，則繼續，直到找不到兩個節點之間的相互距離小於任何其他節點。

下面的代碼打印而在節點之間進行導航並打印它們找到的距離。這兩組點也可以被看到，以查看算法的正確性。

這個代碼能夠正確，無論找到最近的一個節點集是否嵌套，右，左，上或下的其他的，

#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