algorithm - 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.