Skip to main content

Nearest Neighbor Search Using KdTree





//Input should be in input.txt file
//10(2.1,4.3)(3.3,1.5)(4.7,11.1)(4.9,1.6)(5.0,12.3)(5.1,1.2)(6.7,3.3)(19.2,5.4)(20.5,7.9)(100.3,52)
//The first number is the number of points, n, and following it are the coordinates of the n points in ascending order of the x-coordinate.


import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.StringTokenizer;

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;

        double dx;
        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"));
        String strLin;
        strLin = in .readLine();

        StringTokenizer strLi = new StringTokenizer(strLin, "(,) ");
        int numpoints = Integer.parseInt(strLi.nextToken());

        KDTree kdt = new KDTree(numpoints);

        while (strLi.hasMoreTokens()) {

            double x[] = new double[2];
            for (int i = 0; i < numpoints; i++) {

                x[0] = Double.parseDouble(strLi.nextToken());
                x[1] = Double.parseDouble(strLi.nextToken());
                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("(" + kdn.x[0] + " , " + kdn.x[1] + ")");
    }
}
Labels:

Comments

  1. AnonymousMay 8, 2013 at 4:08 AM

    What is the license for this code?
    Would like to use it in a project of mine.

    Greetings.

    ReplyDelete
  2. AnonymousMay 29, 2013 at 12:14 PM

    Thanks for the post.

    ReplyDelete

Post a Comment

Popular posts from this blog

Ubuntu: Access a usb flash drive from the terminal

    1. Find what the drive is called You'll need to know what the drive is called to mount it. To do that fire off: sudo fdisk -l You're looking for a partition that should look something like:   /dev/sdb1 . Remember what it's called. 2. Create a mount point Create a new directory in   /media   so you can mount the drive onto the filesystem: sudo mkdir /media/usb 3. Mount! sudo mount /dev/sdb1 /media/usb When you're done, just fire off: sudo umount /media/usb Source: StackOverflow
1 comment
Read more

Java: Use BigInteger in for-loop

In my previous post , I mentioned a way to handle large integers by using BigInteger. Now I'm going to provide a very important usage of it. We often use for-loop. So here is the way to use it: Ordinary integers: for(int i = 1; i <= n; i++) {  //Task to do } BigInteger: for (BigInteger bi = BigInteger.valueOf(1);                 bi.compareTo(n) <= 0;                 bi = bi.add(BigInteger.ONE)) { //Task to do } here n is a BigInteger variable.
Post a Comment
Read more

Karabiner: Mouse/keyboard customizer for OS X

For beginners, or the one who migrated from Windows environment, Natural Gestures (Scrolling and Swiping) might be bit confusing. But, once you get familiarized with them, it may feel like "What was I doing, all those days?". It all changed, when I connected external mouse to my Macbook. When you start using that WHEEL, you will be confused. Luckily there is a setting for mouse, to change scroll behavior (natural or the other way). But, here's the catch. If you toggle that setting, it also toggles the same for TRACKPAD!!!!! I've seen that many people were freaked out and even raised BUG report to Apple. But, all those reports were closed, saying that is not a bug, but intentional feature!!! For those, who can't leave with such one-sided settings, here is a simple util, which came to my rescue: Karabiner It's simple, powerful and stable mouse/keyboard customizer for OSX. Without going into much detail, here's the configuration I used to ret
Post a Comment
Read more