Clustering PushPin and MapIcon with Windows 8.1 and Windows Phone 8.1

Windows-8-Logo

With more and more OpenData available, the need to represent those datas on a map is rising. However a map with too much information can be complicated to read.
To solve this problem, we have a possibility called Point Clustering, that allows us to represent a group of points through a single point. To be more clear, the real points will appear little by little when the zoom is growing.
Seen that Microsoft is unifying the development  between Windows 8.1 and Windows Phone 8.1, the solution I will show you a solution for both platforms.

The algorithm

In fact the algorithm is quite simple.
First of all, we are just taking the visible part of the map, then we divide this area in a list of smaller area (in squares), finally we group the points present in each small areas.

What do we need?

We want to show objects on maps, those objects have a position. So we create an object called ItemObjet. This object will have a Location object and an object:

public class ItemObjet
{
    public object item { get; set; }
    public Location Location { get; set; }
}

public class Location
{
    public double Latitude { get; set; }
    public double Longitude { get; set; }
}

On the map a collection of ItemObjet will be shown, in order to  simplify the way of writing, I decided to create an object « ItemCollection »:

public class ItemCollection : ObservableCollection<ItemObjet>
{
}

As I said before we are going to work only on the visible part of the map, so we need to define Bounds:

public class Bounds
{
    public double East { get; set; }
    public double West { get; set; }
    public double North { get; set; }
    public double South { get; set; }
}

In addition we need an object that will define the step used with the zoom. This step will be used « to cut » the map in smaller squares with side lenght equal to the step value.


public class Pas
{
    private readonly int min;

    public int Min
    {
        get { return min; }
    }

    private readonly int max;

    public int Max
    {
        get { return max; }
    }

    private readonly double value;

    public double Value
    {
        get { return value; }
    }

    public Pas(int min, int max, double value)
    {
        this.min = min;
        this.max = max;
        this.value = value;
    }
}

A bit in advance, but we will also need a tool that will tell us if a point is inside or outside the area defined by the border (bounds of the visible map ). To do so, I create an extension method:

public static bool IsPointInside(this Location location, Bounds bound)
{
    bool isInside = false;
    if (location != null)
    {
        if (bound.East < bound.West)
        {
            //longitude of the West border is bigger than the easter one
            if ((-180 <= location.Longitude && location.Longitude <= bound.East)
                || (bound.West <= location.Longitude && location.Longitude <= 180))
            {
                if (bound.South <= location.Latitude && location.Latitude <= bound.North)
                {
                    isInside = true;
                }
            }
        }
        else
        {
            //longitude of the east border is bigger than the wester one
            if (bound.West <= location.Longitude && location.Longitude <= bound.East)
            {
                if (bound.South <= location.Latitude && location.Latitude <= bound.North)
                {
                    isInside = true;
                }
            }
        }
    }
    return isInside;
}

There is here a point of complexity. In facts, it’s possible to slide in an infinite way on the longitude axe. This can create a case were the West longitude is bigger than the East longitude of the visible map, which is usually not the case.

CLUSTERITEM, THE WORKING CLASS!

It’s here that the clustering of PushPin takes place. This class expose a serie of DependencyProperties which allows to use the object inside the XAML.

WHICH ARE THE ACCESIBLE PROPERTIES?

Boundaries – allows to define the border of the visible part of the map.
CenterPoint – defines the center of the map
Collection – This collection hold the list of all the points that we want to show.
CurrentShownItem – List of items visible on the map. Can be a cluster or a unique point
ReloadPoint – Forces the reload of the map
Zoom – Used for the zoom of the map
ListPas – Collection which associate for a value of zoom a step for cuting the visible map.

WHICH ACTIONS START THE PROCESS?

There are 2 actions that can start the clustering process:
-The adding and removing items on the list of items (Collection)
-The change of zoom or center of the map.

ADD AND REMOVE ITEMS

The property Collection is an ItemCollection. This type inherits ObservableCollection. In order to know if items had been added or deleted, we will listen the event CollectionChanged. But we have to pay attention, this event is raised every time the collection has changed. In the case we add severals items in the collection, we just want to be notified at the end of the action of adding. To do so I use a timer which will be raised every 100ms:

private static DispatcherTimer timer = new DispatcherTimer();
static double value = 0;
static double valueBis = -1;

static void Collection_CollectionChanged(object sender, NotifyCollectionChangedEventArgs e)
{
    Windows.ApplicationModel.Core.CoreApplication.MainView.CoreWindow.Dispatcher.RunAsync(
               CoreDispatcherPriority.Normal, () =>
               {
                   if (!timer.IsEnabled)
                   {
                       timer.Start();
                   }
                   value = DateTime.Now.Ticks;
               });
}

private async void timer_Tick(object sender, object e)
{
    try
    {
        if (value != valueBis)
        {
            valueBis = value;
        }
        else
        {
            timer.Stop();
            isZoomChanged = true;
            CurrentShownItem.Clear();
            GenerateClusterData();
        }
    }
    catch (Exception ex)
    {
        Debug.WriteLine("timer_Tick " + ex.Message);
    }
}
CHANGE OF ZOOM OR CENTER

