ARTICLES

Handling Pushpin Collisions

Wilfried Mestdagh shares a solution for reducing the number of pushpins that must be displayed on a map

The question often comes up where thousands of pushpins must be displayed. However, nobody wants thousands of pushpins on the screen. So if you get that task then first rephrase the problem, that is: I have thousands pushpins, how do I make a comfortable GUI ?

Displaying thousands of pushpins take time. To avoid this you can only display the pushpins that are in view. Another point is the collision. You really don't want to have an ugly view of lots of pushpins overlapping each other.

In this article we describe the most simple thing to avoid collision, that is with sequentially positions as a route from a vehicle. In a future article we describe other possible approach needed for non sequentially positions.

You really don't want to display an ugly screen like the one above. Instead you calculate the distance between each pushpin, get the distance of 1 pixel, and leave preferable 20 pixels between each pushpin. This must be recalculated at every pan or zoom of the map.

This is the result you get, the more you zoom in you get more detail and more pushpins will be plotted. Only pushpins that are in view are plotted. This picture is the same data but with the code described and with a minimum distance of 20 pixels between the center of the pushpins.

You eventually can indicate to the user that there is more detail available when zooming in by setting a custom symbol for each pushpin if there are some not plotted because of collision, but these things are only limited to your own imagination.

Let's explain shortly what we going to do. First of all we calculate the geocoordinates of the 4 corners of the visible map. We need this to only plot pushpins that are in the visible area. So we calculate the top and bottom latitude and the left and right longitude to do that.

Location topLeftLoc = MP.ActiveMap.XYToLocation(0, 0);
Location bottomRightLoc = MP.ActiveMap.XYToLocation(MP.ActiveMap.Width, MP.ActiveMap.Height);
double top = topLeftLoc.Latitude;
double left = topLeftLoc.Longitude;
double bottom = bottomRightLoc.Latitude;
double right = bottomRightLoc.Longitude;

Then we have to specify the minimum distance we want between each pushpin. We can do that to ask MapPoint the distance of 1 pixel. We want at least 20 pixels between the center of our pushpins so we multiply with 20.

double minimumDistance = MP.ActiveMap.PixelSize * 20;

We do the calculation for each record. In this example dispLat and dispLon is the last displayed pushpin where we want a minimum distance from. You can put it in AfterViewChange then it is recalculated at every pan or zoom of the map.

double lat = positions.DataSource[positions.Index].Lat;
double lon = positions.DataSource[positions.Index].Lon;
if (lat <= top && lat >= bottom && lon >= left && lon <= right &&
    getDistance(dispLat, dispLon, lat, lon) >= minimumDistance) {
    dispLat = lat;
    dispLon = lon;
    Location loc = MP.ActiveMap.GetLocation(lat, lon, 1);
    MP.ActiveMap.AddPushpin(loc, positions.DataSource[positions.Index].Name);
}

We only need to explain the getDistance function. The example is for km. The cosine calculation is for correction of the distance in longitude because this is only equal to latitude if you are on the equator. In this example the distances are very short so this is only needed once and not in each call so you can speed it up. The 60 * 1.852 is because 1 arc minute is exact 1 nautical mile and the division by 1.609 is if your geo units are in miles instead of in kilometres.

private double getDistance(double lat1, double lon1, double lat2, double lon2)
{
    double lat = lat2 - lat1;
    double lon = (lon2 - lon1) * Math.Cos(Deg2Rad((lat1 + lat2) / 2));
    double dist = Math.Sqrt(Math.Pow(lat, 2) + Math.Pow(lon, 2));
    return dist * 60 * 1.852;
    //return dist * 60 * 1.852 / 1.609;
}

This is the CSV file from where I have got the data in this example and here is the complete code inclusive the reader and object data table I have used so that you can drop it in a VS project to test it. Just make a new project, drop an MapPoint activeX component on it, name it MP, assign the AfterViewChange and you can see it working.

In this example I delete all datasets on the map. You don't want this of course. I suggest to create a dataset for the route and only delete that particular dataset. But this is only a quick example of course. The data is in Belgium, but maybe someone can make a CSV file from a route somewhere in US and post the link here, so that the example is also usable with MapPoint North America version.

partial class Main: Form { string csvFileName = Path.GetDirectoryName(Assembly.GetExecutingAssembly().GetModules()[0].FullyQualifiedName) + "\\route.csv"; TextReader reader; Positions positions = new Positions(162); public Main() { InitializeComponent(); reader = new StreamReader(csvFileName); reader.ReadLine(); string line; int n = 1; while (true) { line = reader.ReadLine(); if (line == null) break; string[] pos = line.Split(';'); double lat = Convert.ToDouble(pos[0]); double lon = Convert.ToDouble(pos[1]); Position position = new Position(); position.Lat = lat; position.Lon = lon; position.Name = n.ToString(); n++; positions.DataSource.Add(position); } MP.NewMap(GeoMapRegion.geoMapEurope); } private void MP_AfterViewChange(object sender, EventArgs e) { foreach (MapPoint.DataSet ds in MP.ActiveMap.DataSets) if (ds.DataMapType == GeoDataMapType.geoDataMapTypePushpin) ds.Delete(); Location topLeftLoc = MP.ActiveMap.XYToLocation(0, 0); Location bottomRightLoc = MP.ActiveMap.XYToLocation(MP.ActiveMap.Width, MP.ActiveMap.Height); double top = topLeftLoc.Latitude; double left = topLeftLoc.Longitude; double bottom = bottomRightLoc.Latitude; double right = bottomRightLoc.Longitude; double minimumDistance = MP.ActiveMap.PixelSize * 20; double dispLat = 0; double dispLon = 0; positions.First(); while (!positions.Eof) { double lat = positions.DataSource[positions.Index].Lat; double lon = positions.DataSource[positions.Index].Lon; if (lat <= top && lat >= bottom && lon >= left && lon <= right && getDistance(dispLat, dispLon, lat, lon) >= minimumDistance) { dispLat = lat; dispLon = lon; Location loc = MP.ActiveMap.GetLocation(lat, lon, 1); MP.ActiveMap.AddPushpin(loc, positions.DataSource[positions.Index].Name); } positions.Next(); } } private static double Deg2Rad(double degree) { return degree * Math.PI / 180; } private double getDistance(double lat1, double lon1, double lat2, double lon2) { double lat = lat2 - lat1; double lon = (lon2 - lon1) * Math.Cos(Deg2Rad((lat1 + lat2) / 2)); double dist = Math.Sqrt(Math.Pow(lat, 2) + Math.Pow(lon, 2)); return dist * 60 * 1.852; //return dist * 60 * 1.852 / 1.609; // if it is in miles } public class Position { public double Lat; public double Lon; public string Name; } public class Positions { private List<Position> data; private int index; private bool eof = true; public Positions(int Capacity) { data = new List<Position>(Capacity); } public List<Position> DataSource { get { return data; } } public void Clear() { index = 0; eof = true; data.Clear(); } public int Index { get { return index; } } public bool Eof { get { return eof; } } public void First() { eof = data.Count == 0; index = 0; } public void Next() { eof = index >= data.Count - 1; if (eof) return; index++; } } }

	MP2Kmag Internet