вот еще одно решение. То, что он в основном делает, это загружает оба набора точек в два экземпляра дерева 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