la distancia más corta entre dos puntos (conjunto disjunto)

Question

Este problema es una especie de par más cercano entre los dos conjuntos disjuntos. Imagen superior se expresa este problema. hay dos tipos de conjunto disjunto, puntos azules en el plano x, puntos rojos en el plano + x.

Quiero calcular la distancia mínima (la distancia es | y2-y1 | + | x2 - x1 |) entre un punto azul y uno punto rojo, y creo que el uso búsqueda binaria para encontrar la distancia. ¿Cómo usar la búsqueda binaria de este tipo de problema? Lucho solo en expresando búsqueda binaria dos conjuntos disjuntos. I ya lo sé por un conjunto, pero no sé en el caso de dos conjuntos disjuntos.

++) ¿es lata en tiempo lineal usando la triangulación de Delaunay? (ah, es sólo mi curiosidad, quiero usar la búsqueda binaria)

debajo del código que ya he codificado un conjunto de casos (utilizando la técnica de resolución de problemas, dividir y qonquer) y covertir a dos conjuntos disjuntos. No entiendo cómo hacer en dos conjuntos. Ejemplo, sugerencia. de acuerdo ... por favor alguien me ayude?

#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

Este problema se suele llamar el problema de par bicromático más cercano. Aquí hay un par de enfoques.

1. Delaunay triangulation. (Esto ciertamente funciona con L (= euclidiana) distancias; creo que los pasos se generalizan a L .) Para cada triangulación de Delaunay (puede haber más de uno en casos degenerados), existe un árbol de expansión mínimo cuya todos los bordes pertenecen a la triangulación. A su vez, este árbol de expansión mínimo contiene un borde más corto que cruza el corte entre las clases de color.

2. Estructuras de datos vecinas más cercanas.

3. Si se da que los puntos rojos están separados en x de los puntos azules, entonces es posible que pueda adaptar el paso de fusión O (n) del algoritmo de división y conquista Shamos-Hoey para el más cercano problema de par (monocromático), descrito here.

Answer 2

trabajé en un problema similar donde tenía que encontrar un miembro cercano de identificar si un miembro pertenecen a un grupo dentro de un grupo. Estaba tratando de identificar clusters dentro de los clusters. Aquí está el código. Esto podría ayudarlo a comenzar.

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

Si desea hacer una búsqueda binaria sobre datos espaciales, se puede usar una estructura de datos espaciales, como por ejemplo un árbol cuaternario o un árbol k-d.

Answer 4

aquí hay una solución más. Lo que básicamente hace es cargar tanto el conjunto de puntos en dos instancias de árbol kd (que han construido un mecanismo para cortar el árbol en el eje xey) y luego navegar a través de ambos árboles al verificar cada nodo si las distancias entre los dos menor que la distancia entre los nodos anteriores, si es así, continúe hasta que no se encuentren dos nodos con la distancia mutua menor que cualquier otro.

el siguiente código imprime las distancias encontradas mientras navega entre los nodos y los imprime. Los dos conjuntos de puntos también se visualizan para ver la corrección del algorithem.

Este código se encuentra correctamente los nodos más cercanos, independientemente de si un juego está anidado, a la derecha, izquierda, arriba o abajo de la otra,

#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