Freigeben über

Clustering Pushpins in Windows Store Apps

  • Artikel

Clustering of pushpins in Bing Maps consists of grouping together nearby locations into clusters. As the user zooms in, the clusters break apart to reveal the individual locations. The goal of this process is to reduce the number of pushpins that are displayed on the map at any given time. This results in better performance of the map control and also a better experience for the user, as they will be able to see the map and not have pins hiding behind other pins.

I wrote my first clustering algorithm in the fall of 2007 for version 5 of the Bing Maps AJAX control. This was later turned into an MSDN article which is still available. Over the years this algorithm has evolved. It was added to v6.3, and later turned into a module for v7. The original algorithm used a grid-based system that updated every time you moved the map. This was fast, but also had a small side effect in that even the slightest pan of the map caused the data to re-cluster. Since the grid was based on the current map view, it would sometimes cause data points to move from one grid cell to another, which resulted in pins jumping around.

A couple years ago I created a new point-based clustering algorithm. This algorithm adds the first location in the data set as a cluster point. It then takes the next location in the data set and checks to see if it is nearby any existing cluster point. If it is, then it is added to it. Otherwise a new cluster point is created. This continues until the whole data set is assigned to a cluster. This algorithm is a bit slower than the grid-based algorithm, but results in a much better user experience as the pins don’t jump around when panning the map. Both the grid and point-based clustering modules work with the Bing Maps JavaScript SDK for Windows Store apps.

Recently I had someone ask how to implement clustering in the Bing Maps WPF control. I migrated over the JavaScript to C# and created the code sample you can find here. Since then I ported both of these clustering algorithms into a reusable C# library for use with the Bing Maps Windows Store SDK. Rather than going through how to write the code for the algorithms, this blog post is going to cover how to make use of this library in your Windows Store app.

Before we get started, you can download the full source code for this blog here. If you run the sample application, you will first have to press the Generate Mock Data button so that the application has a data set to work with. Once you have done this and the data set is created, you will be able to view the data on the map either as individual pushpins or clustered using the grid or point-based clustering algorithm. Below is a screenshot of 5,000 pushpins drawn on the map:

image

As you can see, visualizing 5,000 pushpins makes the map pretty crowded and hard to see. You may notice it is harder to pan and zoom the map. Now if you then select the point or grid-based clustering buttons, the pins on the map will update and look something like this. 

image

 To make the clusters easier to see, I have made them red. As you zoom in you will find them break apart into individual clusters.

Creating the Base Project

To implement clustering, first create a new Windows Store App in Visual Studio. Open Visual Studio and create a new project in C# or Visual Basic. Select the Blank App (XAML) template, name the application and then press OK.

image

Next, download the clustering code sample and unzip it. Inside you will find a folder called BingMapsClusteringEngine. Copy this folder and navigate to the folder your project is stored in and paste it there. Next, in Visual Studios, right click on the Solution folder and select Add → Existing Project. In the window that opens, navigate to the folder where your project is stored, locate the BingMapsClusteringEngine.csproj file, and select it. This will add the reusable clustering library to your project.

imageNext, add a references to the clustering library and the Bing Maps SDK. Right click on the References folder and press Add Reference. Select Solution → Projects and select BingMapsClusteringEngine. Next, select Windows → Extensions and then select Bing Maps for C#, C++ and Visual Basic. If you do not see this option, be sure to verify that you have installed the Bing Maps SDK for Windows Store apps. While you are here, also add a reference to the Microsoft Visual C++ Runtime Package, as this is required by the Bing Maps SDK when developing using C# or Visual Basic. Press OK.imageIn Solution Explorer, set the Active solution platform in Visual Studio by right clicking on the Solution folder and selecting Properties. Select Configuration Properties → Configuration. Find your project and the BingMapsClusteringEngine project and under the Platform column, set the target platform to x86 and press OK. image

Now open the MainPage.xaml file. Update the XAML to the following.

