This is an implementation of the Quadtree datastructure. This implementation is solely dependent on JavaScript and p5.js is only used for visualization purposes.
A quadtree has two main objectives:
Firstly, a quadtree needs to be able to insert data and if neccessary subdivide and create child nodes
A quadtree is similar to a binary tree in the sense that it consists of a root note which could extend into child nodes. The only difference is that a quadtree has four of these child nodes instead of two.
Each node stores some data with a capacity/limit to the amount/size of the data as well as a bounding position which its data subsides in. Once the node exceeds its data capacity it branches out and creates four new child nodes.
The boundary is represened as the green border and its data is represented by the green data points.
Once the amount af data exceeds its capacity (in this case capacity = 4) the root node (blue) branches out into four child nodes which then store the remaining data (orange). Which child node stores the data depends on if the data is within the child nodes boundary.
This process repeats indefinitely until all the data points have been stored.
Once the neccessary data has been successfully stored into the quadtree we need to be able to access that data.
Lets say we have a set of 100 points and we have stored these points in a quadtree with its capacity at 4 points per node.
We would like to access all the data points in some area.
Traditionally we would iterate through the entire data set and check if it is within the specified range which wouldn't be that expensive since we are only checking each point once and so it would run in O(n); however, if we choose to modify each point depending on other points then this becomes exponentially expensive because we would have to check each point against every other point n times.
Instead of using the traditional method we rather start at the root node and check if the range overlaps it (aka: the range area is within the bounds of the nodes designated area). If they do overlap then we check if any of its data points are within the range, we then add these 'points in range' into a list. If the node has child nodes then we recursevely do the same for all its children. At the end we will have a list of points which are within the range.
Here the points in that list are red:
[1] Wikipedia Contributors. (2023, April 10). Quadtree. Wikipedia; Wikimedia Foundation. link
[2] The Coding Train. (2018). Coding Challenge #98.1: Quadtree - Part 1 YouTube Video
[3] The Coding Train. (2018). Coding Challenge #98.2: Quadtree - Part 2 YouTube Video
[4] Scott, T. (2018). Quadtrees and Octrees for Representing Spatial Information YouTube Video