Android Mapview: Merging overlapping markers into a new marker

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?

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.

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

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());
    }
}

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);
    }

What you are looking for is usually called clustering. There are common techniques to do this, you can refer, for example, to this SO question, it leads to this post.

The basic idea is to divide the map on squares based on the current zoom level (you can cache calculations based on the zoom level to avoid recalculation when the user starts zooming), and to group them based which square they belong to. So you end up having some sort of grouping based on zoom level, ie for level 1-5 just draw the markers, for level 5-8 group them in squares of 20 miles, for 9-10 in squares of 50 miles, and so on.

Here is another relevant question on SO that you may want to take a look, not sure about the performance of this though: Android Maps Point Clustering

If your markers are grouped, you'll have a fair idea at what zoom level you should be displaying individual markers or the group marker e.g. zoom level > 17 then display individual markers, otherwise display the group marker. I used code something like this in my ItemizedOverlay to change my markers:

@Override
public void draw(Canvas canvas, MapView mapv, boolean shadow)
{       
    int zoom = mapv.getZoomLevel();

    switch(zoom)
    {
        case 19:
            setMarkersForZoomLevel19();
            break;
        case 18:
            setMarkersForZoomLevel18();
            break;
        case 17:
            setMarkersForZoomLevel17();
            break;
        case 16:
            setMarkersForZoomLevel16();
            break;
        default:
            // Hide the markers or remove the overlay from the map view.                
            mapv.getOverlays().clear();
    }       

    area.drawArea(canvas, mapv);

    // Putting this call here rather than at the beginning, ensures that
    // the Overlay items are drawn over the top of canvas stuff e.g. route lines.
    super.draw(canvas, mapv, false);        

}


private void setMarkersForZoomLevel19()
{       
    for (JourneyOverlayItem item : mOverlays)
    {               
        item.setMarker(areaPointIcon48);            
    }
}

If its possible to have the individual markers in a collection, you could easily get the largest and smallest latitude and longitude and the difference between them will give you the latitude and longitude span (this could then be used to zoom to the span to show the group of markers). Divide the spans by 2 and you should have the centre point for placing the group marker.

This is the approach that I used. However, it's O(n^2).

The pins must be sorted based on prominent.

Pick pin with the highest prominent. Look at all pins around it. Absorb pins near that pin.

Then move on to the next highest prominent pin. Do the same. Repeat.

Simple.

Things get complicated if you move the map around, zooming in, zooming out, and you want to ensure that the new pins are not being redrawn. So you check each cluster if they have to split during zoom in, and then you check each cluster if they have to merge during zoom out. Then you remove pins that's gone and add new pins. For every pin you add, you check whether they should join a cluster or form their own cluster.