An interactive intro to quadtrees
Suppose you're building a map application. You have millions of restaurants, gas stations, and landmarks, each with a latitude and longitude. A user taps the screen and asks: "What's near me?"
The simplest approach is to check every single point. Compute the distance from the user's location to every restaurant in the database, keep the ones that are close enough, and throw away the rest.
This works, but it's slow.
With a thousand points, you barely notice the delay. With a million, you're doing a million distance calculations for every single query. On a phone updating the map as the user scrolls, that's untenable.
Drag out a search region below and watch the brute-force approach check every point, one by one:
Scroll to load interactive demo
Every point gets examined, regardless of where it sits. Points on the opposite side of the map get the same treatment as points right next to the query region. We're doing a lot of unnecessary work.
We have no way to skip over points that are obviously too far away. What if we could organize the space itself so that when we search, we can immediately rule out entire regions?
Dividing space
... continue reading