OptimIT

Google Maps has become a de-facto standard on the internet and mapping data has now become easier than ever before in web applications. But in certain cases it does a poor job presenting a large number of points on a small territory. Clustering icons  is one of the solutions, but when working with live data on enterprise level systems, clustering is simply not an option. For building management and support dashboards that deal with such situations we have developed a custom technique for marker displacement. Typical situations can arise in fleet management applications (just check the congestion around major airports or marine ports) and large scale network monitoring applications (where a lot of nodes exist in the same area).

In such applications it can be necessary to show markers on a map without clustering or overlapping. All markers must be shown because a marker color represents live state (for example, process running / slow / interrupted). Objects may be close to each other (or even have the exact same coordinates, like machines in a facility), but must be shown individually to provide proper status indication without having to zoom in to check the state of each one.

The image above represents a clustering solution when a single marker is displayed on the map replacing all markers that are very close to each other at the certain zoom level. This is a good approach if space is very limited and you are looking just for quantity information, but if it is mandatory to display each data point, this approach is not good because it hides relevant information.

The next solution could be to just display markers on the map by default. The problem with this default icon placement is that overlapping occurs when coordinates are close together (or even exact same, if several points are within the same town or building). Overlapping is a problem because the view is blocked by other icons closer to the top so you don’t have relevant data displayed, there could be 1, 5, 50 or more icons hidden below the top 2 or 3 icons. The lower the zoom level, the worse the effect becomes.

To fully understand how we solved this, we have to get a bit more familiar with how Google Maps handles tiles, zooming and translating latitude/longitude into pixel position on screen. Google Maps uses the Mercator projection, which stretches out the poles in order to preserve locally measured angles.

In short, the technique does exactly this:

1. calculate marker positions on screen (from lat/long to pixels)
2. detect if they are too close to each other
3. if they are, displace marker by set number of pixels (usually icon size)
4. recalculate position (from pixels to lat/long)
5. display markers with changed position.

The procedure has to be done at each zoom level change, because when zoomed in, the positions can be correctly shown and all markers might be visible, but while zooming out much of the markers will occupy the same space and overlapping would occur, hiding some of the markers.

While longitude and latitude of a marker remain the same, the pixel coordinates change depending on a zoom level. A map at zoom level 0 contains a single tile (256 x 256 pixels). At zoom level 1 there are four times as many tiles than at the zoom level 0 since the tile size is always constant.

Now that we have the position that the marker should occupy, we run a check to see if it interferes with another marker:

if (Math.abs(stationData.getPixelX() - stationPixels.getPixelX()) < 7
    && Math.abs(stationData.getPixelY() - stationPixels.getPixelY()) < 7) {
    stationData.setPixelY(stationData.getPixelY() - 13);
}

And repeat that for all the markers we are about to plot. To make sure we can effectively keep track of all the changed positions, the original position should always be preserved and all calculated displacements should be temporary. To do this we can go about it in the following way:

1. Create an object that will hold:

• Marker’s original latitude and longitude
• Marker’s original pixel coordinate
• Marker’s new latitude and longitude

2. Create an array that holds all the markers with original coordinates

3. Create an array that will hold all the markers with changed coordinates.

The image below shows tidy displaced icons, without overlaps or clustering.

The following is the source code showing how to achieve marker displacement:

public class ObjectStatus implements Serializable{
   private Double originalLong;
   private Double originalLat;
   private Double newLong;
   private Double newLat;
   private int pixelX;
   private int pixelY;
   // add getters and setters
}
// calculate original pixels from longitudes and latitudes
for (MarkerObject markerObject : allMarkers) {                                                            
   Point markerPoint = map.convertLatLngToContainerPixel(
      LatLng.newInstance(
         markerObject.getOriginalLat(),markerObject.getOriginalLong()));
   // save the original pixels
   markerObject.setPixelX(markerPoint.getX());
   markerObject.setPixelY(markerPoint.getY());
}
      // create an array to keep all markers, regardless of coordinate change
ArrayList<MarkerObject> markersWithModifiedPixels =
   new ArrayList<MarkerObject>();
for (MarkerObject markerObject : allMarkers) {
         for (MarkerObject markerPixels : markersWithModifiedPixels) {
      // check the pixel offset. If there is a marker that is too close,
      // set the new pixelY for the current marker
      // note that constants depend upon icon size
      if (Math.abs(markerObject.getPixelX() - markerPixels.getPixelX()) < 7 &&
         Math.abs(markerObject.getPixelY() - markerPixels.getPixelY()) < 7) {
         markerObject.setPixelY(markerObject.getPixelY() - 13);
         markersWithModifiedPixels.add(markerObject);                          
      }             
      // convert pixels to lat/long and add a marker overlay to the map                   
      for (int i = 0; i < markersWithModifiedPixels.size(); i++){
               LatLng latLng = map.convertContainerPixelToLatLng(Point.newInstance(
         markersWithModifiedPixels.get(i).getPixelX(),
         markersWithModifiedPixels.get(i).getPixelY()));
               markersWithModifiedPixels.get(i).setNewLat(latLng.getLatitude());
         markersWithModifiedPixels.get(i).setNewLong(latLng.getLongitude();
         map.addOverlay(markersWithModifiedPixels.get(i));
      }                                            
       }
}

One important thing to note when calculating marker position is that Google Maps only displays latitudes in the range from -85 to +85 degrees instead of -90/+90. That’s why you have to ensure that a Latitude converted from the changed pixel is in the supported range.