最近距离（分离集）

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