Map dragging is slow when using more than 15 000 markers in a high zoom level

[googlemaps]

Map dragging is slow when using more than 15 000 markers in a high zoom level

[bbreukelen]

With help of stephenmeyer's hack I implemented my version of viewport only clustering which is lightning-fast.

Here is a detailed description of all my changes.
Because my time was limited and I had to reuse the viewport bounds I created a tiny class to store the value in. Quick & dirty but it doesn't hurt anyone.

So, create a class in android/clustering. I called mine bvb.java and this is the content:

package com.google.maps.android.clustering;
import com.google.android.gms.maps.model.LatLngBounds;

public class bvb {
    public static LatLngBounds mapClusterViewportBounds;
    public static boolean infoWindowShowing = false;
}

This holds 2 variables that can be accessed anywhere within the clusterManager.
The mapClusterViewportBounds variable will contain the coordinates of the part in the map that is visible to the user.
The infoWindowShowing variable should be set to true if you are using an infowindow popup when a user clicks on a marker. In the usual code, the clustering is only recalculated when the zoomlevel changes. If a user clicks on a marker, it's centered and the map doesn't zoom. The infowindow shows and stays in place. But with viewport clustering implemented, panning should also recalculate clusters or else you'd not see anything until you zoom. If a marker is now clicked, the infowindow shows, the marker is centered which now triggers reclustering and the infowindow is removed again.
To prevent this, whenever you are showing an infoWindow, add bvb.infoWindowShowing = true;
When an infoWindow is closed, add bvb.infoWindowShowing = false;
Note that you should also add bvb.infoWindowShowing = false; whenever you load new data on the map as the infoWindow is also removed when the map is cleared.

Now edit ClusterManager.java
In the import section add the following:

import android.util.Log;
import com.google.android.gms.maps.model.LatLng;
import com.google.android.gms.maps.model.LatLngBounds;

Find the onCameraChange method and change it to the following:

    @Override
    public void onCameraChange(CameraPosition cameraPosition) {
        // Added this to store the viewport bounds and increase slightly for user convenience
        LatLngBounds b = mMap.getProjection().getVisibleRegion().latLngBounds;
        LatLng bNE = b.northeast;
        LatLng bSW = b.southwest;
        double bAdjustLat = (bNE.latitude - bSW.latitude) * 0.15; // 15% increase
        double bAdjustLon = (bNE.longitude - bSW.longitude) * 0.15; // 15% increase
        bNE = new LatLng(bNE.latitude + bAdjustLat, bNE.longitude + bAdjustLon);
        bSW = new LatLng(bSW.latitude - bAdjustLat, bSW.longitude - bAdjustLon);
        bvb.mapClusterViewportBounds = new LatLngBounds(bSW, bNE);

        if (mRenderer instanceof GoogleMap.OnCameraChangeListener) {
            ((GoogleMap.OnCameraChangeListener) mRenderer).onCameraChange(cameraPosition);
        }

        if (bvb.infoWindowShowing) {
            Log.i("Cluster", "Not reclustering as we have an infoWindow");
            return;
        }
        cluster();
    }

We first load the viewport bounds into a variable. I increased the viewport with 15% so that the corners also show markers/clusters and panning shows at least some data to the sides. Just 15% extra won't hurt performance. You can play with this number and increase/decrease it to your liking.
Then I check if there's an infoWindow set. If so, it will not recluster until it's closed and the onCameraChange method is called.

Now edit algo/NonHierarchicalDistanceBasedAlgorithm.java.
In the import section add the following:

import android.util.Log;
import com.google.maps.android.clustering.bvb;

