Android Maps Point Clustering

Is there any code for Point Clustering in android? How can i load thousand pinpoint without having performance issues?

Answers


Last night i got into PointClustering on Android MapView. Saw that there was nothing out for the community so i would like to share.

Groups the geopoints if the projection of them in the mapView is too close. Also renders only the visible poins.

UPDATE

Code reworked from scrach.

Now available at GitHub

  1. Code Reworked from scratch
  2. Used GVM clustering algorithm (pretty fast but doesn't position clustered point as good as mine)
  3. Soon to add previous clustering algorithm too


I have reworked in the above code and controlled the no of overlay icon in the map view and separated the group and single point.

My Code:

MMapView.java
import java.util.ArrayList;
import java.util.List;

import android.content.Context;
import android.graphics.BitmapFactory;
import android.graphics.Canvas;
import android.graphics.drawable.BitmapDrawable;
import android.graphics.drawable.Drawable;
import android.util.AttributeSet;

import com.google.android.maps.GeoPoint;
import com.google.android.maps.MapView;
import com.google.android.maps.Overlay;
import com.impiger.maphighlight.R;

//Reference - http://stackoverflow.com/questions/7447350/android-maps-point-clustering

public class MMapView extends MapView {

    private static final String TAG = MMapView.class.getSimpleName();
    private static final int MAX_VISIBLE_POINTS = 1;
    private PMapViewOverlay itemizedOverlay;
    private List<Overlay> mapOverlays;
    private List<GeoPoint> geoPoints = new ArrayList<GeoPoint>();
    private BitmapDrawable drawable;
    private Context context;
    private Drawable emptyDrawable;
    private int count;
    private int oldZoomLevel = -1;
    ArrayList<OverlayItemExtended> mOverlays;

    public MMapView(Context context, AttributeSet attrs) {
        super(context, attrs);
        this.context = context;
        mapOverlays = getOverlays();
        drawable = new BitmapDrawable(
                BitmapFactory.decodeResource(getResources(),
                        R.drawable.blue_65));
        itemizedOverlay = new PMapViewOverlay(drawable, context);
        emptyDrawable = context.getResources().getDrawable(
                R.drawable.marker);
        mOverlays = new ArrayList<OverlayItemExtended>();
        init();
    }

    private GeoPoint getPoint(double lat, double lon) {
        return (new GeoPoint((int) (lat * 1000000.0), (int) (lon * 1000000.0)));
    }

    private void init(){
        putPoint(11, 77, true);
        putPoint(11.5, 76.6, false);
        putPoint(10.98383, 77.32112, false);
        putPoint(10, 77, false);
        putPoint(11, 78, false);
        putPoint(11, 77.5, false);
        putPoint(10.5, 77, false);
        putPoint(12, 77, false);
        putPoint(11.77, 77.11, false);
        putPoint(12.1, 78.33, false);
        putPoint(11.83, 77.293, false);
        putPoint(11.12, 77, false);
        putPoint(11.13, 77, false);
        putPoint(11.14, 77, false);
        putPoint(11.15, 77, false);
        putPoint(11.12, 77.2, false);
        putPoint(11.13, 77.34, false);
        putPoint(11.14, 77.4, false);
        putPoint(11.15, 77.1977, false);
        putPoint(11.347373, 77.5627783, true);
        putPoint(11.53454, 76.696645, false);
        putPoint(10.19282, 77.847373, false);
        putPoint(10.4728, 76.39388, false);
        putPoint(11.4563, 78, false);
        putPoint(11.73663, 77.5927, false);
        putPoint(10.5674, 77.6762, false);
        putPoint(12.02882, 77.672782, false);
        putPoint(11.7767876, 77.1123423, false);
        putPoint(12.18332, 78.33, false);
        putPoint(11.8393883, 77.293938783, false);
        putPoint(11.388323, 77.9478723, false);
        putPoint(11.1345645, 77.97723, false);
        putPoint(11.1423423, 77.73774, false);
        putPoint(11.1552, 77.793783, false);
        putPoint(11.127895434, 77.2944554, false);
        putPoint(11.13232345, 77.342234, false);
        putPoint(11.14456573, 77.4, false);
        putPoint(11.159765, 77.1977, false);
    }


    public void putPoint(double lat, double lon, boolean isMyPosition) {
        int latitude = (int) (lat * 1E6);
        int longitude = (int) (lon * 1E6);
        GeoPoint geo = new GeoPoint(latitude, longitude);
        geo = getPoint(lat, lon);

        /*
         * Remove doubles
         */
        Boolean alreadyExists = false;
        for (GeoPoint item : geoPoints) {
            if (item.getLatitudeE6() == geo.getLatitudeE6()
                    && item.getLongitudeE6() == geo.getLongitudeE6()) {
                alreadyExists = true;
            }
        }
        if (!alreadyExists) {
            geoPoints.add(geo);
        }
    }

    /*
     * Place the overlays
     */
    public void placeOverlays() {
        itemizedOverlay.removeAllOverlays();
        getOverlays().clear();
        mapOverlays.clear();
        mOverlays.clear();
        int i = 1;
        for (GeoPoint item : geoPoints) {
            OverlayItemExtended overlayitem = new OverlayItemExtended(item,
                    "title "+i, "snippet");
            // Here is where the magic happens
            addOverlayItemClustered(overlayitem, this,
                    geoPoints.size());
            i++;
        }

        for(int j=0;j<mOverlays.size();j++){
            OverlayItemExtended overlayItem = mOverlays.get(j);
            if(overlayItem.isMaster){
                if(overlayItem.slaves.size() > 0){
                    itemizedOverlay = new PMapViewOverlay(drawable, context);
                    itemizedOverlay.addOverlayItem(overlayItem);
                }else{
                    itemizedOverlay = new PMapViewOverlay(emptyDrawable, context);
                    itemizedOverlay.addOverlayItem(overlayItem);
                }
                mapOverlays.add(itemizedOverlay);
            }
        }
    }

    /*
     * Update the points at panned / zoom etc
     */
    public void dispatchDraw(Canvas canvas) {
        super.dispatchDraw(canvas);
        if (getZoomLevel() != oldZoomLevel) {
            placeOverlays();
        }
        oldZoomLevel = getZoomLevel();
    }

    public void addOverlayItemClustered(OverlayItemExtended thisOverlay,
            MapView mapView, int totalPoints) {
        for (OverlayItemExtended otherOverlay : mOverlays) {
            /*
             * Thresshold for the clustering
             */
            /*
             * Zoom level >15 don't cluster If less than Max_Visible_points
             * don't cluster
             */
            if (mapView.getZoomLevel() >= 14
                    || (MAX_VISIBLE_POINTS > totalPoints)
                    && PointCluster.getOverLayItemDistance(thisOverlay,
                            otherOverlay, mapView) > 60) {
                mOverlays.add(thisOverlay);
                return;
            }
            if (PointCluster.getOverLayItemDistance(thisOverlay, otherOverlay,
                    mapView) < 90 && !thisOverlay.isClustered) {
                // Here is where the clustering actually happens
                if (otherOverlay.isMaster) {
                    thisOverlay.isMaster = false;
                    // otherOverlay.isMaster = false;
                    thisOverlay.isClustered = true;
                    otherOverlay.isClustered = true;
                    otherOverlay.slaves.push(thisOverlay);
                    thisOverlay.parent = otherOverlay;
                } else if (PointCluster.getOverLayItemDistance(thisOverlay,
                        otherOverlay.parent, mapView) < 90
                        && otherOverlay.isClustered) {
                    thisOverlay.isMaster = false;
                    thisOverlay.isClustered = true;
                    thisOverlay.parent = otherOverlay.parent;
                    otherOverlay.parent.slaves.push(thisOverlay);
                }
            }
        }
        mOverlays.add(thisOverlay);
    }
}
OverlayItemExtended.java
import java.util.Stack;

import com.google.android.maps.GeoPoint;
import com.google.android.maps.OverlayItem;

public class OverlayItemExtended extends OverlayItem {

    public boolean isClustered = false;
    public boolean isMaster = true;
    public boolean isMe = false;
    public OverlayItemExtended parent;
    public Stack<OverlayItemExtended> slaves = new Stack<OverlayItemExtended>();

    public OverlayItemExtended(GeoPoint point, String title, String snippet) {
        super(point, title, snippet);
    }
}
PMapViewOverlay.java
import java.util.ArrayList;

import android.content.Context;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.graphics.Point;
import android.graphics.drawable.Drawable;
import android.widget.Toast;

import com.google.android.maps.GeoPoint;
import com.google.android.maps.ItemizedOverlay;
import com.google.android.maps.MapView;

@SuppressWarnings("rawtypes")
public class PMapViewOverlay extends ItemizedOverlay {

    private static final String TAG = PMapViewOverlay.class.getSimpleName();
    private Context context;
    private ArrayList<OverlayItemExtended> mOverlays;

    public PMapViewOverlay(Drawable defaultMarker, Context context) {
        super(boundCenterBottom(defaultMarker));
        this.context = context;
        mOverlays = new ArrayList<OverlayItemExtended>();

        paint.setTextAlign(Paint.Align.CENTER);
        paint.setTextSize(25);
        paint.setAntiAlias(true);
        paint.setStrokeWidth(5);
        paint.setColor(Color.WHITE);
    }

    @Override
    protected OverlayItemExtended createItem(int i) {
        return mOverlays.get(i);
    }

    @Override
    public int size() {
        return mOverlays.size();
    }

    public void addOverlayItem(OverlayItemExtended overlay) {
        mOverlays.add(overlay);
        populate();
    }

    public void removeAllOverlays() {
        mOverlays.clear();
        populate();
    }

    public void removePointsButMe() {
        for (int i = 0; i < mOverlays.size(); i++) {
            OverlayItemExtended overlay = mOverlays.get(i);
            if (overlay.isMe) {
                mOverlays.clear();
                addOverlayItem(overlay);
                break;
            }
        }
        populate();
    }

    Paint paint = new Paint();

    @Override
    public void draw(Canvas canvas, MapView mapView, boolean shadow) {
        super.draw(canvas, mapView, shadow);

        // cycle through all overlays
        for (int index = 0; index < mOverlays.size(); index++) {
            OverlayItemExtended item = mOverlays.get(index);

            // Converts lat/lng-Point to coordinates on the screen
            GeoPoint point = item.getPoint();
            Point ptScreenCoord = new Point();
            mapView.getProjection().toPixels(point, ptScreenCoord);

            if (item.isMaster) {
                if (item.slaves.size() > 0) {
                    canvas.drawText(item.slaves.size() + 1 + "",
                            ptScreenCoord.x, ptScreenCoord.y - 13, paint);
                }
            }
        }
    }

    @Override
    protected boolean onTap(int index) {
        OverlayItemExtended item = mOverlays.get(index);
        if (item.isMaster) {
            if (item.slaves.size() == 0) {
                Toast.makeText(context, "You tapped item " + item.getTitle(),
                        Toast.LENGTH_LONG).show();
            }
        }
        return super.onTap(index);
    }
}

I didn't change any code in PointCluster.java.

I hope this will help somebody.


There is a nice sample for it. Check it here: http://code.google.com/p/android-playground-erdao/source/browse/trunk/SampleClusterMap/?r=226


There is a pull request on github for the Polaris library (https://github.com/cyrilmottier/Polaris) which adds clustering:

https://github.com/cyrilmottier/Polaris/pull/20

https://github.com/damianflannery/Polaris/tree/clustering


There also this answer which only requires you override the draw method of your Overlay. It divides your mapView into sections, so it's a bit less sophisticated. But at least it worked.


FOR ANDROID V2 HERE GOES CLUSTERING CODE

Hi All

I looked at various libraries and found them so complexx could'nt understand a word so i decided to make my own clutering algo Here goes my code in java

static int OFFSET = 268435456;
static double RADIUS = 85445659.4471;
static double pi = 3.1444;

public static double lonToX(double lon) {
        return Math.round(OFFSET + RADIUS * lon * pi / 180);
    }

    public static double latToY(double lat) {
        return Math.round(OFFSET
                - RADIUS
                * Math.log((1 + Math.sin(lat * pi / 180))
                        / (1 - Math.sin(lat * pi / 180))) / 2);
    }

    public static int pixelDistance(double lat1, double lon1, double lat2,
            double lon2, int zoom) {
        double x1 = lonToX(lon1);
        double y1 = latToY(lat1);

        double x2 = lonToX(lon2);
        double y2 = latToY(lat2);

        return (int) (Math
                .sqrt(Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2))) >> (21 - zoom);
    }

    static ArrayList<Cluster> cluster(ArrayList<Marker> markers, int zoom) {

        ArrayList<Cluster> clusterList = new ArrayList<Cluster>();

        ArrayList<Marker> originalListCopy = new ArrayList<Marker>();

        for (Marker marker : markers) {
            originalListCopy.add(marker);
        }

        /* Loop until all markers have been compared. */
        for (int i = 0; i < originalListCopy.size();) {

            /* Compare against all markers which are left. */

            ArrayList<Marker> markerList = new ArrayList<Marker>();
            for (int j = i + 1; j < markers.size();) {
                int pixelDistance = pixelDistance(markers.get(i).getLatitude(),
                        markers.get(i).getLongitude(), markers.get(j)
                                .getLatitude(), markers.get(j).getLongitude(),
                        zoom);

                if (pixelDistance < 40) {

                    markerList.add(markers.get(i));
                    markerList.add(markers.get(j));

                    markers.remove(j);

                    originalListCopy.remove(j);
                    j = i + 1;
                } else {
                    j++;
                }

            }

            if (markerList.size() > 0) {
                Cluster cluster = new Cluster(clusterList.size(), markerList,
                        markerList.size() + 1, originalListCopy.get(i)
                                .getLatitude(), originalListCopy.get(i)
                                .getLongitude());
                clusterList.add(cluster);
                originalListCopy.remove(i);
                markers.remove(i);
                i = 0;

            } else {
                i++;
            }

            /* If a marker has been added to cluster, add also the one */
            /* we were comparing to and remove the original from array. */

        }
        return clusterList;
    }

Just pass in your array list here containing latitude and longitude then to display clusters here goes the function

@Override
    public void onTaskCompleted(ArrayList<FlatDetails> flatDetailsList) {

        LatLngBounds.Builder builder = new LatLngBounds.Builder();

        originalListCopy = new ArrayList<FlatDetails>();
        ArrayList<Marker> markersList = new ArrayList<Marker>();
        for (FlatDetails detailList : flatDetailsList) {

            markersList.add(new Marker(detailList.getLatitude(), detailList
                    .getLongitude(), detailList.getApartmentTypeString()));

            originalListCopy.add(detailList);

            builder.include(new LatLng(detailList.getLatitude(), detailList
                    .getLongitude()));

        }

        LatLngBounds bounds = builder.build();
        int padding = 0; // offset from edges of the map in pixels
        CameraUpdate cu = CameraUpdateFactory.newLatLngBounds(bounds, padding);

        googleMap.moveCamera(cu);

        ArrayList<Cluster> clusterList = Utils.cluster(markersList,
                (int) googleMap.getCameraPosition().zoom);

        // Removes all markers, overlays, and polylines from the map.
        googleMap.clear();

        // Zoom in, animating the camera.
        googleMap.animateCamera(CameraUpdateFactory.zoomTo(previousZoomLevel),
                2000, null);

        CircleOptions circleOptions = new CircleOptions().center(point) //
                // setcenter
                .radius(3000) // set radius in meters
                .fillColor(Color.TRANSPARENT) // default
                .strokeColor(Color.BLUE).strokeWidth(5);

        googleMap.addCircle(circleOptions);

        for (Marker detail : markersList) {

            if (detail.getBhkTypeString().equalsIgnoreCase("1 BHK")) {
                googleMap.addMarker(new MarkerOptions()
                        .position(
                                new LatLng(detail.getLatitude(), detail
                                        .getLongitude()))
                        .snippet(String.valueOf(""))
                        .title("Flat" + flatDetailsList.indexOf(detail))
                        .icon(BitmapDescriptorFactory
                                .fromResource(R.drawable.bhk1)));
            } else if (detail.getBhkTypeString().equalsIgnoreCase("2 BHK")) {
                googleMap.addMarker(new MarkerOptions()
                        .position(
                                new LatLng(detail.getLatitude(), detail
                                        .getLongitude()))
                        .snippet(String.valueOf(""))
                        .title("Flat" + flatDetailsList.indexOf(detail))
                        .icon(BitmapDescriptorFactory
                                .fromResource(R.drawable.bhk_2)));

            }

            else if (detail.getBhkTypeString().equalsIgnoreCase("3 BHK")) {
                googleMap.addMarker(new MarkerOptions()
                        .position(
                                new LatLng(detail.getLatitude(), detail
                                        .getLongitude()))
                        .snippet(String.valueOf(""))
                        .title("Flat" + flatDetailsList.indexOf(detail))
                        .icon(BitmapDescriptorFactory
                                .fromResource(R.drawable.bhk_3)));

            } else if (detail.getBhkTypeString().equalsIgnoreCase("2.5 BHK")) {
                googleMap.addMarker(new MarkerOptions()
                        .position(
                                new LatLng(detail.getLatitude(), detail
                                        .getLongitude()))
                        .snippet(String.valueOf(""))
                        .title("Flat" + flatDetailsList.indexOf(detail))
                        .icon(BitmapDescriptorFactory
                                .fromResource(R.drawable.bhk2)));

            } else if (detail.getBhkTypeString().equalsIgnoreCase("4 BHK")) {
                googleMap.addMarker(new MarkerOptions()
                        .position(
                                new LatLng(detail.getLatitude(), detail
                                        .getLongitude()))
                        .snippet(String.valueOf(""))
                        .title("Flat" + flatDetailsList.indexOf(detail))
                        .icon(BitmapDescriptorFactory
                                .fromResource(R.drawable.bhk_4)));

            } else if (detail.getBhkTypeString().equalsIgnoreCase("5 BHK")) {
                googleMap.addMarker(new MarkerOptions()
                        .position(
                                new LatLng(detail.getLatitude(), detail
                                        .getLongitude()))
                        .snippet(String.valueOf(""))
                        .title("Flat" + flatDetailsList.indexOf(detail))
                        .icon(BitmapDescriptorFactory
                                .fromResource(R.drawable.bhk5)));

            } else if (detail.getBhkTypeString().equalsIgnoreCase("5+ BHK")) {
                googleMap.addMarker(new MarkerOptions()
                        .position(
                                new LatLng(detail.getLatitude(), detail
                                        .getLongitude()))
                        .snippet(String.valueOf(""))
                        .title("Flat" + flatDetailsList.indexOf(detail))
                        .icon(BitmapDescriptorFactory
                                .fromResource(R.drawable.bhk_5)));

            }

            else if (detail.getBhkTypeString().equalsIgnoreCase("2 BHK")) {
                googleMap.addMarker(new MarkerOptions()
                        .position(
                                new LatLng(detail.getLatitude(), detail
                                        .getLongitude()))
                        .snippet(String.valueOf(""))
                        .title("Flat" + flatDetailsList.indexOf(detail))
                        .icon(BitmapDescriptorFactory
                                .fromResource(R.drawable.bhk_2)));

            }
        }

        for (Cluster cluster : clusterList) {

            BitmapFactory.Options options = new BitmapFactory.Options();
            options.inMutable = true;
            options.inPurgeable = true;
            Bitmap bitmap = BitmapFactory.decodeResource(getResources(),
                    R.drawable.cluster_marker, options);

            Canvas canvas = new Canvas(bitmap);

            Paint paint = new Paint();
            paint.setColor(getResources().getColor(R.color.white));
            paint.setTextSize(30);

            canvas.drawText(String.valueOf(cluster.getMarkerList().size()), 10,
                    40, paint);

            googleMap.addMarker(new MarkerOptions()
                    .position(
                            new LatLng(cluster.getClusterLatitude(), cluster
                                    .getClusterLongitude()))
                    .snippet(String.valueOf(cluster.getMarkerList().size()))
                    .title("Cluster")
                    .icon(BitmapDescriptorFactory.fromBitmap(bitmap)));

        }

    }

ANY QUESTIONS OR DOUBTS PLEASE ASK WILL CLEAR THEM ALL ...........THANKS


Google's Android Map Utils has a solution for this: Google Maps Android Marker Clustering Utility.

Add dependency

implementation 'com.google.maps.android:android-maps-utils:0.5'

Make your own ClusterItem

class MyItem(
        private val position: LatLng,
        val title: String,
        private val snippet: String
) : ClusterItem {
    override fun getPosition() = position
    override fun getTitle() = title
    override fun getSnippet() = snippet
}

Setting up the cluster manager and adding items

override fun onMapReady(googleMap: GoogleMap) {
    val clusterManager = ClusterManager<MyItem>(this, googleMap)
    googleMap.setOnCameraIdleListener(clusterManager)

    clusterManager.addItem(MyItem(LatLng(51.51, -0.12), "title", "snippet"))
}

That's it! Items are now shown as follows:

Customizing the icon

In order to customize the icon, add val icon: BitmapDescriptor to your ClusterItem and change the renderer of the cluster manager:

    clusterManager.renderer = object : DefaultClusterRenderer<MyItem>(this, googleMap, clusterManager) {
        override fun onBeforeClusterItemRendered(item: MyItem, markerOptions: MarkerOptions) {
            markerOptions.icon(item.icon)
        }
    }

Making items clickable

As a rule of thumb, any interaction with markers should go through the cluster manager instead. The same applies to making items clickable.

    googleMap.setOnMarkerClickListener(clusterManager)
    clusterManager.setOnClusterItemClickListener {
        Toast.makeText(this, "Clicked on item ${it.title}", Toast.LENGTH_SHORT).show()
        true
    }

Similarly, you can call googleMap.setOnInfoWindowClickListener(clusterManager) and clusterManager.setOnClusterItemInfoWindowClickListener to handle clicks on the info window.


Need Your Help

Linear Algebra library for Javascript?

javascript linear-algebra

I don't need anything fancy; basically, if it will let me do some basic Matrix*Matrix stuff I'll be happy.

Creating SHA1 Hash from NSString

objective-c xcode hash sha1

How can I create a SHA1 from a NSString.