Passing map bounding box to SuperCluster

[leighhalliday]

The SuperCluster algorithm is receiving a static bounding box of [-180, -90, 180, 90]. This is causing performance issues when dealing with larger marker counts or when you are zoomed in with relatively low marker counts (1000). This is because it is trying to render thousands of markers that aren't visible on the screen.

By passing in the map's bounding box, performance increases considerably. During testing I was able to go from struggling with 1000 markers, to no issues at all with 5000.

---

Before submitting your PR, there are a few things you can do to make sure it goes smoothly:

• [x] Make sure to open a GitHub issue as a bug/feature request before writing your code! That way we can discuss the change, evaluate designs, and agree on the general idea
• [x] Ensure the tests and linter pass
• [x] Code coverage does not decrease (if any source code was changed)
• [x] Appropriate docs were updated (if necessary)

Fixes #417 🦕

[google-cla[bot]]

Thanks for your pull request! It looks like this may be your first contribution to a Google open source project. Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

View this failed invocation of the CLA check for more information.

For the most up to date status, view the checks section at the bottom of the pull request.

[leighhalliday]

I found another similar issue... and it seems like this was an explicit choice to use "entire globe" bounding box. So feel free to ignore this PR if using the map bounding box isn't a good idea, but it also seems like this issue wasn't just limited to my experience.

For me, it let me go from having issues rendering 1k markers to 10k without any issues.

Perhaps another approach is to provide a constructor option to switch between map bounding / world bounding? If you'd prefer to go with this approach, I'd be happy to modify this PR.

[luan-dang-techlabs]

Any updates? I am having same issue with sets 13k, there isn't a bound which makes it slow.

[leighhalliday]

Any updates? I am having same issue with sets 13k, there isn't a bound which makes it slow.

Hey! In the meantime, you can extend and add the bounding functionality without too much work:

export default class BoundingSuperClusterAlgorithm extends SuperClusterAlgorithm {
  cluster({ map }) {
    const bounds = map.getBounds().toJSON();
    const boundingBox = [bounds.west, bounds.south, bounds.east, bounds.north];

    return this.superCluster
      .getClusters(boundingBox, Math.round(map.getZoom()))
      .map(this.transformCluster.bind(this));
  }
}

[luan-dang-techlabs]

@leighhalliday - thanks a lot will give it a try.

[bgurung03]

@leighhalliday I think the bounding box change check should be separated out from zoom change check, because when we are at cluster max zoom level, the bounding box changes are ignored. Maybe something like following can be done:

https://github.com/googlemaps/js-markerclusterer/blob/03c56de1ad7ca14b70e633b92ce97597b09e9bbe/src/algorithms/supercluster.ts#L84

if (!changed) {
   if (this.state.zoom > this.maxZoom && state.zoom > this.maxZoom) {
     // still beyond maxZoom, no change
   } else {
     changed = changed || this.state.zoom !== state.zoom;
   }
}

If(!changed && !equal(this.state.boundingBox, state.boundingBox)) {
    changed = true;
}

[amuramoto]

@leighhalliday What about if we allow a bounding box to be passed into the constructor that defaults to world view?

[luan-dang-techlabs]

@leighhalliday - hi , finally got a chance to try your recommendation. can you verify if i am doing this right? Do I need to implement calculator()? If so, what calculate() method do I need?

    class BoundingSuperClusterAlgorithm extends SuperClusterAlgorithm {
          cluster({ map }: any) {
            const bounds: any = map.getBounds().toJSON();
            const boundingBox: any = [bounds.west, bounds.south, bounds.east, bounds.north];
            const transform = this.transformCluster.bind(this);
        
            // @ts-expect-error
            return this.superCluster.getClusters(boundingBox, Math.round(map.getZoom())).map(transform);
          }
}

      const markerCluster = new MarkerClusterer({
        markers,
        map: mapRef.current,
        algorithm: new BoundingSuperClusterAlgorithm()
      });

[davidpadych]

this functionality would be useful to me, what does it look like?

[luan-dang-techlabs]

