How to: Implement a Custom Clusterer
- 8 minutes to read
To implement a custom clusterer, inherit the MapClustererBase class and implement its MapClusterer.Clusterize, CreateObject abstract methods and MapClustererBase.Items property.
In this example, the CURE clustering method is implemented. Note that it has a high algorithmic complexity.
Note
- The Adapter’s MapDataAdapterBase.OnClustered method should be called to notify the Adapter that clustering is finished.
- To create a new collection of cluster representatives, the protected CreateItemColelction method should be used.
<Window
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
xmlns:local="clr-namespace:CustomClustererSample"
xmlns:dxm="http://schemas.devexpress.com/winfx/2008/xaml/map"
x:Class="CustomClustererSample.MainWindow"
Title="MainWindow" Height="720" Width="1280">
<Window.Resources>
<XmlDataProvider x:Key="dataSource"
Source="Data/TreesCl.xml"/>
</Window.Resources>
<Grid>
<dxm:MapControl x:Name="map">
<dxm:ImageTilesLayer>
<dxm:BingMapDataProvider BingKey="YourBingKeyHere"/>
</dxm:ImageTilesLayer>
<dxm:VectorLayer DataLoaded="VectorLayer_DataLoaded">
<dxm:ListSourceDataAdapter DataSource="{Binding Source={StaticResource dataSource}}"
DataMember="Row">
<dxm:ListSourceDataAdapter.Mappings>
<dxm:MapItemMappingInfo Latitude="lat"
Longitude="lon"/>
</dxm:ListSourceDataAdapter.Mappings>
<dxm:ListSourceDataAdapter.Clusterer>
<local:CureClusterer ClusterCount="10"/>
</dxm:ListSourceDataAdapter.Clusterer>
</dxm:ListSourceDataAdapter>
</dxm:VectorLayer>
</dxm:MapControl>
</Grid>
</Window>
using DevExpress.Map;
using DevExpress.Xpf.Map;
using System;
using System.Collections.Generic;
namespace CustomClustererSample {
class CureClusterer : MapClustererBase {
MapVectorItemCollection currentItems;
public override MapVectorItemCollection Items { get { return currentItems; } }
public int ClusterCount { get; set; }
public override void Clusterize(MapVectorItemCollection sourceItems, MapViewport viewport, bool sourceChanged) {
if (sourceChanged) {
currentItems = ClusterizeImpl(sourceItems);
Adapter.OnClustered();
}
}
protected override MapDependencyObject CreateObject() {
return new CureClusterer();
}
MapVectorItemCollection ClusterizeImpl(MapVectorItemCollection sourceItems) {
// Separate localizable and non localizable items.
List<MapItem> nonLocalizableItems = new List<MapItem>();
List<Cluster> clusters = new List<Cluster>();
foreach (MapItem item in sourceItems) {
ISupportCoordLocation localizableItem = item as ISupportCoordLocation;
if (localizableItem != null)
clusters.Add(Cluster.Initialize(localizableItem));
else
nonLocalizableItems.Add(item);
}
// Arrange initial clusters in increasing order of distance to a closest cluster.
clusters = Arrange(clusters);
// Aggregate localizable items.
while (clusters.Count > ClusterCount) {
MergeCloserstClusters(ref clusters);
}
// Convert internal cluster helpers to Map items.
MapVectorItemCollection clusterRepresentatives = CreateItemsCollection();
for (int i = 0; i < clusters.Count; ++i) {
Cluster cluster = clusters[i];
MapDot representative = new MapDot() { Location = new GeoPoint(cluster.CenterPoint.Y, cluster.CenterPoint.X), Size = 100 };
for (int j = 0; j < cluster.Items.Count; ++j)
representative.ClusteredItems.Add(cluster.Items[j] as MapItem);
clusterRepresentatives.Add(representative);
}
for (int i = 0; i < nonLocalizableItems.Count; ++i)
clusterRepresentatives.Add(nonLocalizableItems[i]);
return clusterRepresentatives;
}
static List<Cluster> Arrange(List<Cluster> clusters) {
List<Cluster> arrangedClusters = new List<Cluster>();
for (int i = 0; i < clusters.Count; ++i) {
Cluster cluster = clusters[i];
AssignClosest(cluster, clusters);
// Inserts depending on distance to closest.
Insert(arrangedClusters, cluster);
}
return arrangedClusters;
}
static void AssignClosest(Cluster cluster, List<Cluster> clusters) {
if (clusters.Count < 2) throw new ArgumentOutOfRangeException("Clusters count should be larger than 2.");
Cluster distancableCluster = clusters[0];
if (distancableCluster == cluster)
distancableCluster = clusters[1];
cluster.ClosestCluster = distancableCluster;
for (int i = 0; i < clusters.Count; ++i) {
distancableCluster = clusters[i];
if (distancableCluster == cluster) continue;
double distance = cluster.DistanceTo(distancableCluster);
if (distance < cluster.DistanceToClosest)
cluster.ClosestCluster = distancableCluster;
}
}
static void Insert(List<Cluster> clusters, Cluster cluster) {
for (int i = 0; i < clusters.Count; ++i) {
if (clusters[i].DistanceToClosest > cluster.DistanceToClosest) {
clusters.Insert(i, cluster);
return;
}
}
clusters.Add(cluster);
}
static void MergeCloserstClusters(ref List<Cluster> clusters) {
if (clusters.Count < 2) throw new ArgumentOutOfRangeException("Clusters count should be larger than 2.");
Cluster cluster1 = clusters[0];
Cluster cluster2 = cluster1.ClosestCluster;
clusters.RemoveAt(0);
clusters.Remove(cluster2);
Cluster newCluster = Cluster.Merge(cluster1, cluster2);
clusters.Add(newCluster);
clusters = Arrange(clusters);
}
}
struct MapPoint {
public MapPoint(double x, double y) {
X = x;
Y = y;
}
public double X { get; set; }
public double Y { get; set; }
}
class Cluster {
MapPoint centerPoint;
List<ISupportCoordLocation> items;
Cluster closestCluster;
double distanceToClosest;
public Cluster(List<ISupportCoordLocation> items) {
this.items = items;
centerPoint = CalculateCenterPoint(items);
}
public static Cluster Initialize(ISupportCoordLocation item) {
List<ISupportCoordLocation> items = new List<ISupportCoordLocation>();
items.Add(item);
return new Cluster(items);
}
public MapPoint CenterPoint { get { return this.centerPoint; } }
public List<ISupportCoordLocation> Items { get { return this.items; } }
public Cluster ClosestCluster {
get { return this.closestCluster; }
set {
this.closestCluster = value;
distanceToClosest = DistanceTo(closestCluster);
}
}
public double DistanceToClosest { get { return distanceToClosest; } }
public double DistanceTo(Cluster h) {
return Math.Sqrt((h.CenterPoint.X - CenterPoint.X) * (h.CenterPoint.X - CenterPoint.X) +
(h.CenterPoint.Y - CenterPoint.Y) * (h.CenterPoint.Y - CenterPoint.Y));
}
public static Cluster Merge(Cluster cluster1, Cluster cluster2) {
List<ISupportCoordLocation> newItems = new List<ISupportCoordLocation>(cluster1.Items);
newItems.AddRange(cluster2.Items);
return new Cluster(newItems);
}
public static MapPoint CalculateCenterPoint(List<ISupportCoordLocation> items) {
double meanX = 0;
double meanY = 0;
foreach (ISupportCoordLocation item in items) {
meanX += item.Location.GetX();
meanY += item.Location.GetY();
}
meanX /= items.Count;
meanY /= items.Count;
return new MapPoint(meanX, meanY);
}
}
}
Imports DevExpress.Map
Imports DevExpress.Xpf.Map
Imports System
Imports System.Collections.Generic
Namespace CustomClustererSample
Friend Class CureClusterer
Inherits MapClustererBase
Private currentItems As MapVectorItemCollection
Public Overrides ReadOnly Property Items() As MapVectorItemCollection
Get
Return currentItems
End Get
End Property
Public Property ClusterCount() As Integer
Public Overrides Sub Clusterize(ByVal sourceItems As MapVectorItemCollection, ByVal viewport As MapViewport, ByVal sourceChanged As Boolean)
If sourceChanged Then
currentItems = ClusterizeImpl(sourceItems)
Adapter.OnClustered()
End If
End Sub
Protected Overrides Function CreateObject() As MapDependencyObject
Return New CureClusterer()
End Function
Private Function ClusterizeImpl(ByVal sourceItems As MapVectorItemCollection) As MapVectorItemCollection
' Separate localizable and non localizable items.
Dim nonLocalizableItems As New List(Of MapItem)()
Dim clusters As New List(Of Cluster)()
For Each item As MapItem In sourceItems
Dim localizableItem As ISupportCoordLocation = TryCast(item, ISupportCoordLocation)
If localizableItem IsNot Nothing Then
clusters.Add(Cluster.Initialize(localizableItem))
Else
nonLocalizableItems.Add(item)
End If
Next item
' Arrange initial clusters in increasing order of distance to a closest cluster.
clusters = Arrange(clusters)
' Aggregate localizable items.
Do While clusters.Count > ClusterCount
MergeCloserstClusters(clusters)
Loop
' Convert internal cluster helpers to Map items.
Dim clusterRepresentatives As MapVectorItemCollection = CreateItemsCollection()
For i As Integer = 0 To clusters.Count - 1
Dim cluster_Renamed As Cluster = clusters(i)
Dim representative As New MapDot() With {.Location = New GeoPoint(cluster_Renamed.CenterPoint.Y, cluster_Renamed.CenterPoint.X), .Size = 100}
For j As Integer = 0 To cluster_Renamed.Items.Count - 1
representative.ClusteredItems.Add(TryCast(cluster_Renamed.Items(j), MapItem))
Next j
clusterRepresentatives.Add(representative)
Next i
For i As Integer = 0 To nonLocalizableItems.Count - 1
clusterRepresentatives.Add(nonLocalizableItems(i))
Next i
Return clusterRepresentatives
End Function
Private Shared Function Arrange(ByVal clusters As List(Of Cluster)) As List(Of Cluster)
Dim arrangedClusters As New List(Of Cluster)()
For i As Integer = 0 To clusters.Count - 1
Dim cluster_Renamed As Cluster = clusters(i)
AssignClosest(cluster_Renamed, clusters)
' Inserts depending on distance to closest.
Insert(arrangedClusters, cluster_Renamed)
Next i
Return arrangedClusters
End Function
Private Shared Sub AssignClosest(ByVal cluster_Renamed As Cluster, ByVal clusters As List(Of Cluster))
If clusters.Count < 2 Then
Throw New ArgumentOutOfRangeException("Clusters count should be larger than 2.")
End If
Dim distancableCluster As Cluster = clusters(0)
If distancableCluster Is cluster_Renamed Then
distancableCluster = clusters(1)
End If
cluster_Renamed.ClosestCluster = distancableCluster
For i As Integer = 0 To clusters.Count - 1
distancableCluster = clusters(i)
If distancableCluster Is cluster_Renamed Then
Continue For
End If
Dim distance As Double = cluster_Renamed.DistanceTo(distancableCluster)
If distance < cluster_Renamed.DistanceToClosest Then
cluster_Renamed.ClosestCluster = distancableCluster
End If
Next i
End Sub
Private Shared Sub Insert(ByVal clusters As List(Of Cluster), ByVal cluster_Renamed As Cluster)
Dim i As Integer = 0
Do While i < clusters.Count
If clusters(i).DistanceToClosest > cluster_Renamed.DistanceToClosest Then
clusters.Insert(i, cluster_Renamed)
Return
End If
i += 1
Loop
clusters.Add(cluster_Renamed)
End Sub
Private Shared Sub MergeCloserstClusters(ByRef clusters As List(Of Cluster))
If clusters.Count < 2 Then
Throw New ArgumentOutOfRangeException("Clusters count should be larger than 2.")
End If
Dim cluster1 As Cluster = clusters(0)
Dim cluster2 As Cluster = cluster1.ClosestCluster
clusters.RemoveAt(0)
clusters.Remove(cluster2)
Dim newCluster As Cluster = Cluster.Merge(cluster1, cluster2)
clusters.Add(newCluster)
clusters = Arrange(clusters)
End Sub
End Class
Friend Structure MapPoint
Public Sub New(ByVal x As Double, ByVal y As Double)
Me.X = x
Me.Y = y
End Sub
Public Property X() As Double
Public Property Y() As Double
End Structure
Friend Class Cluster
Private centerPoint_Renamed As MapPoint
Private items_Renamed As List(Of ISupportCoordLocation)
Private closestCluster_Renamed As Cluster
Private distanceToClosest_Renamed As Double
Public Sub New(ByVal items As List(Of ISupportCoordLocation))
Me.items_Renamed = items
centerPoint_Renamed = CalculateCenterPoint(items)
End Sub
Public Shared Function Initialize(ByVal item As ISupportCoordLocation) As Cluster
Dim items_Renamed As New List(Of ISupportCoordLocation)()
items_Renamed.Add(item)
Return New Cluster(items_Renamed)
End Function
Public ReadOnly Property CenterPoint() As MapPoint
Get
Return Me.centerPoint_Renamed
End Get
End Property
Public ReadOnly Property Items() As List(Of ISupportCoordLocation)
Get
Return Me.items_Renamed
End Get
End Property
Public Property ClosestCluster() As Cluster
Get
Return Me.closestCluster_Renamed
End Get
Set(ByVal value As Cluster)
Me.closestCluster_Renamed = value
distanceToClosest_Renamed = DistanceTo(closestCluster_Renamed)
End Set
End Property
Public ReadOnly Property DistanceToClosest() As Double
Get
Return distanceToClosest_Renamed
End Get
End Property
Public Function DistanceTo(ByVal h As Cluster) As Double
Return Math.Sqrt((h.CenterPoint.X - CenterPoint.X) * (h.CenterPoint.X - CenterPoint.X) + (h.CenterPoint.Y - CenterPoint.Y) * (h.CenterPoint.Y - CenterPoint.Y))
End Function
Public Shared Function Merge(ByVal cluster1 As Cluster, ByVal cluster2 As Cluster) As Cluster
Dim newItems As New List(Of ISupportCoordLocation)(cluster1.Items)
newItems.AddRange(cluster2.Items)
Return New Cluster(newItems)
End Function
Public Shared Function CalculateCenterPoint(ByVal items As List(Of ISupportCoordLocation)) As MapPoint
Dim meanX As Double = 0
Dim meanY As Double = 0
For Each item As ISupportCoordLocation In items
meanX += item.Location.GetX()
meanY += item.Location.GetY()
Next item
meanX /= items.Count
meanY /= items.Count
Return New MapPoint(meanX, meanY)
End Function
End Class
End Namespace