Android Mapview: Merging overlapping markers into a new marker

Question

So I have a MapView with a lot of markers, most of which are concentrated in mile wide clusters. When zoomed the markers overlap and appear to only be one. What I want to achieve is at a certain zoom level replace the overlapping markers with a group marker that will display the density of markers and onClick will zoom to display all markers inside. I know I can do this with brute force distance measurements but there must be a more efficient way. Anyone have any solution or smart algorithms on how I can achieve this?

Answer 1

Um... assuming the markers are not grouped, layered or anything: why - before showing them - don't you create a grid of certain density and simply bin the markers into the cells of your grid?

If you then count that several markers fall into the same bin (grid cell) - you can group them. If you need slightly more clever grouping, you might also check the neighbouring cells.

Maybe it sounds a bit primitive but:

• No n^2 algorithms
• No assumption about ordering of the input
• No need to additionally process markers which are not going to be shown

---

The code for the grid:

Note - I come from the C++ world (got here through [algorithm] tag) so I'll stick to the pseudo-C++. I do not know the API of the mapview. But I would be surprised if this couldn't be efficiently translated into whatever language/library you are using.

Input: - list of markers - the rectangle viewing window in world coordinates (section of world we are currently looking at)

In the simplest form, it would look something like this:

void draw(MarkerList mlist, View v) {

    //binning:

    list<Marker> grid[densityX][densityY]; //2D array with some configurable, fixed density
    foreach(Marker m in mlist) {
        if (m.within(v)) {
            int2 binIdx;
            binIdx.x=floor(densityX*(m.coord.x-v.x1)/(v.x2-v.x1));
            binIdx.y=floor(densityY*(m.coord.y-v.y1)/(v.y2-v.y1));
            grid[binIdx.x][binIdx.y].push(m); //just push the reference
        }

    //drawing:

    for (int i=0; i<densityX; ++i)
    for (int j=0; j<densityY; ++j) {
        if (grid[i][j].size()>N) {
            GroupMarker g;
            g.add(grid[i][j]); //process the list of markers belonging to this cell
            g.draw();
        } else {
            foreach (Marker m in grid[i][j])
                m.draw()
        }
    }

}

The problem that might appear is that an unwanted grid split may appear within some clustered group, forming two GroupMarkers. To counter that, you may want to consider not just one grid cell, but also its neighbors in the "\drawing" section, and - if grouped - mark neighboring cells as visited.

Answer 2

The following pragmatic solution based on pixel distance really worked best for me:

http://www.appelsiini.net/2008/11/introduction-to-marker-clustering-with-google-maps

Answer 3

I converted Cygnus X1's answer to Java. Put this method in your custom Overlay and modify drawSingle() and drawGroup() to suit your needs. You improve performance too, like converting the ArrayLists to primitive arrays.

    @Override
    public void draw(Canvas canvas, MapView mapView, boolean shadow) {
        // binning:
        int densityX = 10;
        int densityY = 10;
        // 2D array with some configurable, fixed density
        List<List<List<OverlayItem>>> grid = new ArrayList<List<List<OverlayItem>>>(
                densityX); 

        for(int i = 0; i<densityX; i++){
            ArrayList<List<OverlayItem>> column = new ArrayList<List<OverlayItem>>(densityY);
            for(int j = 0; j < densityY; j++){
                column.add(new ArrayList<OverlayItem>());
            }
            grid.add(column);
        }

        for (OverlayItem m : mOverlays) {
                int binX;
                int binY;

                Projection proj = mapView.getProjection();
                Point p = proj.toPixels(m.getPoint(), null);

            if (isWithin(p, mapView)) {
                double fractionX = ((double)p.x / (double)mapView.getWidth());
                binX = (int) (Math.floor(densityX * fractionX));
                double fractionY = ((double)p.y / (double)mapView.getHeight());
                binY = (int) (Math
                        .floor(densityX * fractionY));
//              Log.w("PointClusterer absolute", p.x+ ", "+p.y);
//              Log.w("PointClusterer relative", fractionX+ ", "+fractionY);
//              Log.w("PointClusterer portion", "Marker is in portion: " + binX
//                      + ", " + binY);
                grid.get(binX).get(binY).add(m); // just push the reference
            }
        }

        // drawing:

        for (int i = 0; i < densityX; i++) {
            for (int j = 0; j < densityY; j++) {
                List<OverlayItem> markerList = grid.get(i).get(j);
                if (markerList.size() > 1) {
                    drawGroup(canvas, mapView, markerList);
                } else {
                    // draw single marker
                    drawSingle(canvas, mapView, markerList);
                }
            }
        }
    }

    private void drawGroup(Canvas canvas, MapView mapView,
            List<OverlayItem> markerList) {
        GeoPoint point = markerList.get(0).getPoint();
        Point ptScreenCoord = new Point();
        mapView.getProjection().toPixels(point, ptScreenCoord);
        Paint paint = new Paint();
        paint.setTextAlign(Paint.Align.CENTER);
        paint.setTextSize(30);
        paint.setAntiAlias(true);
        paint.setARGB(150, 0, 0, 0);
        // show text to the right of the icon
        canvas.drawText("GROUP", ptScreenCoord.x, ptScreenCoord.y + 30, paint);
    }

    private void drawSingle(Canvas canvas, MapView mapView,
            List<OverlayItem> markerList) {
        for (OverlayItem item : markerList) {
            GeoPoint point = item.getPoint();
            Point ptScreenCoord = new Point();
            mapView.getProjection().toPixels(point, ptScreenCoord);
            Paint paint = new Paint();
            paint.setTextAlign(Paint.Align.CENTER);
            paint.setTextSize(30);
            paint.setAntiAlias(true);
            paint.setARGB(150, 0, 0, 0);
            // show text to the right of the icon
            canvas.drawText("SINGLE", ptScreenCoord.x, ptScreenCoord.y + 30,
                    paint);
        }
    }

    public static boolean isWithin(Point p, MapView mapView) {
        return (p.x > 0 & p.x < mapView.getWidth() & p.y > 0 & p.y < mapView
                .getHeight());
    }
}

