Java Program to Find the Nearest Neighbor Using K-D Tree Search

This is a Java Program to implement 2D KD Tree and find nearest neighbor. In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

Here is the source code of the Java Program to Find the Nearest Neighbor Using K-D Tree Search. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to find nearest neighbor using KD Tree implementation
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
class KDNode
{
    int axis;
    double[] x;
    int id;
    boolean checked;
    boolean orientation;
 
    KDNode Parent;
    KDNode Left;
    KDNode Right;
 
    public KDNode(double[] x0, int axis0)
    {
        x = new double[2];
        axis = axis0;
        for (int k = 0; k < 2; k++)
            x[k] = x0[k];
 
        Left = Right = Parent = null;
        checked = false;
        id = 0;
    }
 
    public KDNode FindParent(double[] x0)
    {
        KDNode parent = null;
        KDNode next = this;
        int split;
        while (next != null)
        {
            split = next.axis;
            parent = next;
            if (x0[split] > next.x[split])
                next = next.Right;
            else
                next = next.Left;
        }
        return parent;
    }
 
    public KDNode Insert(double[] p)
    {
        //x = new double[2];
        KDNode parent = FindParent(p);
        if (equal(p, parent.x, 2) == true)
            return null;
 
        KDNode newNode = new KDNode(p, parent.axis + 1 < 2 ? parent.axis + 1
                : 0);
        newNode.Parent = parent;
 
        if (p[parent.axis] > parent.x[parent.axis])
        {
            parent.Right = newNode;
            newNode.orientation = true; //
        } else
        {
            parent.Left = newNode;
            newNode.orientation = false; //
        }
 
        return newNode;
    }
 
    boolean equal(double[] x1, double[] x2, int dim)
    {
        for (int k = 0; k < dim; k++)
        {
            if (x1[k] != x2[k])
                return false;
        }
 
        return true;
    }
 
    double distance2(double[] x1, double[] x2, int dim)
    {
        double S = 0;
        for (int k = 0; k < dim; k++)
            S += (x1[k] - x2[k]) * (x1[k] - x2[k]);
        return S;
    }
}
 
class KDTree
{
    KDNode Root;
 
    int TimeStart, TimeFinish;
    int CounterFreq;
 
    double d_min;
    KDNode nearest_neighbour;
 
    int KD_id;
 
    int nList;
 
    KDNode CheckedNodes[];
    int checked_nodes;
    KDNode List[];
 
    double x_min[], x_max[];
    boolean max_boundary[], min_boundary[];
    int n_boundary;
 
    public KDTree(int i)
    {
        Root = null;
        KD_id = 1;
        nList = 0;
        List = new KDNode[i];
        CheckedNodes = new KDNode[i];
        max_boundary = new boolean[2];
        min_boundary = new boolean[2];
        x_min = new double[2];
        x_max = new double[2];
    }
 
    public boolean add(double[] x)
    {
        if (nList >= 2000000 - 1)
            return false; // can't add more points
 
        if (Root == null)
        {
            Root = new KDNode(x, 0);
            Root.id = KD_id++;
            List[nList++] = Root;
        } else
        {
            KDNode pNode;
            if ((pNode = Root.Insert(x)) != null)
            {
                pNode.id = KD_id++;
                List[nList++] = pNode;
            }
        }
 
        return true;
    }
 
    public KDNode find_nearest(double[] x)
    {
        if (Root == null)
            return null;
 
        checked_nodes = 0;
        KDNode parent = Root.FindParent(x);
        nearest_neighbour = parent;
        d_min = Root.distance2(x, parent.x, 2);
        ;
 
        if (parent.equal(x, parent.x, 2) == true)
            return nearest_neighbour;
 
        search_parent(parent, x);
        uncheck();
 
        return nearest_neighbour;
    }
 
    public void check_subtree(KDNode node, double[] x)
    {
        if ((node == null) || node.checked)
            return;
 
        CheckedNodes[checked_nodes++] = node;
        node.checked = true;
        set_bounding_cube(node, x);
 
        int dim = node.axis;
        double d = node.x[dim] - x[dim];
 
        if (d * d > d_min)
        {
            if (node.x[dim] > x[dim])
                check_subtree(node.Left, x);
            else
                check_subtree(node.Right, x);
        } else
        {
            check_subtree(node.Left, x);
            check_subtree(node.Right, x);
        }
    }
 