In the getClusters method find the line "for (QuadItem candidate : mItems) {
Underneath that is an if section about visitedCandidates.contains(candidate)).
Below that if-section, add this following code (for me it's on line 99).

if (bvb.mapClusterViewportBounds != null && !bvb.mapClusterViewportBounds.contains(candidate.mPosition)) {
                    continue; // Added to exclude markers outside viewport
}

While iterating over all map-points, this doesn't process any point outside your viewport + the 15%.
Which is what make the clustering perform quite well.

Then edit algo/PreCachingAlgorithmDecorator.java.
Find the getClustersInternal method.
Uncomment the following line:

mCache.put(discreteZoom, results);

The cluster-results are cached per zoomlevel. Since we now have viewports-clusters, this no longer works. I thought about caching by zoomlevel and viewport-coordinates, by the chance of hitting the exact same combination multiple times is slim and since it already performs pretty well I decided to disable caching completely. I didn't back-out the caching-code but went for the quick approach of just disabling saving to cache so it will never find any cache.

Here is an archive with the changes files.

Bo

[storkme]

I also have implemented @ericpanorel's solution to greatly improve the performance of clustering with a large data set.

I'm using a custom onCameraChange listener that grabs the bounds of the projection, asynchronously calculates a set of points that are within the new bounds, and then clears & adds the new points to the ClusterManager instance. I should note that I am scaling the bounds from the projection up by a factor of 1.5, this makes the user experience a fair bit nicer (clusters visible on screen don't change so rapidly compared with not scaling the bounds).

I would be interested to know if my workaround is the right way of doing things, seems to me like this functionality should be baked into the clustering algorithm somehow?

Thanks.

[PJHaynes304]

Having used android-maps-extensions and google-maps-clustering I would recommend the following:

https://github.com/sharewire/google-maps-clustering

Performance is fantastic and the code is well written and easily extended. Also has nice animations when the map moves and the clusters regroup.

[JonasDaWi]

Ok I tried it myself. The following code clears all items from the clustermanager and then dynamically checks if markers are in the visible area of the map after a camera position change. If they are, they are added to the clustermanager. This happens in an asynctask and the performance acceptable (at least on a Nexus 7) with ~ 20.000 Markers:
// setup camera change listener to fire the asynctask
mGoogleMap.setOnCameraChangeListener(new OnCameraChangeListener() {
@OverRide
public void onCameraChange(CameraPosition position) {
new DynamicallyAddMarkerTask().execute(mGoogleMap.getProjection().getVisibleRegion().latLngBounds);
}
});

private class DynamicallyAddMarkerTask extends AsyncTask<LatLngBounds, Void, Void> {
protected Void doInBackground(LatLngBounds... bounds) {
mClusterManager.clearItems();
for (Marker currentMarker : listOfMarkers) {
if (bounds[0].contains(currentMarker.mLocation)) {
mClusterManager.addItem(currentMarker);
}
}
return null;
}

@OverRide
protected void onPostExecute(Void result) {
mClusterManager.cluster();
}
}

storkme: how did you scale the bounds to be 1.5 times larger than the visible screen area?
I tried this:
final LatLngBounds screenBounds = mGoogleMap.getProjection().getVisibleRegion().latLngBounds;
float[] screenDiameterInMeters = new float[1];
Location.distanceBetween(screenBounds.northeast.latitude, screenBounds.northeast.longitude, screenBounds.southwest.latitude, screenBounds.southwest.longitude, screenDiameterInMeters);
screenDiameterInMeters[0] *= .5f;
final LatLngBounds.Builder builder = new LatLngBounds.Builder();
builder.include(SphericalUtil.computeOffset(screenBounds.northeast, screenDiameterInMeters[0], 25d));
builder.include(SphericalUtil.computeOffset(screenBounds.southwest, screenDiameterInMeters[0], 215d));

But somehow it doesn't work when I'm above the equator?

Greetings and thanks for the great library!

[JonasDaWi]

I think it had to do something with too long distances. When i keep them about 2.000.000 meters it works!

@broady are you going to include something like this in the clustermanager/alghorithm?

Thank you for the library!

[broady]

Hey folks.

I've actually left the Maps team, so everything I do on this project is in my spare time.

Here's what I think should happen:

• DefaultClusterRenderer implements GoogleMap.OnCameraChangeListener.
• Somehow pipe camera change events to DefaultClusterRenderer.
• On the first camera change event, set a flag that changes the renderer to only render markers inside the visible bounds.
• Update visible markers when the camera changes and/or clusters change.

