Quadtree

The quadtree post serves two purposes: to learn JavaScript in order to make interactive code run on the site, and to gain more experience with tree structures. I had been playing around with binary trees and graphs, and wanted to implement a visual representation of a tree structure. The quadtree idea and implementation may be seen by many sources (Wiki has decent pseudocode). In complete analogy to a binary tree, a quadtree may be recursively built but now 4 children nodes are possible. Of importance to me, though, is that the structure allows for a rapid search or query of neighboring balls, which is useful in the context of 2D collisions for example. The naive algorithm to search for nearest neighbors is O(N²), i.e. for each ball, one must check the position of every other ball which is a double for-loop algorithm (with some minor optimizations that are possible). The quadtree may be used in order to return a sub-list of balls that are in the vicinity of the ball in question; the result may then be used for collision detection, which is a significant improvement relative to the naive approach for many balls. There are other approaches to solve this problem more efficiently, and I am not claiming that the use of a quadtree is the best. Note that I did not implement a collision routine as I’ve already worked this out in a previous post.