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<Point2D> nn = FactoryNearestNeighbor.kdtree(new Distance());

    // Create data that's going to be searched
    List<Point2D> 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<Point2D> 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<Point2D> {

    // 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;
    }
}