Java – find the nearest point (nearest neighbor) of each point

I'm writing a method that takes an array of points as input and finds the closest point to each point in the array except itself I am currently doing this in a brute force way (every other point intersects with every point) My current implementation does not sort the array, but I can sort it by p.x value using the comparebyx method I am considering the running time of the algorithm, and using a large n value will be very time-consuming I don't know much about this topic, and I know a lot 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));
    }
}

Solution

The brute force of nearest neighbor search is only applicable to a small number of points

You may want to view KD trees or spatial data structures in general

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