Art Quadtree

Readme

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


Project Code

This code is written and rendered using p5.js, a quick and easy graphical sketchbook engine written in JavaScript
class Point {
	constructor(x, y) {
		this.x = x;
		this.y = y;
	}
	
	
}

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);
		}
	}
}

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
		);
	}
}

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);
	}
}

please visit our Contact Us page to get in touch
pyxol © 2021