Unfortunately the loose coupling design of the library isn't conducive to this kind of stuff. I think it was a mistake.

@jfschmakeit @markmcd in case they have spare cycles.

[hannesa2]

I can confirm, this https://github.com/mg6maciej/android-maps-extensions/tree/develop can handle a lot of markers without performance issues

[stale]

Closing this. Please reopen if you believe it should be addressed. Thank you for your contribution.

[JonasDaWi]

I think I know why: the markers are distributed all over the the earth and clusters are calculated for all of them although only a small area is visible for the user. So imho a fix would be that clusters are only computed in the visible area.

[broady]

Thanks for reporting!

This is roughly fixed in HEAD, but needs more work, and is why v0.2 (which includes clustering) hasn't been widely publicised. Stand by. :-)

[broady]

Also, very curious what you're doing with 15K markers - feel free to mail me privately if you don't want to talk about it here.

[JonasDaWi]

Seems like adding a simple
if (onScreen)
before line 353 in DefaultClusterRenderer.java fixes the problem. But I'm unsure what other implications this has..

[broady]

Working on this next.

[guillaumeLeRoy]

Hey,
I have 3600 markers and when I zoom the map in a high zoom level it is very slow although I have a Nexus 5. When zooming is it possible to explode only visible clusters ( clusters on screen ) ? I think it will improve performances.

[ericpanorel]

I have encountered a similar problem with this myself, but it was with polylines. And here's what I did.
1.) In my activity/fragment, i have a SparseArray variable, which holds all the coordinate set (not Polyline yet)
2.) I added a listener to the camera change event onCameraChange such that when this event occurs, I fire off a local AsyncTask, to solve which coordinate set(s), are touched/inside the map's bounds. The map's bounds can be solved by calling map.getProjection().getVisibleRegion().latLngBounds. In this AsyncTask, I perform a tight loop (or something smarter) on my sets of coordinates to find out which ones should be displayed
3.) On the AsyncTask's onPostExecute method, I create the Polyline(s) for those coordinate sets, that are in, or touched by the map bounds (returned by doInBackground...

I'm sure for markers, this can be implemented, or maybe implemented already in the library...

[guillaumeLeRoy]

Thank you. Using the idea of your solution helped me improve performances.

[JonasDaWi]

could anyone of you post the code for doing this? I think it'd help many of us!

[akirmse]

I'd also like to suggest that the Algorithm interface include a cancel() member, and that ClusterManager.cluster() call it to stop any previous expensive clustering operations. It makes a difference when the user makes multiple rapid camera changes, e.g. zooming or panning. Better than relying on Java to kill the ClusterTask background thread IMO.

[Calius]

Is there any practicable solution for this issue yet?
Edit:
gruelfin's solution with the AsyncTask helped me a lot. Although, it still is imperative to keep track of one big list of markers over which you have to iterate. Im my case, I have some built in filters, the user can set, in order to minimize the number of total markers. Every time such a setting is changed, I have to update the listOfMarkers. But it is a small nuisance compared to having to recluster this complete list.

[newmanw]

