Find closest point of every point (Nearest Neighbor)

Question

I am writing a method that takes as input an array of points and finds, for each point in the array, the closest point to it other than itself. I am currently doing this in a brute force way (cheking every point with every other point). My current implimentation doesn't have the array sorted but i can sort it by p.x values with the CompareByX method. I am chekcking the running time of the algorithm, and it gets very time consuming with large values of n. I am not very knowledgable on this subject and know very littel about different types of data structures, any simple help would be great!

My current code is:

import java.util.*;
import java.lang.*;
import java.io.*;

class My2dPoint {
  double x;
  double y;

  public My2dPoint(double x1, double y1) {
    x=x1;
    y=y1;
  }

}


class CompareByX implements Comparator<My2dPoint> {
    public int compare(My2dPoint p1, My2dPoint p2) {
    if (p1.x < p2.x) return -1;
        if (p1.x == p2.x) return 0;
        return 1;
    }
}

    /* An object of the above comparator class is used by java.util.Arrays.sort() in main to sort an array of points by x-coordinates */

class Auxiliaries {

    public static double distSquared(My2dPoint p1, My2dPoint p2) {
        double result;
        result = (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
        return result;
    }

}

public class HW3 {
    public static void main (String argv []) throws IOException {
        int range = 1000000; // Range of x and y coordinates in points

        System.out.println("Enter the number of points");

        InputStreamReader reader1 = new InputStreamReader(System.in);
        BufferedReader buffer1 = new BufferedReader(reader1);
        String npoints = buffer1.readLine();
        int numpoints = Integer.parseInt(npoints);

        // numpoints is now the number of points we wish to generate

        My2dPoint inputpoints [] = new My2dPoint [numpoints];

        // array to hold points

        int closest [] = new int [numpoints];

        // array to record soln; closest[i] is index of point closest to i'th

        int px, py;
        double dx, dy, dist;
        int i,j;
        double currbest;
        int closestPointIndex;
        long tStart, tEnd;

        for (i = 0; i < numpoints; i++) {

          px = (int) ( range * Math.random());
          dx = (double) px;
          py = (int) (range * Math.random());
          dy = (double) py;
          inputpoints[i] = new My2dPoint(dx, dy);

        }

        // array inputpoints has now been filled



        tStart = System.currentTimeMillis();

        // find closest [0]


        closest[0] = 1;
        currbest = Auxiliaries.distSquared(inputpoints[0],inputpoints[1]);
        for (j = 2; j < numpoints; j++) {
           dist = Auxiliaries.distSquared(inputpoints[0],inputpoints[j]);
           if (dist < currbest) {
               closest[0] = j;
               currbest = dist;
           }
        }

        // now find closest[i] for every other i 

        for (i = 1; i < numpoints; i++) {
            closest[i] = 0;
            currbest = Auxiliaries.distSquared(inputpoints[i],inputpoints[0]);
            for (j = 1; j < i; j++) {
              dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]);
              if (dist < currbest) {
               closest[i] = j;
               currbest = dist;
          }
            }

            for (j = i+1; j < numpoints; j++) {
              dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]);
              if (dist < currbest) {
          closest[i] = j;
                  currbest = dist;
          }
            }
        }

        tEnd = System.currentTimeMillis();
        System.out.println("Time taken in Milliseconds: " + (tEnd - tStart));
    }
}

Answer 1

Brute force for nearest neighbour search is only feasible for a small number of points.

You might want to look into kd-Trees or spatial data structures generally.

Here is a demo for kd-Tree. This is what wikipedia says.