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