Алгоритм поиска кратчайшего расстояния от точки в множестве A до точек в множестве B

Question

Существует множество A с n 3d точками (x, y, z) и множество B с m 3d точками (x, y, z). Для каждой точки (Xi, Yi, Zi) в множестве A нам нужно найти точку в множестве B, имеющую минимальное расстояние от (Xi, Yi, Zi).

Мой код истекает с заданным сроком. Пожалуйста помоги.

#include<stdio.h> 
#include<stdlib.h> 
#include<math.h> 
long long np[50000][3],qp[50000][3]; 
int main() 
{ 
long long n,q,i,j,d,ans,min; 
scanf("%lld",&n); 
for(i=0;i<n;i++) 
    scanf("%lld%lld%lld",&np[i][0],&np[i][0],&np[i][2]); 
scanf("%lld",&q); 
for(i=0;i<q;i++) 
scanf("%lld%lld%lld",&qp[i][0],&qp[i][1],&qp[i][2]); 
for(i=0;i<q;i++) 
{ 
    ans=0; 
    min=((qp[i][0]-np[0][0])*(qp[i][0]-np[0][0]))+((qp[i][1]-np[0][1])*(qp[i][1]-qp[0][1]))+((qp[i][2]-np[0][2])*(qp[i][2]-np[0][2])); 
    for(j=0;j<n;j++) 
    { 
     d=((qp[i][0]-np[j][0])*(qp[i][0]-np[j][0]))+((qp[i][1]-np[j][1])*(qp[i][1]-qp[j][1]))+((qp[i][2]-np[j][2])*(qp[i][2]-np[j][2])); 
     if(d<min) 
     { 
      ans=j; 
      min=d; 
     } 
    } 
    printf("%lld\n",ans); 
} 
return 0; 
} 

Answer 1

Вы используете алгорифм O (n^2). Я сомневаюсь, что это достаточно быстро. Для некоторых способов сделать это быстрее, проверьте this article.

Или, более конкретно, вы можете использовать подход, основанный на принципе разделения, описанный в этой статье, что относительно просто, если вам удобно рекурсия. Поскольку вы имеете дело с осью z, вам нужно расширить описанный там алгоритм, чтобы использовать две разделительные линии (одну для оси x, затем одну для y), так что это будет немного сложнее.

Answer 2

. Один из подходов - создать nearest neighbour triangulation из любого набора, который является O (n log n), затем использовать что-то вроде proximity search, чтобы закрепить каждую точку в очереди от другого набора на триангуляцию, чтобы найти ближайший сосед. Для такого типа вещей в C, Joseph O'Rourkes book будет полезно прочитать.