For now, in both cases, the user has to force the reload using the property ReloadPoint.

THE TREATMENT

This one has to be separated in two. In fact, two kinds of reload exist.
The first one due to a zoom change(change of zoom bigger than one unit). In this case the map is cleared and we recalculate the points.
In the second case the zoom is smaller than one unit or the center of the map changed. In the case we are just going to draw the new visible points and hide the invisible ones.

ZOOM

First clear the map:


CurrentShownItem.Clear();

The new value of the zoom will be notified

Then we are going to generate the new points with the following method:

GenerateWithZoomChange(collection) 

This method will first work on the min and max values of longitudes.
As we saw before, it can happen that the West value of the longitude is bigger than the East value. In this case, a boolean will be used to know how to continue the job (isMapBig):


if (!isMapBig)
{
    await Task.Run(() =>
    {
        for (double iLatitude = minBound; iLatitude <= maxBound; iLatitude = iLatitude + pas)
        {
            for (double iLongitude = minBoundWE; iLongitude <= maxBoundWE; iLongitude = iLongitude + pas)
            {
                RunLogicCluster(iLatitude, iLongitude, _zoom, _col, pas, center);
            }
        }
    });
}
else
{
    await Task.Run(() =>
    {
        for (double iLatitude = minBound; iLatitude <= maxBound; iLatitude = iLatitude + pas)
        {
            for (double iLongitude = -180; iLongitude < _bound.East; iLongitude = iLongitude + pas)
            {
                RunLogicCluster(iLatitude, iLongitude, _zoom, _col, pas, center);
            }



            for (double iLongitude = _bound.West; iLongitude <= 180; iLongitude = iLongitude + pas)
            {
                RunLogicCluster(iLatitude, iLongitude, _zoom, _col, pas, center);
            }
        }
    });
}

As you can see tha points are generated via two nested « for » loop.

The method RunLogicCluster() calculate the average value of longitudes and latitudes of the points present in the smaller area and create a cluster item. If there is only one push pin in a zone we add it directly.
Points are added in the collection CurrentShownItem.
In the case where the zoom is maximum and there is still cluster points, we don’t draw a cluster item, but all the pushpins present.

CHANGING THE CENTER

It’s mostly the same thing as before, the only difference is that there is a new step that destroys the point that are no longer visible.


List<ItemObjet> itemToDelete = new List<ItemObjet>();
// we only want the items present in the new visible map
// no need to redraw the items already drawned
var _bound = Boundaries;
var queryItem = (from item in _col
                 where item.Location.IsPointInside(_bound) && !item.Location.IsPointInside(_oldBound)
                 select item).ToList();

var queryToClear = (from item in CurrentShownItem
                    where !item.Location.IsPointInside(_bound)
                    select item).ToList();

foreach (var push in queryToClear)
{
    itemToDelete.Add(push);
}

Windows.ApplicationModel.Core.CoreApplication.MainView.CoreWindow.Dispatcher.RunAsync(
    CoreDispatcherPriority.Normal, () =>
    {
        foreach (var item in itemToDelete)
        {
            CurrentShownItem.Remove(item);
        }
    });
await GenerateWithZoomChange(queryItem);

Then the following is the same. In both cases we are going to save the current values of the borders of the visible map.

USING

This algo is working with Windows 8.1 and Windows Phone 8.1 thank to the use of Portable librairies.

WINDOWS 8.1

I defined the clustering tool in the XAML code with a Bing map control. I also defined DataTemplate for clusterPushPin and PushPin.


<DataTemplate x:Key="PinDataTemplate">
  <Grid DataContext="{Binding}" Loaded="FrameworkElement_OnLoaded">
    <controls:CustomPushPin Item="{Binding item}"/>
    <!--<bm:Pushpin Background="Green"></bm:Pushpin>-->
    <bm:MapLayer.Position>
      <bm:Location Latitude="{Binding Location.Latitude}" Longitude="{Binding Location.Longitude}" />
    </bm:MapLayer.Position>
  </Grid>
</DataTemplate>

<DataTemplate x:Key="ClusterPinDataTemplate">
  <Grid DataContext="{Binding}" Loaded="FrameworkElement_OnLoaded">
    <bm:Pushpin Background="Red" Tapped="UIElement_OnTapped" Text="{Binding item}">

    </bm:Pushpin>
    <bm:MapLayer.Position>
      <bm:Location Latitude="{Binding Location.Latitude}" Longitude="{Binding Location.Longitude}" />
    </bm:MapLayer.Position>
  </Grid>
</DataTemplate>

<dtSelector:PushPinSelector x:Key="PushPinSelector" PinTemplate="{StaticResource PinDataTemplate}" ClusterPinTemplate="{StaticResource ClusterPinDataTemplate}"/>

<cluster:ClusterItem ReloadPoint="{Binding ReloadPoint,Mode=TwoWay,UpdateSourceTrigger=PropertyChanged}"
                     CenterPoint="{Binding Center}"
                     collection="{Binding CollectionPoint}"
                     Boundaries="{Binding Bounds,UpdateSourceTrigger=PropertyChanged}"
                     Zoom="{Binding ZoomLevel,UpdateSourceTrigger=PropertyChanged}"
                     ListPas="{Binding ListPas}"
                     x:Name="clusterItems"/>

