AbhijeetMajumdar · April 1, 2025 03:53 · Jul 1, 2015 · Jul 1, 2015 · Jul 1, 2015 · Jul 1, 2015
diff --git a/quadtree → quadtree.java b/quadtree → quadtree.java
diff --git a/quadtree → quadtree b/quadtree → quadtree
diff --git a/gistfile1.java → quadtree b/gistfile1.java → quadtree
@@ -1,5 +1,12 @@
+A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to
+partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or 
+rectangular, or may have arbitrary shapes. 
+
+More on 
 https://en.wikipedia.org/wiki/Quadtree
 
+Thanks to Jim for such an excellent visual representation on http://jimkang.com/quadtreevis/
+
 
 import java.util.ArrayList;
 import java.util.List;

diff --git a/gistfile1.java b/gistfile1.java
@@ -0,0 +1,200 @@
+https://en.wikipedia.org/wiki/Quadtree
+
+
+import java.util.ArrayList;
+import java.util.List;
+
+/*
+ *  			N
+ *  		W		E
+ *  			S
+ */
+
+class Node {
+	int x, y, value;
+
+	Node(int x, int y, int value) {
+		this.x = x;
+		this.y = y;
+		this.value = value; /* some data*/ 
+	}
+}
+/* Using two points of Rectangular (Top,Left) & (Bottom , Right)*/
+class Boundry {
+	public int getxMin() {
+		return xMin;
+	}
+
+	public int getyMin() {
+		return yMin;
+	}
+
+	public int getxMax() {
+		return xMax;
+	}
+
+	public int getyMax() {
+		return yMax;
+	}
+
+	public Boundry(int xMin, int yMin, int xMax, int yMax) {
+		super();
+		/*
+		 *  Storing two diagonal points 
+		 */
+		this.xMin = xMin;
+		this.yMin = yMin;
+		this.xMax = xMax;
+		this.yMax = yMax;
+	}
+
+	public boolean inRange(int x, int y) {
+		return (x >= this.getxMin() && x <= this.getxMax()
+				&& y >= this.getyMin() && y <= this.getyMax());
+	}
+
+	int xMin, yMin, xMax, yMax;
+
+}
+
+public class QuadTree {
+	final int MAX_CAPACITY =4;
+	int level = 0;
+	List<Node> nodes;
+	QuadTree northWest = null;
+	QuadTree northEast = null;
+	QuadTree southWest = null;
+	QuadTree southEast = null;
+	Boundry boundry;
+
+	QuadTree(int level, Boundry boundry) {
+		this.level = level;
+		nodes = new ArrayList<Node>();
+		this.boundry = boundry;
+	}
+
+	/* Traveling the Graph using Depth First Search*/
+	static void dfs(QuadTree tree) {
+		if (tree == null)
+			return;
+
+		System.out.printf("\nLevel = %d [X1=%d Y1=%d] \t[X2=%d Y2=%d] ",
+				tree.level, tree.boundry.getxMin(), tree.boundry.getyMin(),
+				tree.boundry.getxMax(), tree.boundry.getyMax());
+
+		for (Node node : tree.nodes) {
+			System.out.printf(" \n\t  x=%d y=%d", node.x, node.y);
+		}
+		if (tree.nodes.size() == 0) {
+			System.out.printf(" \n\t  Leaf Node.");
+		}
+		dfs(tree.northWest);
+		dfs(tree.northEast);
+		dfs(tree.southWest);
+		dfs(tree.southEast);
+
+	}
+
+	void split() {
+		int xOffset = this.boundry.getxMin()
+				+ (this.boundry.getxMax() - this.boundry.getxMin()) / 2;
+		int yOffset = this.boundry.getyMin()
+				+ (this.boundry.getyMax() - this.boundry.getyMin()) / 2;
+
+		northWest = new QuadTree(this.level + 1, new Boundry(
+				this.boundry.getxMin(), this.boundry.getyMin(), xOffset,
+				yOffset));
+		northEast = new QuadTree(this.level + 1, new Boundry(xOffset,
+				this.boundry.getyMin(), xOffset, yOffset));
+		southWest = new QuadTree(this.level + 1, new Boundry(
+				this.boundry.getxMin(), xOffset, xOffset,
+				this.boundry.getyMax()));
+		southEast = new QuadTree(this.level + 1, new Boundry(xOffset, yOffset,
+				this.boundry.getxMax(), this.boundry.getyMax()));
+
+	}
+
+	void insert(int x, int y, int value) {
+		if (!this.boundry.inRange(x, y)) {
+			return;
+		}
+
+		Node node = new Node(x, y, value);
+		if (nodes.size() < MAX_CAPACITY) {
+			nodes.add(node);
+			return;
+		}
+		// Exceeded the capacity so split it in FOUR
+		if (northWest == null) {
+			split();
+		}
+
+		// Check coordinates belongs to which partition 
+		if (this.northWest.boundry.inRange(x, y))
+			this.northWest.insert(x, y, value);
+		else if (this.northEast.boundry.inRange(x, y))
+			this.northEast.insert(x, y, value);
+		else if (this.southWest.boundry.inRange(x, y))
+			this.southWest.insert(x, y, value);
+		else if (this.southEast.boundry.inRange(x, y))
+			this.southEast.insert(x, y, value);
+		else
+			System.out.printf("ERROR : Unhandled partition %d %d", x, y);
+	}
+
+	public static void main(String args[]) {
+		QuadTree anySpace = new QuadTree(1, new Boundry(0, 0, 1000, 1000));
+		anySpace.insert(100, 100, 1);
+		anySpace.insert(500, 500, 1);
+		anySpace.insert(600, 600, 1);
+		anySpace.insert(700, 600, 1);
+		anySpace.insert(800, 600, 1);
+		anySpace.insert(900, 600, 1);
+		anySpace.insert(510, 610, 1);
+		anySpace.insert(520, 620, 1);
+		anySpace.insert(530, 630, 1);
+		anySpace.insert(540, 640, 1);
+		anySpace.insert(550, 650, 1);
+		anySpace.insert(555, 655, 1);
+		anySpace.insert(560, 660, 1);
+		//Traveling the graph
+		QuadTree.dfs(anySpace);
+	}
+}
+Output
+
+Level = 1 [X1=0 Y1=0] 	[X2=1000 Y2=1000]  
+	  x=100 y=100 
+	  x=500 y=500 
+	  x=600 y=600 
+	  x=700 y=600
+Level = 2 [X1=0 Y1=0] 	[X2=500 Y2=500]  
+	  Leaf Node.
+Level = 2 [X1=500 Y1=0] 	[X2=500 Y2=500]  
+	  Leaf Node.
+Level = 2 [X1=0 Y1=500] 	[X2=500 Y2=1000]  
+	  Leaf Node.
+Level = 2 [X1=500 Y1=500] 	[X2=1000 Y2=1000]  
+	  x=800 y=600 
+	  x=900 y=600 
+	  x=510 y=610 
+	  x=520 y=620
+Level = 3 [X1=500 Y1=500] 	[X2=750 Y2=750]  
+	  x=530 y=630 
+	  x=540 y=640 
+	  x=550 y=650 
+	  x=555 y=655
+Level = 4 [X1=500 Y1=500] 	[X2=625 Y2=625]  
+	  Leaf Node.
+Level = 4 [X1=625 Y1=500] 	[X2=625 Y2=625]  
+	  Leaf Node.
+Level = 4 [X1=500 Y1=625] 	[X2=625 Y2=750]  
+	  x=560 y=660
+Level = 4 [X1=625 Y1=625] 	[X2=750 Y2=750]  
+	  Leaf Node.
+Level = 3 [X1=750 Y1=500] 	[X2=750 Y2=750]  
+	  Leaf Node.
+Level = 3 [X1=500 Y1=750] 	[X2=750 Y2=1000]  
+	  Leaf Node.
+Level = 3 [X1=750 Y1=750] 	[X2=1000 Y2=1000]  
+	  Leaf Node.
No results found