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.

https://github.com/lessthanoptimal/ddogleg/tree/v0.23.3/examples/src/org/ddogleg/example/ExampleNearestNeighbor.java

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());
    // Multiple instances of search can be created. Each of these can be called independently in a thread
    NearestNeighbor.Search<Point2D> search = nn.createSearch();

    // 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 (search.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;
    }
}