This is a Java Program to implement 2D 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 Perform Searching in a 2-Dimension K-D Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a java program to search an element in a 2D KD Tree import java.io.IOException; import java.util.Scanner; class KD2DNode { int axis; double[] x; int id; boolean checked; boolean orientation; KD2DNode Parent; KD2DNode Left; KD2DNode Right; public KD2DNode(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 KD2DNode FindParent(double[] x0) { KD2DNode parent = null; KD2DNode 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 KD2DNode Insert(double[] p) { x = new double[2]; KD2DNode parent = FindParent(p); if (equal(p, parent.x, 2) == true) return null; KD2DNode newNode = new KD2DNode(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 KD2DTree { KD2DNode Root; int TimeStart, TimeFinish; int CounterFreq; double d_min; KD2DNode nearest_neighbour; int KD_id; int nList; KD2DNode CheckedNodes[]; int checked_nodes; KD2DNode List[]; double x_min[], x_max[]; boolean max_boundary[], min_boundary[]; int n_boundary; public KD2DTree(int i) { Root = null; KD_id = 1; nList = 0; List = new KD2DNode[i]; CheckedNodes = new KD2DNode[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 KD2DNode(x, 0); Root.id = KD_id++; List[nList++] = Root; } else { KD2DNode pNode; if ((pNode = Root.Insert(x)) != null) { pNode.id = KD_id++; List[nList++] = pNode; } } return true; } public KD2DNode find_nearest(double[] x) { if (Root == null) return null; checked_nodes = 0; KD2DNode 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(KD2DNode 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(KD2DNode 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 KD2DNode search_parent(KD2DNode 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; KD2DNode 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 void inorder() { inorder(Root); } private void inorder(KD2DNode root) { if (root != null) { inorder(root.Left); System.out.print("(" + root.x[0] + ", " + root.x[1] + ") "); inorder(root.Right); } } public void preorder() { preorder(Root); } private void preorder(KD2DNode root) { if (root != null) { System.out.print("(" + root.x[0] + ", " + root.x[1] + ") "); inorder(root.Left); inorder(root.Right); } } public void postorder() { postorder(Root); } private void postorder(KD2DNode root) { if (root != null) { inorder(root.Left); inorder(root.Right); System.out.print("(" + root.x[0] + ", " + root.x[1] + ") "); } } public void search(double x, double y) { search(Root, x, y); } private void search(KD2DNode root, double x, double y) { if (root != null) { search(root.Left, x, y); if (x == root.x[0] && y == root.x[1]) System.out.print("True (" + root.x[0] + ", " + root.x[1] + ") "); search(root.Right, x, y); } } } public class KD2D_Search { public static void main(String args[]) throws IOException { int numpoints = 5; Scanner sc = new Scanner(System.in); KD2DTree kdt = new KD2DTree(numpoints); double x[] = new double[2]; x[0] = 0.0; x[1] = 0.0; kdt.add(x); x[0] = 3.3; x[1] = 1.5; kdt.add(x); x[0] = 4.7; x[1] = 11.1; kdt.add(x); x[0] = 5.0; x[1] = 12.3; kdt.add(x); x[0] = 5.1; x[1] = 1.2; kdt.add(x); System.out.println("Enter the co-ordinates of the point: <x> <y>"); double x1 = sc.nextDouble(); double y1 = sc.nextDouble(); kdt.search(x1, y1); System.out.println("\nInorder of 2D Kd tree: "); kdt.inorder(); System.out.println("\nPreorder of 2D Kd tree: "); kdt.preorder(); System.out.println("\npostorder of 2D Kd tree: "); kdt.postorder(); sc.close(); } }
Output:
$ javac KD2D_Search.java $ java KD2D_Search Enter the co-ordinates of the point: <x> <y> 5.1 1.2 True (5.1, 1.2) 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)
Related posts:
Send an email using the SMTP protocol
Feign – Tạo ứng dụng Java RESTful Client
OAuth2 Remember Me with Refresh Token
Introduction to Spring Data JPA
Toán tử instanceof trong java
Exception Handling in Java
Logout in an OAuth Secured Application
Java Program to Implement Max-Flow Min-Cut Theorem
Form Validation with AngularJS and Spring MVC
Concurrent Test Execution in Spring 5
Creating a Custom Starter with Spring Boot
Java TreeMap vs HashMap
New in Spring Security OAuth2 – Verify Claims
Immutable ArrayList in Java
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Java Program to implement Sparse Vector
Java Program to Implement the RSA Algorithm
Spring Security Custom AuthenticationFailureHandler
Spring Boot - Admin Client
Java Program to Implement Pairing Heap
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Debugging Reactive Streams in Java
Converting String to Stream of chars
Spring Security – security none, filters none, access permitAll
Spring Cloud – Bootstrapping
Function trong Java 8
Hướng dẫn Java Design Pattern – Iterator
A Custom Data Binder in Spring MVC
Copy a List to Another List in Java
Giới thiệu SOAP UI và thực hiện test Web Service
Convert Character Array to String in Java
How to Get the Last Element of a Stream in Java?