Create Adaptive Grid On The Map For Clusterization

In our application we use google map APIs v1. I wrote grid-based clusterization for markers (total amount up to few thousands). Everything works fine - good performance, etc... Th

Solution 1:

For android maps API v1 there is a clustering library here: https://github.com/damianflannery/Polaris. This is a fork of Cyril Mottier's Polaris library, but the discussion on pull request suggest it won't be merged back into original. See here. I haven't looked at the source, so I can't tell you if they use grid clustering.

As for your question, I think using static screen-independent cluster grid is the way to go. I'd only suggest changing the values of millidegrees. For zoom level that is different by 1, millidegs should be divided (or multiplied) by 2.

Also note that with latitude you can't use degrees value directly, but you have to push it through a Mercator projection. This is to make grid consist of squares instead of having them look like rectangles with height few times greater than width closer to the north and south poles.

This is basically what I do in Android Maps Extensions for maps API v2. I assumed 180 degrees grid size on zoom level 0, so 90 degrees on zoom level 1, 45 on 2, etc. and about 85 microdegrees on zoom 21. The value can be changed in the API.

To you the most useful parts of the code from Extensions lib would be: SphericalMercator to convert latitude and some portions from GridClusteringStrategy.