Clustering plugin

[jmkiley]

@incanus mentioned that his clustering example may be able to be adapted to work as a plugin. This may be a good option until mapbox/mapbox-gl-native#5814 is implemented in our Maps SDK.

[jmkiley]

This seems like a useful next plugin. I'll start working on it in early October. The clustering example seems to provide a good template, so can start from there!

[jmkiley]

It looks like the Android marker clustering plugin ports open-source clustering algorithms. I am leaning towards attempting this with the iOS equivalent, rather than simply porting the workaround as I originally planned. This would be more of a lift, but likely a better option in the long run. Thoughts?

cc @1ec5 @boundsj @fabian-guerra @lilykaiser

[1ec5]

ClusterKit already implements clustering of MGLAnnotationViews (alongside MapKit and Google Maps support). The project is MIT-licensed, so we could in theory adapt it into a plugin without much fuss. Assuming ClusterKit does well at what it does, should we still build this plugin, or should we focus on building annotation view clustering into the map SDK for MapKit parity (mapbox/mapbox-gl-native#5815)?

[fabian-guerra]

Considering that MapKit added this at last WWDC it may make more sense build this into our SDK for parity. I have seen clustering annotations is a requested feature in our repo and is a pretty common use case. Making this a first class citizen sounds like it's the way to go. But I may be wrong.

[jmkiley]

I have begun to experiment with both ClusterKit and the Google Maps utilities library in this branch: https://github.com/mapbox/mapbox-plugins-ios/tree/jk-clustering-plugin

Both libraries offer two algorithms. My current plan is to port the grid-based clustering algorithm first, since it doesn't rely on a quad tree (as far as I can tell). Based on how that goes, I'll work on porting the second clustering method.

A third option may be to create an iOS wrapper for SuperCluster, but I have not investigated how to go about that.

Introducing it as a plugin makes sense in the short term, since plugins are by nature experimental. It may be a better SDK feature in the long run, but I'd like to test it out here first.

Edited to add: The ClusterKit grid-based clustering algorithm does seem to use a quad tree, but their quad tree implementation seems simpler to port than the Google Maps one.

[1ec5]

A third option may be to create an iOS wrapper for SuperCluster, but I have not investigated how to go about that.

It would make sense to use Supercluster for an implementation built into the iOS SDK, because the SDK’s build system already pulls in that library, but not for a plugin implementation. To use a C++ library like Supercluster in this repository would unnecessarily complicate the build system, for example by making it difficult or impossible to distribute the library as source code via CocoaPods or Carthage. Instead, if we persue a plugin implementation, we might as well use a C or Objective-C implementation of the same algorithms.

[jmkiley]

Using a C or Objective-C implementation of Supercluster may be the most straight-forward approach in the long run, but I'm not sure that I would be able to efficiently port it.

Next steps for me will be looking into how much of a lift these options would be. I'll keep looking at both ClusterKit and the Google Maps utilities library, but I can also look into what be needed in order to use Supercluster with MGLPointAnnotation in the iOS SDK.

[jmkiley]

I'm going to port ClusterKit, with some modifications to optimize it for Mapbox. It's the most feasible for me to complete in a reasonable amount of time. My first focus will be a direct port that I can then refactor to focus on Mapbox. Additional goals for further down the line:

• Minimize the use of MapKit (for example, not using MKMapRectUnion)

• Include a simplified clustering algorithm (similar to what Google Maps Utils for iOS offers) so that we can test out additional clustering algorithms before we begin work on introducing this to the SDK. This allows us to more safely experiment with other clustering algorithms as we look at using this with other algorithms.