Quad Tree
13 Oct 2020
A quadtree is a tree data structure in which each internal node has exactly four children. Originally within databases for storing data in an easily searchable manner, it can also be used to find pixels in a 2D plane. Here's a demonstration of just that.

In the canvas(right) below we have a bunch of points (colored Black) randomly scattered across. A quadtree is built in such a manner that each point is assigned at least one block of the quadtree. The quadtree's search functionality makes it easier to find the point closest (colored Red) to the mouse (colored Blue).

Quadtree searches are O(log n) searches as opposed to brute force searches that are O(n). There are two canvas below. The left one is a brute force search. The right one is QuadTree.


1. quadtreecanvas.js - Download, index.html 
//Code goes here
2. quadtree.js - Download, index.html 
//Code goes here

Javascript Demos ▼

Here's a bunch of javascript... things I wrote over the years whenever time permitted.