<Page

    x:Class="BingMapsClusteringExample.MainPage"

    xmlns="https://schemas.microsoft.com/winfx/2006/xaml/presentation"

    xmlns:x="https://schemas.microsoft.com/winfx/2006/xaml"

    xmlns:local="using:BingMapsClusteringExample"

    xmlns:d="https://schemas.microsoft.com/expression/blend/2008"

    xmlns:mc="https://schemas.openxmlformats.org/markup-compatibility/2006"

    xmlns:m="using:Bing.Maps"

  

    <Grid Background="{StaticResource ApplicationPageBackgroundThemeBrush}">

        <m:Map Name="MyMap" Credentials="YOUR_BING_MAPS_KEY"/>

 

        <Border Width="260" Height="270" CornerRadius="15" Background="Black"

               Margin="20" VerticalAlignment="Center" HorizontalAlignment="Right">

            <StackPanel Margin="10">

 

                <TextBlock Text="Mock Data Size:" FontSize="18"/>

 

                <TextBox Name="EntitySize" Text="5000"/>

 

                <Button Name="GenerateBtn" Content="Generate Mock Data"

                        Click="GenerateData_Clicked" Margin="0,10"/>

 

                <Button Name="ViewAllBtn" Content="View all locations"

                        IsEnabled="False"  Click="ViewAllData_Clicked"/>

 

                <Button Name="PointBtn" Content="Use Point Based Clustering"

                IsEnabled="False" Margin="0,10" Click="PointClusterData_Clicked"/>

 

                <Button Name="GridBtn" Content="Use Grid Based Clustering"

                        IsEnabled="False" Click="GridClusterData_Clicked"/>

            </StackPanel>

        </Border>

    </Grid>

</Page>

This will add a map and a bunch of buttons to the app for testing out the clustering functionality. Next, open the MainPage.xaml.cs or MainPage.xaml.vb file and update it with the following code. This code contains the event handlers for the buttons without any logic in them yet along with a useful method for generating mock data to test with. When mock data is being generated, all the buttons are disabled until the process is completed. The mock data is stored as a global private property in the document so that we can use it from the button handlers and do all the testing using the same data set.

C#

using Bing.Maps;

using BingMapsClusteringEngine;

using System;

using Windows.UI;

using Windows.UI.Popups;

using Windows.UI.Xaml;

using Windows.UI.Xaml.Controls;

using Windows.UI.Xaml.Media;

 

namespace BingMapsClusteringExample

{

    public sealed partial class MainPage : Page

    {

        private ItemLocationCollection _mockData;

 

        public MainPage()

        {

            this.InitializeComponent();

        }

 

        private async void GenerateData_Clicked(object sender, RoutedEventArgs e)

        {

        }

 

        private void ViewAllData_Clicked(object sender, RoutedEventArgs e)

        {

        }

 

        private void PointClusterData_Clicked(object sender, RoutedEventArgs e)

        {

        }

 

        private void GridClusterData_Clicked(object sender, RoutedEventArgs e)

        {

        }

 

        private void GenerateMockData(int numEntities)

        {

            GenerateBtn.IsEnabled = false;

            ViewAllBtn.IsEnabled = false;

            PointBtn.IsEnabled = false;

            GridBtn.IsEnabled = false;

 

            _mockData = new ItemLocationCollection();

 

            Random rand = new Random();

 

            object item;

            Location loc;

 

            for (int i = 0; i < numEntities; i++)

            {

                item = "Location number: " + i;

 

                loc = new Location()

     {

                    Latitude = rand.NextDouble() * 180 - 90,

                    Longitude = rand.NextDouble() * 360 - 180

                };

 

                _mockData.Add(item, loc);

            }

 

            GenerateBtn.IsEnabled = true;

            ViewAllBtn.IsEnabled = true;

            PointBtn.IsEnabled = true;

            GridBtn.IsEnabled = true;

        }

    }

}

 

VB

Imports BingMapsClusteringEngine

Imports Bing.Maps

Imports Windows.UI.Popups

Imports Windows.UI

 

Public NotInheritable Class MainPage

    Inherits Page

 

    Private _mockData As ItemLocationCollection

 

    Public Sub New()

        Me.InitializeComponent()

    End Sub

 

    Private Async Sub GenerateData_Clicked(sender As Object, e As RoutedEventArgs)

    End Sub

 

    Private Sub ViewAllData_Clicked(sender As Object, e As RoutedEventArgs)

    End Sub

 

    Private Sub PointClusterData_Clicked(sender As Object, e As RoutedEventArgs)

    End Sub

 

    Private Sub GridClusterData_Clicked(sender As Object, e As RoutedEventArgs)

    End Sub

 

    Private Sub GenerateMockData(numEntities As Integer)

        GenerateBtn.IsEnabled = False

        ViewAllBtn.IsEnabled = False

        PointBtn.IsEnabled = False

        GridBtn.IsEnabled = False

 

        _mockData = New ItemLocationCollection()

 

        Dim rand As Random = New Random()

 

        Dim item As Object

        Dim loc As Location

 

        For i As Integer = 0 To numEntities

            'Create some mock metadata to store

            item = "Location number: " + CStr(i)

 

            loc = New Location()

            loc.Latitude = rand.NextDouble() * 180 - 90

            loc.Longitude = rand.NextDouble() * 360 - 180

 

            _mockData.Add(item, loc)

        Next

 

        'Enable all the buttons

        GenerateBtn.IsEnabled = True

        ViewAllBtn.IsEnabled = True

        PointBtn.IsEnabled = True

        GridBtn.IsEnabled = True

    End Sub

