Optimising many-to-many geo-contains

I have a map with hundreds of tiles, and need group 1000s of points into these tiles.

This is a painfully slow operation, and I’ve tried the following but with no real performance improvements:

  1. Pre-filtering to local points before performing the geo-contains function
  2. Using @Fil 's geoContainsCache so that each tile’s geometry is calculated just once (and not for every tile x point comibation).

Is there anything else I could try? I could materialise the groupings in Python, but it’d be neat to have dynamic tile sizes in Observable.


1 Like


we can take advantage that the grid is very griddy (with the same longitudes and latitudes on each axis), and index it based on the top-right corner of each tile. Then the search for a specific coordinates is just a matter of bisecting these coordinates on x then on y. The following function returns the index of the tile element that contains the point, if any:

findTile = {
  const corners = tiles.features.map((d, i) => [
  const x = d3.sort(d3.group(corners, (d) => +d[0]).keys());
  const y = d3.sort(d3.group(corners, (d) => +d[1]).keys());
  const I = d3.rollup(
    (v) => v[0][2],
    (d) => +d[0],
    (d) => +d[1]
  return ({ Long, Lat }) => {
    const x0 = x[d3.bisect(x, +Long)];
    const y0 = y[d3.bisect(y, +Lat)];
    return I.get(x0)?.get(y0);

Note that, if you filter on the result being undefined, you will see that the grid is not covering the whole dataset:

Notebook: Catches sites / recifs / Observable


Fantastic, thanks! I look forward to exploring this tomorrow.

When I try to make the tile-sizing dynamic, your notebook seizes up:

Why would this be the case?

The tile algorithm itself is reasonably responsive in isolation:


The notebook works well with step: 0.5, but not for step 0.1.

Why would the step size of the parameter impact performance so much?