Question

Create a kD tree with:

x-nodes and y-nodes -- and maintain the following two properties:

• The children of an x-node are y-nodes
• The children of a y-node are x-nodes

Each type of node uses a different comparison to order points. This causes different levels of the tree to compare points differently, using the following rules:

• For every x-node:
  • All descendants in the left subtree have a smaller x-coordinate than the point stored at the node. Visually, all descendant points are left of this point.
  • All descendants in the right subtree have a larger x-coordinate than the points stored at the node. Visually, all descendant points are right of this point.
• For every y-node:
  • All descendants in the left subtree have a smaller y-coordinate than the point stored at the node. Visually, all descendant points are below this point.
  • All descendants in the right subtree have a larger y-coordinate than the point stored at the node. Visually, all descendant points are above this point.

Create a draw method:

• void draw()
  • Draws the spatial tree (you may use StdDraw). Each node should show the point, and the regions bounding each point (see below). (Hint: use recursion.)

Please implement in Java.

Answer 1

K-D Tree also called as K-Dimensional Tree, is a binary search tree where data in each node is a K-Dimensional point in space. It is used for various applications like nearest point in k-dimensional space, efficient storage of spatial data, range search etc. A non-leaf node in K-D tree divides the space into two parts, called as half-spaces. The left child of the node represents the left half while right child represents right half. The space is divided into 2 halves irrespective of the number of dimensions. To be more accurate, every internal node represents a hyperplane that cuts the space in 2 parts. The root would have an x-aligned plane, the root’s children would both have y-aligned planes, the root’s grandchildren would all have x-aligned planes, and the root’s great-grandchildren would all have y-aligned planes and so on.

Insert(x, y): Every insert operation divides the space. The algorithm here considers space to be 2-dimensional but is applicable in all dimensions:

Search the tree for (x, y) until a leaf node is reached.
If the tree is empty, add a new node as root representing the point (x, y). Here, the space can be divided along any axis. Indicate the axis along which the space is divided and end insertion.
Insert a new node where the point (x, y) should have existed and have it store (x, y). If the parent divided the space along x-axis, have the point divide the space along y-axis, otherwise have it divide space along x-axis.
Consider following points in a 2-D plane:
(3, 6), (17, 15), (13, 15), (6, 12), (9, 1), (2, 7), (10, 19)

Insert (3, 6): Since tree is empty, make it the root node.
Insert (17, 15): Compare it with root node point. Since root node is X-aligned, the X-coordinate value will be compared to determine if it lies in the rightsubtree or in the right subtree. This point will be Y-aligned.
Insert (13, 15): X-value of this point is greater than X-value of point in root node. So, this will lie in the right subtree of (3, 6). Again Compare Y-value of this point with the Y-value of point (17, 15) (Why?). Since, they are equal, this point will lie in the right subtree of (17, 15). This point will be X-aligned.
Insert (6, 12): X-value of this point is greater than X-value of point in root node. So, this will lie in the right subtree of (3, 6). Again Compare Y-value of this point with the Y-value of point (17, 15) (Why?). Since, 12 < 15, this point will lie in the left subtree of (17, 15). This point will be X-aligned.
Insert (9, 1):Similarly, this point will lie in the right of (6, 12).
Insert (2, 7):Similarly, this point will lie in the left of (3, 6).
Insert (10, 19): Similarly, this point will lie in the left of (13, 15).
Search(x, y): This function checks if the point exists in space. Start with root node as current node.

If the current node represents the point (x, y), return true.
If current node is not a leaf node, goto step 3, otherwise return false.
Let current node be the point (X, Y). If the node divides space along x-axis, compare x with X. If x < X, set current node as left child, otherwise set current node as right child. If the node divided the space along y-axis, compare y and Y.
Goto step 1.
Point2D class is a part of JavaFX. This class defines a 2-dimensional point in space. The Point2D class represents a 2D point by its x, y coordinates. It inherits java.lang.Object class. Constructor of the class is Point2D(double x, double y): Create a point2D object with specified x and y coordinates. Most common methods of Point2D class are:

distance(double x1, double y1) - Calculates the distance between this point and point (x1, y1)
equals(java.lang.Object obj) - Returns whether this object is equal to the specified object or not
getX() - Returns the x coordinate of the point
getY() - Returns the y coordinate of the point
Here is a program

kd-trees :

Each level has a cutting dimension
Cycle through the dimensions as you walk down the tree.
Each node contains a point P = (x,y)
To find (x',y') only compare coordinate from the cutting dimension, if cutting dimension is x, then ask: is x’ < x ?
Insert Code :

insert(Point x, KDNode t, int cd)
{
if t == null
t = new KDNode(x)
else if (x == t.data)
// error! duplicate
else if (x[cd] < t.data[cd])
t.left = insert(x, t.left, (cd+1) % DIM)
else
t.right = insert(x, t.right, (cd+1) % DIM)
return t
}

Java Program for you :

class KDNode
{
KDNode left;
KDNode right;
int []data;
public KDNode()
{
left=null;
right=null;
}
public KDNode(int []x)
{
left=null;
right=null;
data = new int[2];
for (int k = 0; k < 2; k++)
data[k]=x[k];
}
}
class SpatialTree
{
KDNode root;
int cd=0;
int DIM=2;
public SpatialTree()
{
root=null;
}
public boolean isEmpty()
{
return root == null;
}
public void insert(int []x)
{
root = insert(x,root,cd);
}
private KDNode insert(int []x,KDNode t,int cd)
{
if (t == null)
t = new KDNode(x);
else if (x[cd] < t.data[cd])
t.left = insert(x, t.left, (cd+1)%DIM);
else
t.right = insert(x, t.right, (cd+1)%DIM);
return t;
}
public boolean search(int []data)
{
return search(data,root,0);
}
private boolean search(int []x,KDNode t,int cd)
{
boolean found=false;
if(t==null){
return false;
}
else
{
if(x[cd]==t.data[cd])
{
if(x[0]==t.data[0] && x[1]==t.data[1])
return true;
}
else if(x[cd]<t.data[cd])
{
found = search(x,t.left,(cd+1)%DIM);
}
else if(x[cd]>t.data[cd])
{
found = search(x,t.right,(cd+1)%DIM);
}
return found;
}
}
public void inorder()
{
inorder(root);
}
private void inorder(KDNode r)
{
if (r != null)
{
inorder(r.left);
System.out.print("("+r.data[0]+","+r.data[1] +") ");
inorder(r.right);
}
}
public void preorder()
{
preorder(root);
}
private void preorder(KDNode r)
{
if (r != null)
{
System.out.print("("+r.data[0]+","+r.data[1] +") ");
preorder(r.left);
preorder(r.right);
}
}
/ Function for postorder traversal /
public void postorder()
{
postorder(root);
}
private void postorder(KDNode r)
{
if (r != null)
{
postorder(r.left);
postorder(r.right);
System.out.print("("+r.data[0]+","+r.data[1] +") ");
}
}
}
public class SpatialTreeNode
{
public static void main(String[] args)
{
SpatialTree stn = new SpatialTree();
int x[] = new int[2];
x[0] = 30;
x[1] = 40;
stn.insert(x);
x[0] = 5;
x[1] = 25;
stn.insert(x);
x[0] = 10;
x[1] = 12;
stn.insert(x);
x[0] = 70;
x[1] = 70;
stn.insert(x);
x[0] = 50;
x[1] = 30;
stn.insert(x);
System.out.println("Input Elements");
System.out.println("(30,40) (5,25) (10,12) (70,70) (50,30)\n\n");
System.out.println("Printing KD Tree in Inorder");
stn.inorder();
System.out.println("\nPrinting KD Tree in PreOder");
stn.preorder();
System.out.println("\nPrinting KD Tree in PostOrder");
stn.postorder();
System.out.println("\nsearching...............");
x[0]=40;x[1]=40;
System.out.OUTprintln(stn.search(x));
}
}

OUTPUT