An interactive explanation of quadtrees.

April 24, 2014 6:33 PM

An interactive explanation of quadtrees.
Because I was confused by them initially, I wrote an explanation of the concept of quadtrees (including some details about the D3 implementation of them), with some interactive elements that hopefully provide some hands-on stickiness. I tried to shoot for a non-programmer audience in the end.

Works on the latest Chrome, Safari, Firefox, and Mobile Safari.

Role: Developer

posted by ignignokt (13 comments total)

This looks great, and makes think I should look at D3 more deeply.

If you're open to suggestions, on the bottom where you've got the map and the tree side-by-side, the tree seems to auto-zoom and auto-pan on click-events on the map. For me, it makes me lose my sense of location in the tree and would rather it not happen. But it is hard to locate a single node in a big tree so I see how that can help the view locate the node. If you wanted to put more work in to it here's my suggestion: Animate concentric circles shrinking down to the selected node, "targeting" it, and then leave a slightly lightened circle around it, of fixed size in screen units. Probably more work than you want to do; just thought I'd share the idea.

(I also want to see a visualization of how the nearest neighbor algorithm works, with each step taking about second. Maybe that's my project.)
posted by benito.strauss at 7:33 PM on April 29, 2014

This was great, thanks. I'm diving into graphics programming for the first time as part of my new project at work (which includes quadtrees in its implementation), so this 101-level stuff is perfect for me.
posted by mbrubeck at 9:07 PM on April 29, 2014

benito.strauss: I can see that, re: the tree panning losing people. Do you think that if the zoom was more distant while it panned, that it'd be less disorienting? I can try that, and maybe slowing the pan down.

Re: Nearest neighbor: I don't know if you saw this, but it'd be a great place to start. The edge cases (in which the target point is right on the edge of one of the big quads) seem like they'd be terrible, but they're not so bad, really.

There's a ton of D3 resources out there, and there's much of D3 I've never touched, but feel free to ask me whatever if you take that project on!

mbrubeck: Glad to be of help! I've had trouble with graphics stuff in the past, and I think the inspectability/debuggability of SVG has helped make it way easier, as compared to situations in which you're sending a series of bezier curve commands or filling buffers with triangles.
posted by ignignokt at 9:38 PM on April 29, 2014

Yes, I think seeing more of the tree during the pan would help me. Slower, too, but it might bore others.

And the edge case you've described is precisely the case I always wonder about when I see quadtrees. The node's so close to the root I don't know how the algorithm manages to eliminate many branches. I guess I should actually read the damn code.
posted by benito.strauss at 8:49 AM on April 30, 2014

as I was adding 100 pts, and 100 pts more, it became clear that the depth of the tree wasn't growing, making the usage of the trees pretty clear -- very cool. I too have complaints about the tree zooming to the far right point after it's been rebuilt though, I'd prefer to keep the global view of the tree.
posted by garlic at 5:46 PM on May 1, 2014

benito strauss, I updated it to zoom out and pause for a bit before focusing in on the selected node. Does that work any better for you?

Thanks, garlic. The zooming to the far right point behavior is the result of it trying to show the last-added point, but now that you bring it up, that's not that meaningful of a thing to show. So, maybe I'll go for a zoom-out on those events as well.
posted by ignignokt at 6:32 AM on May 2, 2014

The zooming in seems to go to the wrong location now in Firefox 30.0a2 on Linux. It works correctly in Chromium.
posted by mbrubeck at 12:21 PM on May 2, 2014

Thanks for the bug report! I just updated it so that it works in Firefox on Mac and probably works on Linux Firefox. (Let me know if that's not true.) Panning is still choppy (might not be much I can do about that), but it ends up focusing on the correct node.

It also shows all of the quads in the map now on Firefox – I just noticed it was cutting them off.
posted by ignignokt at 7:10 AM on May 5, 2014 [1 favorite]

FYI, it's been posted to reddit, where it made the front page of /r/programming.
posted by benito.strauss at 9:51 PM on May 14, 2014

Oh, neat! Thanks for posting it, if you did.
posted by ignignokt at 5:44 AM on May 15, 2014

I can't take the credit — I didn't post it. I just read the /r/programming front page and recognized the domain. I wonder how the person who did post it ("darth_flammable") did find it.

And I'm not even sure being posted there is a something you'd want. The first comment starts "the explanation as to why a quadtree has 4 children is crap". Oh Reddit.
posted by benito.strauss at 10:08 AM on May 15, 2014 [1 favorite]

And now I see quadtrees everywhere. Here's a fun use of them to render an image by successively quad-splitting the subsquare with the greatest color-variation. I think it illustrates pretty well how they give detail only where it's needed.
posted by benito.strauss at 9:32 PM on May 19, 2014 [1 favorite]

That is beautiful! Yeah, "detail only where needed" is a good way to think about it.

On a less artistic note, I recently came across this collision detection example which drove home how lightweight they can be. In it, a new quadtree is built and walked on every single tick in the force simulation layout. On one hand, it's only a 200-node tree, but on the other, the tick happens nearly 60 times per second.
posted by ignignokt at 10:38 PM on May 19, 2014