Answer 4

Assuming your markers are grouped together in an ItemizedOverlay you could create a method which was called when the map was zoomed. This would compare pixel co-ordinates of each marker to see if they overlap and set a flag. Then in the draw method you could draw either the grouped marker or individuals;

Something like:

    //this would need to be wired to be called when the mapview is zoomed
    //it sets the drawgrouped flag if co-ordinates are close together
    Boolean drawGrouped=false;
    public void onMapZoom(MapView mapView){
      //loop thru overlay items
      Integer i,l=this.size();
      OverlayItem item;
      Integer deltaX=null,deltaY=null;
      Projection proj = mapView.getProjection();
      Point p=new Point();
      Integer x=null,y=null;
      Integer tolerance = 10; //if co-ordinates less than this draw grouped icon
      for(i=0;i<l;i++){
         //get the item
        item=this.getItem(i);
       //convert the overlays position to pixels
        proj.toPixels(item.getPoint(), p);
        proj.toPixels(item.getPoint(), p);
        //compare co-ordinates
        if(i==0){
            x=p.x;
            y=p.y;
            continue;
        }
        deltaX=Math.abs(p.x-x);
        deltaY=Math.abs(p.y-y);

        //if the co-ordinates are too far apart dont draw grouped
        if(deltaX>tolerance || deltaY>tolerance){
            drawGrouped=false;
            return;
        }
        x=p.x;
        y=p.y;
      }
      //all co-ords are within the tolerance
      drawGrouped=true;
    }

    public void draw(android.graphics.Canvas canvas, MapView mapView, boolean shadow){
        if(drawGrouped==true){
            //draw the grouped icon *needs to be optimised to only do it once
            drawGrouped(canvas,mapView,shadow);
            return;
        }
        //not grouped do regular drawing
        super.draw(canvas, mapView, shadow);
    }