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

Reverse Engineering : Extract contents from .img file

Unyaffs is a program to extract files from a YAFFS2 file system image. Currently it can only extract images created by mkyaffs2image. Download the source from here . Compiling : Extract the contents into a suitable place and run the following command make Usage : unyaffs [options] <image_file_name> [<extract_directory>] Options: -d detection of flash layout, no extraction -b spare contains bad block information -c <chunk size> set chunk size in KByte (default: autodetect, max: 16) -s <spare size> set spare size in Byte (default: autodetect, max: 512) -t list image contents -v verbose output -V print version Source: Official github repository
Post a Comment
Read more

Mac Yosemite : Ugly turned out to be Uglier and Ugliest

You might have read my review on Mac OSX Yosemite , The Good, bad and ugly. Now it turned out to be UGLIEST. No more words. Here's the image. If you are on Yosemite, you might be familiar with it. Most of the times, you get stuck on boot logo. I've seen complaints regarding it saying that fellow members are ignorant of it and they deny such possibility, even though many are still facing it. Workarounds suggested by our online friends: Just reboot your mac as many times it takes to your desktop. Boot into safe mode, by holding SHIFT and then reboot. Comment your workaround below, mine is the first one. If you are still on Mavericks, be there till Apple provides a fix for this.
Post a Comment
Read more

Reverse Engineering : Android Dex files to Class files

In my previous post, we have seen how to extract the contents of img file . After extraction, you will find that most of the files have ".dex" extension. These are Compiled Android application code files. In order to convert them into executable format (.class or .jar), you can use dex2jar tool. Extract it to a proper location and open the terminal to this location. Now run the following command: ./d2j-dex2jar.sh <Path-to-dex_file> It will bundle the dex files into a jar file, and stores it in the current directory. dex2jar can also be used to convert dex files into variuos other formats. For detailed info, click here .
Post a Comment
Read more