End Class

 

At this point you should be able to build the application without any error occurring. However, since there is no logic in button handlers yet, the app won’t do much. The mock data is being stored in an ItemLocationCollection which allows each record to store an object and related location as a tuple. The object can be anything you want to have associated with the location, such as an ID value for requesting additional information from a service or a view model for populating an infobox.

To generate the mock data for testing, add the following code to the GenerateData_Clicked event handler. This code will clear all data from the map and get the mock data size from a textbox on the page. A check is done to ensure the number is valid and a message shown if it isn’t. If it is valid, then the GenerateMockData method is called to generate the desired number of mock data points.

C#

private async void GenerateData_Clicked(object sender, RoutedEventArgs e)

{

    MyMap.Children.Clear();

 

    int size;

 

    if (string.IsNullOrWhiteSpace(EntitySize.Text) ||

        !int.TryParse(EntitySize.Text, out size))

    {

        var dialog = new MessageDialog("Invalid size.");

        await dialog.ShowAsync();

        return;

    }

 

    GenerateMockData(size);

}

 

VB

Private Async Sub GenerateData_Clicked(sender As Object, e As RoutedEventArgs)

    MyMap.Children.Clear()

 

    Dim size As Integer

 

  If String.IsNullOrWhiteSpace(EntitySize.Text) Or

            Not Integer.TryParse(EntitySize.Text, size) Then

 

        Dim dialog = New MessageDialog("Invalid size.")

        Await dialog.ShowAsync()

        Return

    End If

 

    GenerateMockData(size)

End Sub

Next we will add the logic for viewing all the mock data on the map. To do this, loop through all the mock data items and create a pushpin for each one and add it to the map. Update the ViewAllData_Clicked event handler with the following code:

C#

private void ViewAllData_Clicked(object sender, RoutedEventArgs e)

{

    MyMap.Children.Clear();

 

    for (int i = 0; i < _mockData.Count; i++)

    {

        var pin = new Pushpin();

        pin.Tag = _mockData[i].Item;

        MapLayer.SetPosition(pin, _mockData[i].Location);

        MyMap.Children.Add(pin);

    }

}

 

VB

Private Sub ViewAllData_Clicked(sender As Object, e As RoutedEventArgs)

    MyMap.Children.Clear()

 

    For i As Integer = 0 To _mockData.Count

        Dim pin = New Pushpin()

        pin.Tag = _mockData(i).Item

        MapLayer.SetPosition(pin, _mockData(i).Location)

        MyMap.Children.Add(pin)

    Next

End Sub

If you run the application and try first pressing the button to create the mock data and then clicking the button to view all the data, you should see the map fill with pushpins. This may be slow, and if you entered a really large number, the application may even throw an error. If you try and pan or zoom you will likely notice significant lag by the map.

Implementing Clustering

In the sample, there are two classes with clustering logic in them; GridBasedClusteredLayer and PointBasedClusterLayer. Both of these classes inherit from an abstract class called BaseClusteredLayer. As such, these two classes share the same public properties and events.

There are two properties available: ClusterRadius and Items. The ClusterRadius is used by the algorithms for specifying how many pixels two pushpins can be separated before being grouped together. The smaller the radius, the more clusters (and more pushpins) will be displayed on the map. A smaller radius may also reduce the number of items you can have in the dataset before running into performance issues. The Items property is an ItemLocationCollection class which allows you to add your item and location information to be clustered. Every time this collection changes, the layer re-clusters. For best performance when initially adding a lot of locations, it is best to first add all your data to a separate ItemLocationCollection and then add it to the Items property using the AddRange method.

There are two event handlers on the cluster layers, CreateItemPushpin and CreateClusteredItemPushpin. These two event handlers are fired when the cluster layer tries to create the pushpins for representing the individual and clustered items. The CreateItemPushpin event handler accepts an object, which is the item that is linked with the location. The CreateClusteredItemPushpin event handler takes in a ClusteredPoint object. The ClusteredPoint class contains information about a cluster such as the location and a list of indices of all the items in the collection, and the length of this list is the number of items in the cluster. You can also get all the items by indices by using the GetItemByIndex or GetItemsByIndex methods from the Items property on the clustering layer. Both of these events can return a standard Pushpin or create a completely custom UIElement to represent the location on the map.

