Find minimum distance between 2 points in 2 arrays

Question

I have 2 lists containing points (x,y and z) and would like to find the closest points.

I assume I need to do something like this:

for (int i = 0; i < myarray1.Count; i++)
{
  for (int j = 0; j < myarray2.Count; j++)
  {
    // Calculate the quadratic distance between 2 points (point in index i and j)
    // Then store the minimum distance I guess?   
  }
}

Answer 1

To compute the distance:

double sqr(double x) {return x*x;}

double distance(MyPoint a, MyPoint b) {
  return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)+sqr(a.z-b.z);
}

Then in the second loop you store the minimum distance found so far:

double d = distance(myarray1[i],myarray2[j]);
if (d<min_d) min_d = d;

where min_d is defined at the beginning:

double min_d = Float.MAX_VALUE;

Answer 2

another option is to use Kd-tree
using the Nearest neighbour search will give you a O(log n) complexity to find the nearest point to a given set of points, and your code will have O( n log n), instead of O (n^2).

see here for implementation and example of how to use it.

Answer 3

  double min_dist = DOUBLE_MAX;
  for (i = 0; i < myarray1.Count; i++)
   {
     for (j = 0; j < myarray2.Count; j++)
     {
       curr_dist = dist(a[i],a[j]);  
       if( min_dist > curr_dist)
         {
              min_dist = curr_dist;
         }
     }
   }

where

double dist(Point a, Point b) {
  return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2);
}

Answer 4

In C# I would do this using Linq.

First I would define the function that calculates the distance between two points as in Emanuelle Paolini's answer:

public double Distance(Point p1, Point p2)
{
   return Math.Sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p1.y) * (p1.y - p1.y) + (p1.z - p1.z) * (p1.z - p1.z));
}

Then I would query the two lists as follows:

var distanceQuery = from p1 in myarray1
                    from p2 in myarray2
                    select Dist(p1, p2);

And finally I would retrieve the minimum distance:

var minimumDistance = distanceQuery.Min();

Answer 5

Formula is

Math.sqrt(Math.pow(Math.abs(x1-x2),2) + Math.pow(Math.abs(y1-y2),2)+ Math.pow(Math.abs(z1-z2),2))