<bm:Map x:Name="map"
        Credentials="*"
        ViewChangeEnded="map_ViewChangeEnded">
  <bm:MapItemsControl ItemsSource="{Binding ElementName=clusterItems,Path=CurrentShownItem}"
                      ItemTemplateSelector="{StaticResource PushPinSelector}"/>
</bm:Map>

Subscribe to the ViewChangedEnded event is enought to get a notification when the map is changed (zoom changed or center changed). The event will have to be handled like follow:


private async void map_ViewChangeEnded(object sender, ViewChangeEndedEventArgs e)
{
    ViewModel.Bounds.East = (sender as Bing.Maps.Map).Bounds.East;
    ViewModel.Bounds.North = (sender as Bing.Maps.Map).Bounds.North;
    ViewModel.Bounds.West = (sender as Bing.Maps.Map).Bounds.West;
    ViewModel.Bounds.South = (sender as Bing.Maps.Map).Bounds.South;

    if (zoomLevelDouble != map.ZoomLevel)
    {                
        ViewModel.ZoomLevel = (int)map.ZoomLevel;
    }
    ViewModel.ReloadPoint = true;
    zoomLevelDouble = map.ZoomLevel;
}

ListPas.Add(new Pas(1, 2, 100));
ListPas.Add(new Pas(3, 5, 10));
ListPas.Add(new Pas(6, 8, 1));
ListPas.Add(new Pas(9, 10, 0.3));
ListPas.Add(new Pas(11, 12, 0.1));
ListPas.Add(new Pas(13, 13, 0.05));
ListPas.Add(new Pas(14, 15, 0.01));
ListPas.Add(new Pas(16, 19, 0.0005));
ListPas.Add(new Pas(20, 20, 0.0001));
ListPas.Add(new Pas(16, 16, 0.005));
ListPas.Add(new Pas(17, 17, 0.001));
ListPas.Add(new Pas(18, 18, 0.0005));
ListPas.Add(new Pas(19, 19, 0.0002));
ListPas.Add(new Pas(20, 20, 0.00001));

WINDOWS PHONE 8.1

<cluster:ClusterItem ReloadPoint="{Binding ReloadPoint,Mode=TwoWay,UpdateSourceTrigger=PropertyChanged}"
                     collection="{Binding CollectionPoint}"
                     Boundaries="{Binding Bounds,UpdateSourceTrigger=PropertyChanged}"
                     Zoom="{Binding ZoomLevel,UpdateSourceTrigger=PropertyChanged}"
                     ListPas="{Binding ListPas}"
                     x:Name="clusterItems"/>

<Maps:MapControl x:Name="map"
                 MapServiceToken="*" CenterChanged="map_CenterChanged">
  <Maps:MapItemsControl x:Name="MapItemsControl"
                        ItemsSource="{Binding ElementName=clusterItems,Path=CurrentShownItem}"
                        ItemTemplate="{StaticResource PinDataTemplate}"/>
</Maps:MapControl>

In the case of Windows Phone, subscribing to CenterChanged is enough. In fact, even during a zoom, in most of the case, the center of the map will change.
In case of adding an item in the ObservableCollection, this event is raised all the time during the modification and not only when the change ends. Like I did before, I will use a DispatcherTimer.
Then the treatment is the same!

GeoboundingBox geoBox = map.GetBounds();

ViewModel.Bounds.East = geoBox.SoutheastCorner.Longitude;
ViewModel.Bounds.North = geoBox.NorthwestCorner.Latitude;
ViewModel.Bounds.West = geoBox.NorthwestCorner.Longitude;
ViewModel.Bounds.South = geoBox.SoutheastCorner.Latitude;

if (zoomLevelDouble != map.ZoomLevel)
{
    ViewModel.ZoomLevel = (int)map.ZoomLevel;
}
ViewModel.ReloadPoint = true;
zoomLevelDouble = map.ZoomLevel;

ListPas.Add(new Pas(1, 1, 1));
ListPas.Add(new Pas(2, 2, 0.5));
ListPas.Add(new Pas(3, 5, 0.2));
ListPas.Add(new Pas(6, 7, 0.1));
ListPas.Add(new Pas(8, 9, 0.08));
ListPas.Add(new Pas(10, 11, 0.05));
ListPas.Add(new Pas(12, 13, 0.03));
ListPas.Add(new Pas(14, 14, 0.01));
ListPas.Add(new Pas(15, 15, 0.008));
ListPas.Add(new Pas(16, 16, 0.005));
ListPas.Add(new Pas(17, 17, 0.001));
ListPas.Add(new Pas(18, 18, 0.0005));
ListPas.Add(new Pas(19, 19, 0.0002));
ListPas.Add(new Pas(20, 20, 0.00001));

CONCLUSION

Using a map in application might be a good thing in order to allow the user to find easily points of interest. However un map with too much data will become unreadable.
Point clustering of points become a real need. More over with the code portability, an universal solution can allows us to save a lot of time.
All sources files of the article are available here.

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s