How to: Implement a Custom Clusterer

• Nov 13, 2018
• 10 minutes to read

To implement a custom clusterer, design a class implementing the IClusterer interface and its IClusterer.Clusterize and IClusterer.SetOwner abstract methods, and IClusterer.Items and IClusterer.IsBusyproperties.

In this example, the CURE clustering method is implemented. Note that it has a high algorithmic complexity.

Note

• The owner adapter’s IMapDataAdapter.OnClustered method should be called to notify the Adapter that clustering is finished.
• When creating a cluster representative collection, send an owner as the constructor argument.

Form1.cs

using DevExpress.XtraMap;
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Windows.Forms;
using System.Xml.Linq;

namespace CustomClustererSample {
    public partial class Form1 : Form {
        VectorItemsLayer VectorLayer { get { return (VectorItemsLayer)map.Layers["VectorLayer"]; } }
        ListSourceDataAdapter DataAdapter { get { return (ListSourceDataAdapter)VectorLayer.Data; } }

        public Form1() {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e) {
            VectorLayer.DataLoaded += (obj, args) => { map.ZoomToFitLayerItems(); };

            DataAdapter.DataSource = LoadData();
            DataAdapter.Clusterer = new CureClusterer();
        }

        List<Tree> LoadData() {
            List<Tree> trees = new List<Tree>();
            XDocument doc = XDocument.Load("Data\\treesCl.xml");
            foreach (XElement xTree in doc.Element("RowSet").Elements("Row"))
                trees.Add(new Tree {
                    Latitude = Convert.ToDouble(xTree.Element("lat").Value, CultureInfo.InvariantCulture),
                    Longitude = Convert.ToDouble(xTree.Element("lon").Value, CultureInfo.InvariantCulture),
                    LocationName = xTree.Element("location").Value
                });
            return trees;
        }
    }
}

CureClusterer.cs

using DevExpress.Map;
using DevExpress.XtraMap;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace CustomClustererSample {
    class CureClusterer : IClusterer {
        bool isBusy;
        int clusterCount = 10;
        MapItemCollection currentItems;
        IMapDataAdapter owner;

        public CureClusterer() {
            isBusy = false;
        }

        public bool IsBusy {
            get {
                return isBusy;
            }
        }

        public MapItemCollection Items {
            get {
                return currentItems;
            }
        }

        public int ClusterCount {
            get { return clusterCount; }
            set {
                if (value < 1) throw new ArgumentOutOfRangeException("The ClusterCount should be larger than 1.");
                ClusterCount = value;
            }
        }

        public void Clusterize(IEnumerable<MapItem> sourceItems, MapViewport viewport, bool sourceChanged) {
            Thread clusteringThread = new Thread(() => {
                isBusy = true;
                if (sourceChanged) {
                    currentItems = ClusterizeImpl(sourceItems);
                    owner.OnClustered();
                }
                isBusy = false;
            });
            clusteringThread.Start();
        }

        public void SetOwner(IMapDataAdapter owner) {
            this.owner = owner;
        }

        MapItemCollection ClusterizeImpl(IEnumerable<MapItem> 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.
            MapItemCollection clusterRepresentatives = new MapItemCollection(owner);
            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 };
                representative.ClusteredItems = cluster.Items.Select(item => item as MapItem).ToList();
                representative.TitleOptions.Pattern = representative.ClusteredItems.Count.ToString();
                clusterRepresentatives.Add(representative);
            }
            clusterRepresentatives.AddRange(nonLocalizableItems);
            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);
        }
    }

    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);
        }
    }
}

Tree.cs

using System;

namespace CustomClustererSample {
    class Tree {
        string locationName;

        public Tree() {
            locationName = "";
        }
        public double Latitude { get; set; }
        public double Longitude { get; set; }
        public string LocationName {
            get { return this.locationName; }
            set {
                if (value == null) throw new ArgumentNullException("LocationName");
                if (value.Equals(this.locationName)) return;
                this.locationName = value;
            }
        }
    }
}

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CustomClustererSample {
    static class Program {
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        [STAThread]
        static void Main() {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new Form1());
        }
    }
}

Tree.vb

Imports System

Namespace CustomClustererSample
    Friend Class Tree

        Private locationName_Renamed As String

        Public Sub New()
            locationName_Renamed = ""
        End Sub
        Public Property Latitude() As Double
        Public Property Longitude() As Double
        Public Property LocationName() As String
            Get
                Return Me.locationName_Renamed
            End Get
            Set(ByVal value As String)
                If value Is Nothing Then
                    Throw New ArgumentNullException("LocationName")
                End If
                If value.Equals(Me.locationName_Renamed) Then
                    Return
                End If
                Me.locationName_Renamed = value
            End Set
        End Property
    End Class
End Namespace

Form1.vb

Imports DevExpress.XtraMap
Imports System
Imports System.Collections.Generic
Imports System.Globalization
Imports System.Windows.Forms
Imports System.Xml.Linq

