a bit of ds: QuadTree (and Implementation)

A few days ago I made a little implementation on QuadTree on my (still very green) github io page, here is a link: QuadTree Demo

What is cool about this data structure is that like binary tree, it is recursive in nature, so you can write very little code and achieve a highly complex work. I think it is widely use in game programming for collision detections between objects, especially when the number of objects are pretty huge where \(O(N^2)\) check won't cut it.

QuadTree is conceptually very simple. Suppose we have a "quadrant". We will further split this quadrant into four equal parts if and only if there is at least two elements inside this current quadrant. Then we recursively do the same on the four resulting parts. That's it!

For collision detection application, you can determine beforehand how deep is the recursion or how big is the area for which a collision can occur.