Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees

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

Output:

$ javac KD3D_Search.java
$ java KD3D_Search
 
Enter the co-ordinates of the point: <x> <y> <z>
5.1 1.2 4.2 
True (5.1, 1.2, 4.2)  
Inorder of 2D Kd tree: 
(0.0, 0.0, 0.0)  (5.1, 1.2, 4.2)  (3.3, 1.5, 4.0)  (4.7, 11.1, 2.3)  (5.0, 12.3, 5.7)  
Preorder of 2D Kd tree: 
(0.0, 0.0, 0.0)  (5.1, 1.2, 4.2)  (3.3, 1.5, 4.0)  (4.7, 11.1, 2.3)  (5.0, 12.3, 5.7)  
postorder of 2D Kd tree: 
(5.1, 1.2, 4.2)  (3.3, 1.5, 4.0)  (4.7, 11.1, 2.3)  (5.0, 12.3, 5.7)  (0.0, 0.0, 0.0)  
 
Enter the co-ordinates of the point: <x> <y> <z>
5.1 5.2 5.3
False
Inorder of 2D Kd tree: 
(0.0, 0.0, 0.0)  (5.1, 1.2, 4.2)  (3.3, 1.5, 4.0)  (4.7, 11.1, 2.3)  (5.0, 12.3, 5.7)  
Preorder of 2D Kd tree: 
(0.0, 0.0, 0.0)  (5.1, 1.2, 4.2)  (3.3, 1.5, 4.0)  (4.7, 11.1, 2.3)  (5.0, 12.3, 5.7)  
postorder of 2D Kd tree: 
(5.1, 1.2, 4.2)  (3.3, 1.5, 4.0)  (4.7, 11.1, 2.3)  (5.0, 12.3, 5.7)  (0.0, 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 & discussions at Telegram SanfoundryClasses.