The following are two simple event handlers that return pushpins to represent the locations on the map. Individual locations use a standard pushpin, clusters are represented using a red pushpin with a plus sign. I used red, as the plus sign was hard to see in the screenshots, but you may prefer to use a different color. Add these event handlers to the MainPage.xaml.cs or MainPage.xaml.vb file.

C#

private UIElement CreateItemPushpin(object item)

{

    var pin = new Pushpin()

    {

        Tag = item

    };

 

    return pin;

}

 

private UIElement CreateClusteredItemPushpin(ClusteredPoint clusterInfo)

{

    var pin = new Pushpin()

    {

        Background = new SolidColorBrush(Colors.Red),

        Text = "+",

        Tag = clusterInfo

    };

 

    return pin;

}

 

VB

Private Function CreateItemPushpin(item As Object) As UIElement

    Dim pin = New Pushpin()

    pin.Tag = item

    Return pin

End Function

 

Private Function CreateClusteredItemPushpin(clusterInfo As ClusteredPoint) As UIElement

    Dim pin = New Pushpin()

    pin.Background = New SolidColorBrush(Colors.Red)

    pin.Text = "+"

    pin.Tag = clusterInfo

    Return pin

End Function

Adding a clustering layer to the map is as simple as adding a MapLayer to the map. Use the following code to update the PointClusterData_Clicked button handler. This code clears the map, creates an instance of the PointBasedClusteredLayer class, and adds the event handlers for creating the pushpins. It then adds the layer as a child of the map and populates the Items property of the layer with the mock data.

C#

private void PointClusterData_Clicked(object sender, RoutedEventArgs e)

{

    MyMap.Children.Clear();

 

    //Create an instance of the Point Based clustering layer

    var layer = new PointBasedClusteredLayer();

 

    //Add event handlers to create the pushpins

    layer.CreateItemPushpin += CreateItemPushpin;

    layer.CreateClusteredItemPushpin += CreateClusteredItemPushpin;

 

    MyMap.Children.Add(layer);

 

    //Add mock data to layer

    layer.Items.AddRange(_mockData);

}

 

VB

Private Sub PointClusterData_Clicked(sender As Object, e As RoutedEventArgs)

    MyMap.Children.Clear()

 

    'Create an instance of the Point Based clustering layer

    Dim layer = New PointBasedClusteredLayer()

 

    'Add event handlers to create the pushpins

    AddHandler layer.CreateItemPushpin, AddressOf CreateItemPushpin

    AddHandler layer.CreateClusteredItemPushpin, AddressOf CreateClusteredItemPushpin

 

    MyMap.Children.Add(layer)

 

    'Add mock data to layer

    layer.Items.AddRange(_mockData)

End Sub

The logic for adding a GridBasedClusteredLayer is exactly the same. Update the GridClusterData_Clicked button handler with the following code.

C#

private void GridClusterData_Clicked(object sender, RoutedEventArgs e)

{

    MyMap.Children.Clear();

 

    //Create an instance of the Grid Based clustering layer

    var layer = new GridBasedClusteredLayer();

 

    //Add event handlers to create the pushpins

    layer.CreateItemPushpin += CreateItemPushpin;

    layer.CreateClusteredItemPushpin += CreateClusteredItemPushpin;

 

    //Add mock data to layer

    layer.Items.AddRange(_mockData);

    MyMap.Children.Add(layer);

}

 

VB

Private Sub GridClusterData_Clicked(sender As Object, e As RoutedEventArgs)

    MyMap.Children.Clear()

 

    'Create an instance of the Grid Based clustering layer

    Dim layer = New GridBasedClusteredLayer()

 

    'Add event handlers to create the pushpins

    AddHandler layer.CreateItemPushpin, AddressOf CreateItemPushpin

    AddHandler layer.CreateClusteredItemPushpin, AddressOf CreateClusteredItemPushpin

 

    MyMap.Children.Add(layer)

 

    'Add mock data to layer

    layer.Items.AddRange(_mockData)

End Sub

The application is now complete. Run it and press the button to generate mock data. Select a clustering method to implement and then test it out by panning and zooming the map. Doing some testing I have found these work well for upwards of 50,000 locations on an x86 machine. I would expect this to be lower on an ARM-based device. That said, 50,000 locations is a lot of data points. You likely won’t want to have the user download that much data all at once. Again, you can download the full source code for this blog from the MSDN samples here.

If you are looking for some other great resources on Bing Maps for Windows Store apps, look through this blog, or check out all the Bing Maps MSDN code samples.

If you are looking to implement clustering on Windows Phone 8, this code should be easy enough port over. Also, you can find an interesting blog post that uses a hexagon based clustering algorithm for Windows Phone 8 here.

Comments