    public void set_bounding_cube(KDNode node, double[] x)
    {
        if (node == null)
            return;
        int d = 0;
        double dx;
        for (int k = 0; k < 2; k++)
        {
            dx = node.x[k] - x[k];
            if (dx > 0)
            {
                dx *= dx;
                if (!max_boundary[k])
                {
                    if (dx > x_max[k])
                        x_max[k] = dx;
                    if (x_max[k] > d_min)
                    {
                        max_boundary[k] = true;
                        n_boundary++;
                    }
                }
            } else
            {
                dx *= dx;
                if (!min_boundary[k])
                {
                    if (dx > x_min[k])
                        x_min[k] = dx;
                    if (x_min[k] > d_min)
                    {
                        min_boundary[k] = true;
                        n_boundary++;
                    }
                }
            }
            d += dx;
            if (d > d_min)
                return;
 
        }
 
        if (d < d_min)
        {
            d_min = d;
            nearest_neighbour = node;
        }
    }
 
    public KDNode search_parent(KDNode parent, double[] x)
    {
        for (int k = 0; k < 2; k++)
        {
            x_min[k] = x_max[k] = 0;
            max_boundary[k] = min_boundary[k] = false; //
        }
        n_boundary = 0;
 
        KDNode search_root = parent;
        while (parent != null && (n_boundary != 2 * 2))
        {
            check_subtree(parent, x);
            search_root = parent;
            parent = parent.Parent;
        }
 
        return search_root;
    }
 
    public void uncheck()
    {
        for (int n = 0; n < checked_nodes; n++)
            CheckedNodes[n].checked = false;
    }
 
}
 
public class KDTNearest
{
 
    public static void main(String args[]) throws IOException
    {
        BufferedReader in = new BufferedReader(new FileReader("input.txt"));
        int numpoints = 5;
 
        KDTree kdt = new KDTree(numpoints);
        double x[] = new double[2];
 
        x[0] = 2.1;
        x[1] = 4.3;
        kdt.add(x);
 
        x[0] = 3.3;
        x[1] = 1.5;
        kdt.add(x);
 
        x[0] = 4.7;
        x[1] = 11.1;
        kdt.add(x);
 
        x[0] = 5.0;
        x[1] = 12.3;
        kdt.add(x);
 
        x[0] = 5.1;
        x[1] = 1.2;
        kdt.add(x);
 
        System.out
                .println("Enter the co-ordinates of the point: (one after the other)");
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        double sx = Double.parseDouble(br.readLine());
        double sy = Double.parseDouble(br.readLine());
 
        double s[] = { sx, sy };
        KDNode kdn = kdt.find_nearest(s);
        System.out.println("The nearest neighbor is: ");
        System.out.println("(" + kdn.x[0] + " , " + kdn.x[1] + ")");
        in.close();
    }
}

Output:

$ javac KDTNearest.java
$ java KDTNearest
 
Enter the co-ordinates of the point: (one after the other)
4.3
1.5
The nearest neighbor is: 
(5.1 , 1.2)

Related posts:

Bootstrapping Hibernate 5 with Spring
Daemon Threads in Java
Converting a Stack Trace to a String in Java
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
Sending Emails with Java
So sánh ArrayList và Vector trong Java
Java Program to Find Maximum Element in an Array using Binary Search
Java Program to Emulate N Dice Roller
Java Program to Implement the Vigenere Cypher
Unsatisfied Dependency in Spring
Hướng dẫn Java Design Pattern – DAO
Spring REST API + OAuth2 + Angular
An Intro to Spring Cloud Contract
Java Program to Check if a Point d lies Inside or Outside a Circle Defined by Points a, b, c in a Pl...
HandlerAdapters in Spring MVC
Java Program to do a Depth First Search/Traversal on a graph non-recursively
Guide to java.util.concurrent.Future
Calling Stored Procedures from Spring Data JPA Repositories
Phương thức tham chiếu trong Java 8 – Method References
Java Program to implement Array Deque
Registration – Activate a New Account by Email
Guide to the ConcurrentSkipListMap
Count Occurrences of a Char in a String
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Spring Boot - Enabling Swagger2
Java Program to Implement Bucket Sort
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
The “final” Keyword in Java
Spring Boot - OAuth2 with JWT
A Comparison Between Spring and Spring Boot
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS