Art›Quadtree

QuadTree

This project is powered by p5.js and originates from this QuadTree tutorial with details extracted from the QuadTree Wikipedia entry.

Live example here

Preview of QuadTree

index.html

<!doctype html>
<html>
<head>
	<meta charset="utf-8" />
	<meta http-equiv="X-UA-Compatible" content="IE=edge" />
	<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" />
	
	<title>p5.js - QuadTree</title>
	
	<script src="lib/p5.min.js"></script>
	<!-- <script src="lib/p5.dom.min.js"></script> -->
	<!-- <script src="lib/p5.sound.min.js"></script> -->
	
	<script src="point.js"></script>
	<script src="rectangle.js"></script>
	<script src="quadtree.js"></script>
	
	<script src="sketch.js"></script>
</head>
<body>
	
</body>
</html>

point.js

	
	class Point {
		constructor(x, y) {
			this.x = x;
			this.y = y;
		}
		
		
	}

quadtree.js

	
	class QuadTree {
		constructor(boundary, n) {
			this.boundary = boundary;
			this.capacity = n;
			this.points = [];
			this.divided = false;
		}
		
		subdivide() {
			if(this.divided) {
				return;
			}
			
			// nw
			let nw = new Rectangle(
				(this.boundary.x - (this.boundary.w / 2)),
				(this.boundary.y - (this.boundary.h / 2)),
				(this.boundary.w / 2),
				(this.boundary.h / 2)
			);
			this.northwest = new QuadTree(nw, this.capacity);
			
			// ne
			let ne = new Rectangle(
				(this.boundary.x + (this.boundary.w / 2)),
				(this.boundary.y - (this.boundary.h / 2)),
				(this.boundary.w / 2),
				(this.boundary.h / 2)
			);
			this.northeast = new QuadTree(ne, this.capacity);
			
			// sw
			let sw = new Rectangle(
				(this.boundary.x - (this.boundary.w / 2)),
				(this.boundary.y + (this.boundary.h / 2)),
				(this.boundary.w / 2),
				(this.boundary.h / 2)
			);
			this.southwest = new QuadTree(sw, this.capacity);
			
			// se
			let se = new Rectangle(
				(this.boundary.x + (this.boundary.w / 2)),
				(this.boundary.y + (this.boundary.h / 2)),
				(this.boundary.w / 2),
				(this.boundary.h / 2)
			);
			this.southeast = new QuadTree(se, this.capacity);
			
			// prevent further dividing
			this.divided = true;
		}
		
		insert(point) {
			if(!this.boundary.contains(point)) {
				return;
			}
			
			if(this.points.length < this.capacity) {
				this.points.push(point);
			} else {
				this.subdivide();
				
				this.northwest.insert(point);
				this.northeast.insert(point);
				this.southwest.insert(point);
				this.southeast.insert(point);
			}
		}
		
		query(range, found) {
			if(!found) {
				found = [];
			}
			
			if(!this.boundary.insersects(range)) {
				return found;
			}
			
			for(let p of this.points) {
				if(range.contains(p)) {
					found.push(p);
				}
			}
			
			if(this.divided) {
				this.northwest.query(range, found);
				this.northeast.query(range, found);
				this.southwest.query(range, found);
				this.southeast.query(range, found);
			}
			
			return found;
		}
		
		show() {
			stroke(255);
			strokeWeight(1);
			noFill();
			rectMode(CENTER);
			rect(this.boundary.x, this.boundary.y, (this.boundary.w * 2), (this.boundary.h * 2));
			
			if(this.divided) {
				this.northwest.show();
				this.northeast.show();
				this.southwest.show();
				this.southeast.show();
			}
			
			for(let p of this.points) {
				strokeWeight(3);
				point(p.x, p.y);
			}
		}
	}

rectangle.js

	
	class Rectangle {
		constructor(x, y, w, h) {
			this.x = x;
			this.y = y;
			this.w = w;
			this.h = h;
		}
		
		contains(point) {
			return (
				   (point.x >= (this.x - this.w))
				&& (point.x <  (this.x + this.w))
				&& (point.y >= (this.y - this.h))
				&& (point.y <  (this.y + this.h))
			);
		}
		
		insersects(range) {
			return !(
				   range.x - range.w > this.x + this.w
				|| range.x + range.w < this.x - this.w
				|| range.y - range.h > this.y + this.h
				|| range.y + range.h < this.y - this.h
			);
		}
	}

sketch.js

	
	let qtree;
	
	function setup() {
		createCanvas(600, 600);
		
		let boundary = new Rectangle(300, 300, 300, 300);
		qtree = new QuadTree(boundary, 4);
		
		for(let i = 0; i < 500; i++) {
			//let p = new Point(random), random(height));
			let x = randomGaussian(width/2, width/8);
			let y = randomGaussian(height/2, height/8);
			let p = new Point(x, y);
			
			qtree.insert(p);
		}
	}
	
	function draw() {
		if(mouseIsPressed) {
			let p = new Point(mouseX, mouseY);
			qtree.insert(p);
		}
		
		background(0);
		
		qtree.show();
		
		stroke(0, 255, 0);
		strokeWeight(1);
		rectMode(CENTER);
		
		let range = new Rectangle(mouseX, mouseY, 75, 64);
		
		let points = qtree.query(range);
		
		stroke(200, 0, 0);
		strokeWeight(1);
		text("Found: "+ points.length, (range.x + 3 - range.w), (range.y - 10 - range.h));
		
		stroke(0, 255, 0);
		strokeWeight(1);
		fill(color(0, 255, 0, 30));
		rect(range.x, range.y, (range.w * 2), (range.h * 2));
		
		stroke(0, 255, 0);
		strokeWeight(3);
		
		for(let p of points) {
			point(p.x, p.y);
		}
	}