@davidpadych

      const markerCluster = new MarkerClusterer({
           markers,
          map: mapRef.current,
          algorithm: new BoundingSuperClusterAlgorithm({ maxZoom: 10 })
       });

[davidpadych]

Could someone please do a review?

[luan-dang-techlabs]

@davidpadych @leighhalliday - with latest "@googlemaps/markerclusterer": "^2.0.13", the type errors are gone. This code works well and speeds up performance. Thanks again @leighhalliday

@leighhalliday - I noticed that when I try to 'mousemove' the map, the clusters don't render. It appears calculate() isn't working properly when 'mousemove'.

class BoundingSuperClusterAlgorithm extends SuperClusterAlgorithm {
  cluster({ map }: any) {
    const bounds: any = map.getBounds().toJSON();
    /** Need to dynamically set the bounding box, by default markercluster bound is hard coded which
     *  causes performance issue.
     *
     *  @example
     *   https://github.com/googlemaps/js-markerclusterer/issues/417
     */
    const boundingBox: any = [bounds.west, bounds.south, bounds.east, bounds.north];
    const transform = this.transformCluster.bind(this);

    return this.superCluster.getClusters(boundingBox, Math.round(map.getZoom())).map(transform);
  }
}

/**
   * Control how cluster should behave when clicking on cluster.
   *
   * @param event
   * @param cluster
   * @param map
   */
  const handleClusterOnClick = (event: google.maps.MapMouseEvent, cluster: Cluster, map: google.maps.Map) => {
    const lat = cluster.position.lat();
    const lng = cluster.position.lng();
    const zoom = map.getZoom() ?? 1;
    /** Get the current zoom level then increment by 1 */
    map.setZoom(zoom + 1);
    /** Pan to the current location to be centered */
    map.panTo({ lat, lng });
  };

 new MarkerClusterer({
        markers,
        map: mapRef.current,
        onClusterClick: handleClusterOnClick,
        algorithm: new BoundingSuperClusterAlgorithm({ maxZoom: 13, radius: 75 })
      });

[davidpadych]

@luan-dang-techlabs

State did not change when moved.. in library source code, state is only defined by zoom supercluster.ts

This PR extends the state with a bounding box.

[luan-dang-techlabs]

@leighhalliday - i see what you are saying. is this a bug then if the map doesn't re-render when dragging?

[NikitaKolpinskiy]

@leighhalliday Had the same issue as @luan-dang-techlabs with 'mousemove' event, is there any way to update marker clusters ?

[luan-dang-techlabs]

@leighhalliday Had the same issue as @luan-dang-techlabs with 'mousemove' event, is there any way to update marker clusters ?

@NikitaKolpinskiy I decided to use this tutorial instead from @leighhalliday pasted below, I highly recommend it instead of js-markerclusterer.

https://www.leighhalliday.com/google-maps-clustering

[daun]

Can confirm this PR + the suggested fix by @bgurung03 works great to improve performance.

[michalkrynski]

Any updates? I am having same issue with sets 13k, there isn't a bound which makes it slow.

Hey! In the meantime, you can extend and add the bounding functionality without too much work:

export default class BoundingSuperClusterAlgorithm extends SuperClusterAlgorithm {
  cluster({ map }) {
    const bounds = map.getBounds().toJSON();
    const boundingBox = [bounds.west, bounds.south, bounds.east, bounds.north];

    return this.superCluster
      .getClusters(boundingBox, Math.round(map.getZoom()))
      .map(this.transformCluster.bind(this));
  }
}

Hi is that fix is still valid? I have another issue using that - when I move map to the any direction markers/cluster are not refreshing. On the map are displaying only that markers what fit to the bound.

[daun]

@michalkrynski You'll need to add both the fix you're quoting as well as the fix suggested by @bgurung03, otherwise it won't update on mouse move.

[davidpadych]

Any update?

[amuramoto]

Closing in favor of https://github.com/googlemaps/js-markerclusterer/pull/640

Thanks for being the one to set all this in motion @leighhalliday !