Any word on this? I have about 8k markers and the lib is unusable at that point unfortunately. And I say unfortunately with great respect as this is a beautiful lib as far as UI, very easy to use and documented well. Really hoping I can use this soon :(

At a high level zoom things are pretty good. However as I start to zoom in performance degrades. I assume this is due to markers and clusters off the viewport being drawn/redrawn as I zoom.

Then once I am zoomed all the way in if I zoom out quickly I notice a huge hit. All the markers are unclustered (as I was all the way zoomed in before). I keep zooming out until I can see the entire map. I can see all (unclustered) markers and it takes 20-30 seconds to loop through all 8K markers and place them back into a clusters.

All of this probably relates to the fact that off screen markers and clusters are being drawn. However I also wonder if this is slow due to the animations. In cases like this it might make sense to be able to turn off animations and just remove and redraw all clusters and marker on zoom change.

[akirmse]

I made the following changes locally to get the library to work reasonably
well with lots of markers:

• Disable animation completely. There is a constant you can change in the
  existing code for this.
• When camera motion stops, use an AsyncTask to remove all items from the
  ClusterManager, and then re-add only those visible on the screen. (I do
  this only if there's a large number of markers.)
• In ClusterManager, I imported the
  mClusterTask.executeOnExecutor(AsyncTask.THREAD_POOL_EXECUTOR) change from
  upstream (I had an older version of the library).
• I added a cancel() method on Algorithm, and a periodic check in
  NonHierarchicalDistanceBasedAlgorithm.getClusters, so that I could cancel
  previous clustering operations when starting a new one.

I like this library but I wish the team were more responsive to obvious
problems like this and
https://code.google.com/p/gmaps-api-issues/issues/detail?id=5313

On Mon, Apr 6, 2015 at 6:44 PM, Billy Newman [email protected]
wrote:

Any word on this? I have about 8k markers and the lib is unusable at that
point unfortunately. And I say unfortunately with great respect as this is
a beautiful lib as far as UI, very easy to use and documented well. Really
hoping I can use this soon :(

At a high level zoom things are pretty good. However as I start to zoom in
performance degrades. I assume this is due to markers and clusters off the
viewport being drawn/redrawn as I zoom.

Then once I am zoomed all the way in if I zoom out quickly I notice a huge
hit. All the markers are unclustered (as I was all the way zoomed in
before). I keep zooming out until I can see the entire map. I can see all
(unclustered) markers and it takes 20-30 seconds to loop through all 8K
markers and place them back into a clusters.

All of this probably relates to the fact that off screen markers and
clusters are being drawn. However I also wonder if this is slow due to the
animations. In cases like this it might make sense to be able to turn off
animations and just remove and redraw all clusters and marker on zoom
change.

—
Reply to this email directly or view it on GitHub
#29 (comment)
.

[newmanw]

@akirmse agreed, wish issues like this would get more attention. Of course I am not contributing so I can't really complain ;)

Is this being actively worked by contributors, or has anyone forked, maybe a possible PR for this?

[emkou]

For more than two years the clustering element of this library is totally unusable. Clustering more than 100 items even on a big area brings huge performance issues. This should be either adressed or removed completely from the library. The suggestion by @akirmse does significantly improve the performance of this library.

[stephenmeyer]

Heres my hacked version :
Update NonHierarchicalDistanceBasedAlgorithm getClusters function to

public Set<? extends Cluster> getClusters(double zoom, LatLngBounds bounds)

Add the following if to the QuadItem candidate for each loop

if(!bounds.contains(candidate.mPosition)) {
continue;
}

Replace ClusterManager.cs onCameraChange function with the following:

mMap.clear();
mPreviousCameraPosition = mMap.getCameraPosition();
currentBounds = mMap.getProjection().getVisibleRegion().latLngBounds;
Set<? extends Cluster> results = mAlgorithm.getClusters(mPreviousCameraPosition.zoom, currentBounds);
for(Cluster cluster : results)
{
// Strip out DefaultClusterRendered.cs perform method and render each cluster accordingly here
}

[gintechsystems]

@akirmse can you show your example in code?

[WonderCsabo]

@broady any update on this one? Your clustering looks very cool, the animations are great, but it just cannot handle more markers. And this is a big problem, since the point of clustering that we have lots of markers. I am currently using this algorithm to only cluster the visible markers, but this also has drawbacks (clusters change a lot, user have to wait a little bit when cluster show up after changing camera).
Are you planning to implement robust solution? Thanks in advance for your answer, and for this great library in general! :)

[gintechsystems]

I had to modify this library to my needs to get it working. I turned off animation and have it refreshing async on camera change. I have about 50k+ markers and it works great. It will only show markers in the visible region.

[newmanw]

Anyone on maps team supporting this or is it left to die?

[broady]

@newmanw I've just written down the exact steps of my preferred solution. Please discuss, send a pull request, etc! :)

[WonderCsabo]

@broady it is sad you no longer work on this officially, and no one else took over. This is an important project, even referred from the official doc. Thanks for still managing the project, your time is much appreciated!

I already tried to implement your solution, but only in a very naive way. ClusterManager automatically calls mRenderer.onCameraChange if the renderer implements OnCameraChangeListener, so piping that is already done. This is my onCameraChange method in the renderer:

@Override
public void onCameraChange(CameraPosition cameraPosition) {
  LatLngBounds bounds = map.getProjection().getVisibleRegion().latLngBounds;

  for (Marker marker : clusterManager.getClusterMarkerCollection().getMarkers()) {
      if (bounds.contains(marker.getPosition())) {
          marker.setVisible(true);
      } else {
          marker.setVisible(false);
      }
  }
}

There are two problems with this approach:

• when panning/rotating, the movements are slow because this loop blocks the drawing thread for too much time by iterating over all the clusters and checking they are in the bounds or not
• this does not help at all when zooming, because the markers are added asynchronously that time

So a more complicated solution is needed, but i could not figure that out.

[meierjan]

+1 for this issue

[Libby713]

As one solution to slow animation you can now choose to disable the animations, which was added in 27f7a5b

[CeccoCQ]

I've a map with 4k markers on it. I've tried the VisibleBasedAlgorithm but the performance remains very very slow.
When I zoom out the map, I've to wait some seconds before the clustering ends.
When I zoom in, the cluster disappear very slow, so the user is confused.

My experience:

• I've disabled the animations;
• I've used the https://github.com/zamesilyasa/android-maps-utils (branch issue-82)
• I've added further optimization on ClusterRenderer class

Is there a way to avoid the cluster expansion when the markers aren't visible on maps bounds? I think that this could be only solution.

[Gary111]

@CeccoCQ, you can try this optimised variant of Screen Based algorith zamesilyasa@8694da3.

[CeccoCQ]

Hi @Gary111,
I've finish the experiments with your code just now and I've seen some improvements.

By your experience, is there a way to increase the bitmap drawing performance?

[zamesilyasa]

Are you sure you are using as small bitmaps(thumbnails) for markers as possible? if bitmap is large, it will slow rendering down.

[Gary111]

@CeccoCQ, If you mean drawing markers, I use disk and memory LRU cache for this. So I generate icon only once and save it in cache, next time I just extract it form cache. It increases performance a little.

[CeccoCQ]

Hi, thanks for your responses.

This is my code used to create the bitmap (into MyRenderer constructor):

public LruCache<Integer, BitmapDescriptor> mIcons;
.....
int sizeSelected = Math.round(TypedValue.applyDimension(TypedValue.COMPLEX_UNIT_DIP, 50, context.getResources().getDisplayMetrics()));
Bitmap selectedBitmap = BitmapFactory.decodeResource(context.getResources(), mso.markerSelected).copy(Bitmap.Config.ARGB_8888, true);
Bitmap selected = Bitmap.createScaledBitmap(selectedBitmap, sizeSelected, sizeSelected, true);
BitmapDescriptor descSelected = mIcons.get(mso.markerSelected);
if (descSelected == null) {
    descSelected = BitmapDescriptorFactory.fromBitmap(selected);
    mIcons.put(markerTypeId, descSelected);
}

then into the onBeforeClusterItemRendered method:

BitmapDescriptor desc = mIcons.get(markerTypeId);

The original bitmap is a png file of 294x294px of 15Kb

[PJHaynes304]

So... over 4 years down the line is there any progress on this issue??
I've just migrated from AME to AMU and the performance is MUCH MUCH worse.
I thought it would be a step forwards in performance but it's been a huge leap backwards.
Even with animations turned off it takes an age for clusters to be regrouped when zooming out.

[nitkgupta]

I am facing the same issue. Dragging too slow when zooming out. Is there any way to fasten this?

[PJHaynes304]

The fact this issue has been open for 5 years and the lack of response from anyone suggests this will not be addressed. I’d recommend a 3rd party clustering library if you want something that works.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. Please comment here if it is still valid so that we can reprioritize. Thank you!