ELI5: What is a QuadTree?
Imagine you have a HUGE area (like a whole city) and you need to find points in it. Looking through every single point would be SO slow!
TL;DR: A QuadTree is like dividing a pizza into 4 equal slices, then cutting each slice into 4 more, and keeping going! When you want to find something, you only look in the slice where it might be.
🍕 The Pizza Example
Let's say you have a map and want to find all the restaurants in New York City:
- Start with the WHOLE map
- Divide it into 4 quadrants (north, south, east, west)
- If one quadrant has too many restaurants, divide IT into 4 more pieces!
- Keep going until each piece has only a few restaurants
- Now finding a restaurant is super fast - just pick the right quadrant!
⏱️ Why Is It Fast?
Without QuadTree: Checking 1 million points = 1 million checks 😩
With QuadTree: Same 1 million points = only ~20 checks! 🚀
It's called "logarithmic time" - which means even if you have 100x more points, you only need a few more checks!