Namespace CustomClustererSample
    Partial Public Class Form1
        Inherits Form

        Private ReadOnly Property VectorLayer() As VectorItemsLayer
            Get
                Return CType(map.Layers("VectorLayer"), VectorItemsLayer)
            End Get
        End Property
        Private ReadOnly Property DataAdapter() As ListSourceDataAdapter
            Get
                Return CType(VectorLayer.Data, ListSourceDataAdapter)
            End Get
        End Property

        Public Sub New()
            InitializeComponent()
        End Sub

        Private Sub Form1_Load(ByVal sender As Object, ByVal e As EventArgs) Handles Me.Load
            AddHandler VectorLayer.DataLoaded, Sub(obj, args)
                map.ZoomToFitLayerItems()
            End Sub

            DataAdapter.DataSource = LoadData()
            DataAdapter.Clusterer = New CureClusterer()
        End Sub

        Private Function LoadData() As List(Of Tree)
            Dim trees As New List(Of Tree)()
            Dim doc As XDocument = XDocument.Load("Data\treesCl.xml")
            For Each xTree As XElement In doc.Element("RowSet").Elements("Row")
                trees.Add(New Tree With { _
                    .Latitude = Convert.ToDouble(xTree.Element("lat").Value, CultureInfo.InvariantCulture), _
                    .Longitude = Convert.ToDouble(xTree.Element("lon").Value, CultureInfo.InvariantCulture), _
                    .LocationName = xTree.Element("location").Value _
                })
            Next xTree
            Return trees
        End Function
    End Class
End Namespace

CureClusterer.vb

Imports DevExpress.Map
Imports DevExpress.XtraMap
Imports System
Imports System.Collections.Generic
Imports System.Linq
Imports System.Threading

Namespace CustomClustererSample
    Friend Class CureClusterer
        Implements IClusterer


        Private isBusy_Renamed As Boolean

        Private clusterCount_Renamed As Integer = 10
        Private currentItems As MapItemCollection
        Private owner As IMapDataAdapter

        Public Sub New()
            isBusy_Renamed = False
        End Sub

        Public ReadOnly Property IsBusy() As Boolean Implements IClusterer.IsBusy
            Get
                Return isBusy_Renamed
            End Get
        End Property

        Public ReadOnly Property Items() As MapItemCollection Implements IClusterer.Items
            Get
                Return currentItems
            End Get
        End Property

        Public Property ClusterCount() As Integer
            Get
                Return clusterCount_Renamed
            End Get
            Set(ByVal value As Integer)
                If value < 1 Then
                    Throw New ArgumentOutOfRangeException("The ClusterCount should be larger than 1.")
                End If
                clusterCount_Renamed = value
            End Set
        End Property

        Public Sub Clusterize(ByVal sourceItems As IEnumerable(Of MapItem), ByVal viewport As MapViewport, ByVal sourceChanged As Boolean) Implements IClusterer.Clusterize
            Dim clusteringThread As Thread = New Thread(Sub()
                                                            isBusy_Renamed = True
                                                            If sourceChanged Then
                                                                currentItems = ClusterizeImpl(sourceItems)
                                                                owner.OnClustered()
                                                            End If
                                                            isBusy_Renamed = False
                                                        End Sub)
            clusteringThread.Start()
        End Sub

        Public Sub SetOwner(ByVal owner As IMapDataAdapter) Implements IClusterer.SetOwner
            Me.owner = owner
        End Sub

        Private Function ClusterizeImpl(ByVal sourceItems As IEnumerable(Of MapItem)) As MapItemCollection
            ' 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 New MapItemCollection(owner)
            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 _
                }
                representative.ClusteredItems = cluster_Renamed.Items.Select(Function(item) TryCast(item, MapItem)).ToList()
                representative.TitleOptions.Pattern = representative.ClusteredItems.Count.ToString()
                clusterRepresentatives.Add(representative)
            Next i
            clusterRepresentatives.AddRange(nonLocalizableItems)
            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)()
            Dim i As Integer = 0
            Do While i < clusters.Count

                Dim cluster_Renamed As Cluster = clusters(i)
                AssignClosest(cluster_Renamed, clusters)
                ' Inserts depending on distance to closest.
                Insert(arrangedClusters, cluster_Renamed)
                i += 1
            Loop
            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 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

Program.vb

Imports System
Imports System.Collections.Generic
Imports System.Linq
Imports System.Threading.Tasks
Imports System.Windows.Forms

Namespace CustomClustererSample
    Friend NotInheritable Class Program

        Private Sub New()
        End Sub

        ''' <summary>
        ''' The main entry point for the application.
        ''' </summary>
        <STAThread> _
        Shared Sub Main()
            Application.EnableVisualStyles()
            Application.SetCompatibleTextRenderingDefault(False)
            Application.Run(New Form1())
        End Sub
    End Class
End Namespace