Java Program to Construct K-D Tree for 2 Dimensional Data

«
»
This is a Java Program to implement 2D KD Tree and print the various traversals. 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 Construct K-D Tree for 2 Dimensional Data (assume static data). The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to construct a KD tree for two dimensional static data
  2. import java.io.IOException;
  3.  
  4. class KD2DNode
  5. {
  6.     int axis;
  7.     double[] x;
  8.     int id;
  9.     boolean checked;
  10.     boolean orientation;
  11.  
  12.     KD2DNode Parent;
  13.     KD2DNode Left;
  14.     KD2DNode Right;
  15.  
  16.     public KD2DNode(double[] x0, int axis0)
  17.     {
  18.         x = new double[2];
  19.         axis = axis0;
  20.         for (int k = 0; k < 2; k++)
  21.             x[k] = x0[k];
  22.  
  23.         Left = Right = Parent = null;
  24.         checked = false;
  25.         id = 0;
  26.     }
  27.  
  28.     public KD2DNode FindParent(double[] x0)
  29.     {
  30.         KD2DNode parent = null;
  31.         KD2DNode next = this;
  32.         int split;
  33.         while (next != null)
  34.         {
  35.             split = next.axis;
  36.             parent = next;
  37.             if (x0[split] > next.x[split])
  38.                 next = next.Right;
  39.             else
  40.                 next = next.Left;
  41.         }
  42.         return parent;
  43.     }
  44.  
  45.     public KD2DNode Insert(double[] p)
  46.     {
  47.         x = new double[2];
  48.         KD2DNode parent = FindParent(p);
  49.         if (equal(p, parent.x, 2) == true)
  50.             return null;
  51.  
  52.         KD2DNode newNode = new KD2DNode(p,
  53.                 parent.axis + 1 < 2 ? parent.axis + 1 : 0);
  54.         newNode.Parent = parent;
  55.  
  56.         if (p[parent.axis] > parent.x[parent.axis])
  57.         {
  58.             parent.Right = newNode;
  59.             newNode.orientation = true; //
  60.         } else
  61.         {
  62.             parent.Left = newNode;
  63.             newNode.orientation = false; //
  64.         }
  65.  
  66.         return newNode;
  67.     }
  68.  
  69.     boolean equal(double[] x1, double[] x2, int dim)
  70.     {
  71.         for (int k = 0; k < dim; k++)
  72.         {
  73.             if (x1[k] != x2[k])
  74.                 return false;
  75.         }
  76.  
  77.         return true;
  78.     }
  79.  
  80.     double distance2(double[] x1, double[] x2, int dim)
  81.     {
  82.         double S = 0;
  83.         for (int k = 0; k < dim; k++)
  84.             S += (x1[k] - x2[k]) * (x1[k] - x2[k]);
  85.         return S;
  86.     }
  87. }
  88.  
  89. class KD2DTree
  90. {
  91.     KD2DNode Root;
  92.  
  93.     int TimeStart, TimeFinish;
  94.     int CounterFreq;
  95.  
  96.     double d_min;
  97.     KD2DNode nearest_neighbour;
  98.  
  99.     int KD_id;
  100.  
  101.     int nList;
  102.  
  103.     KD2DNode CheckedNodes[];
  104.     int checked_nodes;
  105.     KD2DNode List[];
  106.  
  107.     double x_min[], x_max[];
  108.     boolean max_boundary[], min_boundary[];
  109.     int n_boundary;
  110.  
  111.     public KD2DTree(int i)
  112.     {
  113.         Root = null;
  114.         KD_id = 1;
  115.         nList = 0;
  116.         List = new KD2DNode[i];
  117.         CheckedNodes = new KD2DNode[i];
  118.         max_boundary = new boolean[2];
  119.         min_boundary = new boolean[2];
  120.         x_min = new double[2];
  121.         x_max = new double[2];
  122.     }
  123.  
  124.     public boolean add(double[] x)
  125.     {
  126.         if (nList >= 2000000 - 1)
  127.             return false; // can't add more points
  128.  
  129.         if (Root == null)
  130.         {
  131.             Root = new KD2DNode(x, 0);
  132.             Root.id = KD_id++;
  133.             List[nList++] = Root;
  134.         } else
  135.         {
  136.             KD2DNode pNode;
  137.             if ((pNode = Root.Insert(x)) != null)
  138.             {
  139.                 pNode.id = KD_id++;
  140.                 List[nList++] = pNode;
  141.             }
  142.         }
  143.  
  144.         return true;
  145.     }
  146.  
  147.     public KD2DNode find_nearest(double[] x)
  148.     {
  149.         if (Root == null)
  150.             return null;
  151.  
  152.         checked_nodes = 0;
  153.         KD2DNode parent = Root.FindParent(x);
  154.         nearest_neighbour = parent;
  155.         d_min = Root.distance2(x, parent.x, 2);
  156.         ;
  157.  
  158.         if (parent.equal(x, parent.x, 2) == true)
  159.             return nearest_neighbour;
  160.  
  161.         search_parent(parent, x);
  162.         uncheck();
  163.  
  164.         return nearest_neighbour;
  165.     }
  166.  
  167.     public void check_subtree(KD2DNode node, double[] x)
  168.     {
  169.         if ((node == null) || node.checked)
  170.             return;
  171.  
  172.         CheckedNodes[checked_nodes++] = node;
  173.         node.checked = true;
  174.         set_bounding_cube(node, x);
  175.  
  176.         int dim = node.axis;
  177.         double d = node.x[dim] - x[dim];
  178.  
  179.         if (d * d > d_min)
  180.         {
  181.             if (node.x[dim] > x[dim])
  182.                 check_subtree(node.Left, x);
  183.             else
  184.                 check_subtree(node.Right, x);
  185.         } else
  186.         {
  187.             check_subtree(node.Left, x);
  188.             check_subtree(node.Right, x);
  189.         }
  190.     }
  191.  
  192.     public void set_bounding_cube(KD2DNode node, double[] x)
  193.     {
  194.         if (node == null)
  195.             return;
  196.         int d = 0;
  197.         double dx;
  198.         for (int k = 0; k < 2; k++)
  199.         {
  200.             dx = node.x[k] - x[k];
  201.             if (dx > 0)
  202.             {
  203.                 dx *= dx;
  204.                 if (!max_boundary[k])
  205.                 {
  206.                     if (dx > x_max[k])
  207.                         x_max[k] = dx;
  208.                     if (x_max[k] > d_min)
  209.                     {
  210.                         max_boundary[k] = true;
  211.                         n_boundary++;
  212.                     }
  213.                 }
  214.             } else
  215.             {
  216.                 dx *= dx;
  217.                 if (!min_boundary[k])
  218.                 {
  219.                     if (dx > x_min[k])
  220.                         x_min[k] = dx;
  221.                     if (x_min[k] > d_min)
  222.                     {
  223.                         min_boundary[k] = true;
  224.                         n_boundary++;
  225.                     }
  226.                 }
  227.             }
  228.             d += dx;
  229.             if (d > d_min)
  230.                 return;
  231.  
  232.         }
  233.  
  234.         if (d < d_min)
  235.         {
  236.             d_min = d;
  237.             nearest_neighbour = node;
  238.         }
  239.     }
  240.  
  241.     public KD2DNode search_parent(KD2DNode parent, double[] x)
  242.     {
  243.         for (int k = 0; k < 2; k++)
  244.         {
  245.             x_min[k] = x_max[k] = 0;
  246.             max_boundary[k] = min_boundary[k] = false; //
  247.         }
  248.         n_boundary = 0;
  249.  
  250.         KD2DNode search_root = parent;
  251.         while (parent != null && (n_boundary != 2 * 2))
  252.         {
  253.             check_subtree(parent, x);
  254.             search_root = parent;
  255.             parent = parent.Parent;
  256.         }
  257.  
  258.         return search_root;
  259.     }
  260.  
  261.     public void uncheck()
  262.     {
  263.         for (int n = 0; n < checked_nodes; n++)
  264.             CheckedNodes[n].checked = false;
  265.     }
  266.  
  267.     public void inorder()
  268.     {
  269.         inorder(Root);
  270.     }
  271.  
  272.     private void inorder(KD2DNode root)
  273.     {
  274.         if (root != null)
  275.         {
  276.             inorder(root.Left);
  277.             System.out.print("(" + root.x[0] + ", " + root.x[1] + ")  ");
  278.             inorder(root.Right);
  279.         }
  280.     }
  281.  
  282.     public void preorder()
  283.     {
  284.         preorder(Root);
  285.     }
  286.  
  287.     private void preorder(KD2DNode root)
  288.     {
  289.         if (root != null)
  290.         {
  291.             System.out.print("(" + root.x[0] + ", " + root.x[1] + ")  ");
  292.             inorder(root.Left);
  293.             inorder(root.Right);
  294.         }
  295.     }
  296.  
  297.     public void postorder()
  298.     {
  299.         postorder(Root);
  300.     }
  301.  
  302.     private void postorder(KD2DNode root)
  303.     {
  304.         if (root != null)
  305.         {
  306.             inorder(root.Left);
  307.             inorder(root.Right);
  308.             System.out.print("(" + root.x[0] + ", " + root.x[1] + ")  ");
  309.         }
  310.     }
  311. }
  312.  
  313. public class KDTree_TwoD_Data
  314. {
  315.     public static void main(String args[]) throws IOException
  316.     {
  317.         int numpoints = 5;
  318.  
  319.         KD2DTree kdt = new KD2DTree(numpoints);
  320.         double x[] = new double[2];
  321.  
  322.         x[0] = 0.0;
  323.         x[1] = 0.0;
  324.         kdt.add(x);
  325.  
  326.         x[0] = 3.3;
  327.         x[1] = 1.5;
  328.         kdt.add(x);
  329.  
  330.         x[0] = 4.7;
  331.         x[1] = 11.1;
  332.         kdt.add(x);
  333.  
  334.         x[0] = 5.0;
  335.         x[1] = 12.3;
  336.         kdt.add(x);
  337.  
  338.         x[0] = 5.1;
  339.         x[1] = 1.2;
  340.         kdt.add(x);
  341.  
  342.         System.out.println("Inorder of 2D Kd tree: ");
  343.         kdt.inorder();
  344.  
  345.         System.out.println("\nPreorder of 2D Kd tree: ");
  346.         kdt.preorder();
  347.  
  348.         System.out.println("\nPostorder of 2D Kd tree: ");
  349.         kdt.postorder();
  350.     }
  351. }

Output:

advertisement
$ javac KDTree_TwoD_Data.java
$ java KDTree_TwoD_Data
 
Inorder of 2D Kd tree: 
(0.0, 0.0)  (5.1, 1.2)  (3.3, 1.5)  (4.7, 11.1)  (5.0, 12.3)  
Preorder of 2D Kd tree: 
(0.0, 0.0)  (5.1, 1.2)  (3.3, 1.5)  (4.7, 11.1)  (5.0, 12.3)  
Postorder of 2D Kd tree: 
(5.1, 1.2)  (3.3, 1.5)  (4.7, 11.1)  (5.0, 12.3)  (0.0, 0.0)

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.