Two-dimensional recursive spatial subdivision.

d3-quadtree

Not that this has any real performance consequences, but I'm trying to figure out how the outlier in the top-left of this screen-shot came about:

https://i.imgur.com/0eTPQUP.png

Like, wouldn't the algorithm as implemented have completely avoided visiting that note?

Job van der Zwan

It's easy to get the wrong intuition—when we drill down the hierarchy, nodes are eliminated with the L1 distance; it's only leaf nodes that are evaluated with L2. This outlier is a leaf in a rather large quad.

I was exploring a rudimentary regular square grid approach to the same problem, and wanted to compare it to a quadtree approach. This notebook was exactly what I was looking for. Thanks! Here's my square grid approach, for comparison: https://observablehq.com/@mast4461/point-neighborhood-lookup-grid