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:
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.
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.
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.
Next, 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.
In 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.
Now open the MainPage.xaml file. Update the XAML to the following.
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.
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.
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:
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.
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.
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.
The logic for adding a GridBasedClusteredLayer is exactly the same. Update the GridClusterData_Clicked button handler with the following code.
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.
- Ricky Brundritt, EMEA Bing Maps TSP
ClusteringPushpins-Thumbnail.png
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:
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.
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.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.
Next, 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.
In 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.
Now open the MainPage.xaml file. Update the XAML to the following.
| <Page x:Class="BingMapsClusteringExample.MainPage" xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" xmlns:local="using:BingMapsClusteringExample" xmlns:d="http://schemas.microsoft.com/expression/blend/2008" xmlns:mc="http://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 { publicsealedpartialclassMainPage : Page { privateItemLocationCollection _mockData; public MainPage() { this.InitializeComponent(); } privateasyncvoid GenerateData_Clicked(object sender, RoutedEventArgs e) { } privatevoid ViewAllData_Clicked(object sender, RoutedEventArgs e) { } privatevoid PointClusterData_Clicked(object sender, RoutedEventArgs e) { } privatevoid GridClusterData_Clicked(object sender, RoutedEventArgs e) { } privatevoid GenerateMockData(int numEntities) { GenerateBtn.IsEnabled = false; ViewAllBtn.IsEnabled = false; PointBtn.IsEnabled = false; GridBtn.IsEnabled = false; _mockData = newItemLocationCollection(); Random rand = newRandom(); object item; Location loc; for (int i = 0; i < numEntities; i++) { item = "Location number: " + i; loc = newLocation() { 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 PublicNotInheritableClassMainPage InheritsPage Private _mockData AsItemLocationCollection PublicSubNew() Me.InitializeComponent() EndSub PrivateAsyncSub GenerateData_Clicked(sender AsObject, e AsRoutedEventArgs) EndSub PrivateSub ViewAllData_Clicked(sender AsObject, e AsRoutedEventArgs) EndSub PrivateSub PointClusterData_Clicked(sender AsObject, e AsRoutedEventArgs) EndSub PrivateSub GridClusterData_Clicked(sender AsObject, e AsRoutedEventArgs) EndSub PrivateSub GenerateMockData(numEntities AsInteger) GenerateBtn.IsEnabled = False ViewAllBtn.IsEnabled = False PointBtn.IsEnabled = False GridBtn.IsEnabled = False _mockData = NewItemLocationCollection() Dim rand AsRandom = NewRandom() Dim item AsObject Dim loc AsLocation For i AsInteger = 0 To numEntities 'Create some mock metadata to store item = "Location number: " + CStr(i) loc = NewLocation() 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 EndSub EndClass |
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#
| privateasyncvoid GenerateData_Clicked(object sender, RoutedEventArgs e) { MyMap.Children.Clear(); int size; if (string.IsNullOrWhiteSpace(EntitySize.Text) || !int.TryParse(EntitySize.Text, out size)) { var dialog = newMessageDialog("Invalid size."); await dialog.ShowAsync(); return; } GenerateMockData(size); } |
VB
| PrivateAsyncSub GenerateData_Clicked(sender AsObject, e AsRoutedEventArgs) MyMap.Children.Clear() Dim size AsInteger IfString.IsNullOrWhiteSpace(EntitySize.Text) Or NotInteger.TryParse(EntitySize.Text, size) Then Dim dialog = NewMessageDialog("Invalid size.") Await dialog.ShowAsync() Return EndIf GenerateMockData(size) EndSub |
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#
| privatevoid ViewAllData_Clicked(object sender, RoutedEventArgs e) { MyMap.Children.Clear(); for (int i = 0; i < _mockData.Count; i++) { var pin = newPushpin(); pin.Tag = _mockData[i].Item; MapLayer.SetPosition(pin, _mockData[i].Location); MyMap.Children.Add(pin); } } |
VB
| PrivateSub ViewAllData_Clicked(sender AsObject, e AsRoutedEventArgs) MyMap.Children.Clear() For i AsInteger = 0 To _mockData.Count Dim pin = NewPushpin() pin.Tag = _mockData(i).Item MapLayer.SetPosition(pin, _mockData(i).Location) MyMap.Children.Add(pin) Next EndSub |
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#
| privateUIElement CreateItemPushpin(object item) { var pin = newPushpin() { Tag = item }; return pin; } privateUIElement CreateClusteredItemPushpin(ClusteredPoint clusterInfo) { var pin = newPushpin() { Background = newSolidColorBrush(Colors.Red), Text = "+", Tag = clusterInfo }; return pin; } |
VB
| PrivateFunction CreateItemPushpin(item AsObject) AsUIElement Dim pin = NewPushpin() pin.Tag = item Return pin EndFunction PrivateFunction CreateClusteredItemPushpin(clusterInfo AsClusteredPoint) AsUIElement Dim pin = NewPushpin() pin.Background = NewSolidColorBrush(Colors.Red) pin.Text = "+" pin.Tag = clusterInfo Return pin EndFunction |
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#
| privatevoid PointClusterData_Clicked(object sender, RoutedEventArgs e) { MyMap.Children.Clear(); //Create an instance of the Point Based clustering layer var layer = newPointBasedClusteredLayer(); //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
| PrivateSub PointClusterData_Clicked(sender AsObject, e AsRoutedEventArgs) MyMap.Children.Clear() 'Create an instance of the Point Based clustering layer Dim layer = NewPointBasedClusteredLayer() '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) EndSub |
The logic for adding a GridBasedClusteredLayer is exactly the same. Update the GridClusterData_Clicked button handler with the following code.
C#
| privatevoid GridClusterData_Clicked(object sender, RoutedEventArgs e) { MyMap.Children.Clear(); //Create an instance of the Grid Based clustering layer var layer = newGridBasedClusteredLayer(); //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
| PrivateSub GridClusterData_Clicked(sender AsObject, e AsRoutedEventArgs) MyMap.Children.Clear() 'Create an instance of the Grid Based clustering layer Dim layer = NewGridBasedClusteredLayer() '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) EndSub |
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.
- Ricky Brundritt, EMEA Bing Maps TSP
ClusteringPushpins-Thumbnail.png
