This is an implementation of the QuadTree data structure based on a video made by Daniel Shiffman, a.k.a., The Coding Train. QuadTrees have a myriad of applications, including image processing, collision detection, and even simulation Conway's game of life. I'm hoping to explore most of these at some point within this repository.
- numpy
- matplotlib
A friend of mine generated an algorithm for determining the two closest schools in VT in O(nlogn) using Java (which can be found here). Since a QuadTree is well-suited for two-dimensional spatial data and is capable of operating at O(logn) time for querying the points, I figured I could try and write an algorithm that outperforms his. Whether or not I actually achieve that goal is better left to someone who understands time complexity, but nevertheless this method affords the correct answer (for anyone interested, the answer is, unsurprisingly, People's Academy and People's Academy Middle School). Below is a visualization of the schools with a QuadTree overlayed on the state. Also, the data can be found here.
