# Nearest Neighbor¶

A nearest neighbor searches for all the neighbors of a point inside of a set which minimizes a distance metric. In DDogleg the only distance metric available is Euclidean distance squares, which is the same as minimizing Euclidean distance, but faster.

ExampleNearestNeighbor.java

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 public static void main( String args[] ) { // Easiest way to create a NN algorithm is using the factory below // The class Distance (defined below) describes the data type which the kd tree will be processing // It specifies the degree of freedom and provides access to each element in the data type NearestNeighbor nn = FactoryNearestNeighbor.kdtree(new Distance()); // Create data that's going to be searched List points = new ArrayList<>(); // For sake of demonstration add a set of points along the line for( int i = 0; i < 10; i++ ) { points.add(new Point2D(i,i*2)); } // Pass the points and associated data. Internally a data structure is constructed that enables fast lookup. // This can be one of the more expensive operations, depending on which implementation is used. nn.setPoints(points,true); // declare storage for where to store the result NnData result = new NnData<>(); // It will look for the closest point to [1.1,2.2] which will be [1,2] // The second parameter specifies the maximum distance away that it will consider for a neighbor // set to -1 to set to the largest possible value if( nn.findNearest(new Point2D(1.1,2.2),-1,result) ) { System.out.println("Best match:"); System.out.println(" point = "+result.point.x+" "+result.point.y); System.out.println(" data = "+result.index); System.out.println(" distance = "+result.distance); } else { System.out.println("No match found"); } } /** * Describe the Point2D data type so that the nearest-neighbor search will understand it */ public static class Distance implements KdTreeDistance { // How far apart two points are @Override public double distance(Point2D a, Point2D b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); } // value for element index in point @Override public double valueAt(Point2D point, int index) { if( index == 0 ) return point.x; else return point.y; } // Number of elements in point @Override public int length() { return 2; } }