Optimising many-to-many geo-contains

Community Help
1

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.

Thanks,
Ben

1 Like
2

Hello,

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) => [
    ...d.geometry.coordinates[0][2],
    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(
    corners,
    (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:

Capture d’écran 2022-09-27 à 09.09.21
Capture d’écran 2022-09-27 à 09.09.21556×600 226 KB

Notebook: Catches sites / recifs / Observable

2 Likes
3

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

4

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:

Thanks,
Ben

5

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

6

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