I. L'algo▲
Dans les faits, l'algo est relativement simple.
Tout d'abord, on ne prend que la partie visible de la carte, puis on découpe cette zone en petites sous-parties (des carrés), avant de regrouper les points présents ensemble dans une petite zone.
I-A. De quoi a-t-on besoin ?▲
On veut afficher sur les cartes des objets qui ont une position. On va donc générer un objet que l'on nommera ItemObjet, et qui aura besoin de connaitre un objet Location :
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; }
}Sur la carte, on affichera une collection d'ItemObjet, pour faciliter l'écriture, j'ai décidé de créer un objet ItemCollection :
public class ItemCollection : ObservableCollection<ItemObjet>
{
}Comme je l'ai dit tout à l'heure, on ne travaillera que sur la partie visible de la carte, on a donc besoin de définir un objet pour les frontières :
public class Bounds
{
public double East { get; set; }
public double West { get; set; }
public double North { get; set; }
public double South { get; set; }
}De plus, on a besoin d'un objet qui définit le pas à utiliser lors du zoom. Le pas sera utilisé pour découper la carte en plusieurs petits carrés ayant pour côté la valeur du pas.
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;
}J'anticipe un peu, mais on aura aussi besoin d'un outil pour nous permettre de savoir si un point est à l'intérieur du rectangle défini par les frontières. Pour cela, j'ai fait le choix d'utiliser une méthode d'extension :
public static bool IsPointInside(this Location location, Bounds bound)
{
bool isInside = false;
if (location != null)
{
if (bound.East < bound.West)
{
//la longitude de la frontière ouest est supérieure à celle de la frontière est
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
{
//la longitude de la frontière est est supérieure à celle de la frontière ouest
if (bound.West <= location.Longitude && location.Longitude <= bound.East)
{
if (bound.South <= location.Latitude && location.Latitude <= bound.North)
{
isInside = true;
}
}
}
}
return isInside;
}Il y a ici un point de complexité. Dans les faits, il est possible de faire défiler la carte sur l'axe des longitudes à l'infini. Cela peut provoquer un cas particulier où la longitude ouest est supérieure à la longitude est. Ce qui en général n'est pas le cas.
I-B. Clusteritem, la classe qui travaille !▲
C'est ici que la logique de clusterisation a lieu. Cette classe expose une série de DependencyProperties qui permettent d'utiliser l'objet dans le XAML.
I-B-1. Quelles sont les propriétés accessibles ?▲
Boundaries - permet de définir les frontières visibles de la carte.
CenterPoint - définit le centre de la carte.
Collection - c'est dans cette collection que la liste de tous les points que l'on veut montrer seront stockés.
CurrentShownItem - la liste d'items qui seront visibles sur la carte (que ce soit un point unique ou un point cluster).
ReloadPoint - permet de forcer le rechargement de la carte.
Zoom - permet de connaître le zoom de la carte (amplitude de 1-20).
ListPas - une collection qui permet, pour une valeur de zoom donnée, d'associer un pas pour le découpage de la zone.
I-B-2. Quelles actions lancent le process ?▲
Il y a deux actions qui permettent de lancer le processus de clusterisation :
- l'ajout et la suppression d'items dans la liste d'items ;
- le changement de zoom ou de centre sur la carte.
I-B-2-a. Ajout et suppression d'items▲
La propriété Collection est de type ItemCollection. Ce type hérite de ObservableCollection. Pour savoir si des items ont été ajoutés ou supprimés, on écoutera l'événement CollectionChanged. Il faut cependant faire attention, cet événement est levé à chaque modification de la collection. Dans le cas de l'ajout de N éléments dans la collection, on ne veut être notifié que lors de la fin de l'ajout. J'utilise pour cela un timer qui se déclenchera toutes les 100 ms :
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);
}
}I-B-2-b. Changement de zoom ou de centre▲
Pour le moment, dans ces deux cas, l'utilisateur doit forcer la recharge des points via la propriété ReloadPoint.
I-C. Le traitement▲
Celui-ci doit être séparé en deux. Dans les faits, il existe deux types de recharge de points.
Le premier est dû à un changement de zoom (le zoom doit changer de plus d'une unité de zoom). Dans ce cas, la carte est nettoyée et on recalcule les points.
Le deuxième est dû à un zoom inférieur à une unité de zoom ou à un changement de centre. Dans ce cas-ci, on ne va dessiner que les nouveaux points et cacher les points qui passent hors frontières.
I-C-1. Zoom▲
Dans un premier temps nettoyage de la carte :
CurrentShownItem.Clear();La nouvelle valeur du zoom va être notifiée.
Ensuite on va générer les nouveaux points avec la méthode :
GenerateWithZoomChange(collection)Cette méthode va d'abord faire un travail sur les bornes min et max des longitudes.
Comme vu précédemment, il peut arriver que la valeur de la longitude ouest soit supérieure à la longitude est. Dans ce cas, un boolean sera utilisé pour savoir comment doit continuer le travail (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);
}
}
});
}On peut voir ici que la génération des points se fait via deux boucles for imbriquées.
La méthode RunLogicCluster() calcule la valeur moyenne des longitudes et des latitudes des points présents dans la petite zone définie et ajoute un point cluster. S'il n'y a qu'un seul point, alors on l'ajoute directement.
Les points sont ajoutés dans la collection CurrentShownItem.
Dans le cas où le zoom est maximum et qu'il y aurait encore des points cluster, on ne demande pas le dessin d'un cluster, mais on dessine tous les points présents.
I-C-2. Déplacement du centre▲
Dans l'ensemble, le traitement est le même que précédemment, la seule différence est l'ajout d'une étape qui permet de définir la nouvelle zone visible et de cacher les points qui disparaissent de cette zone.
List<ItemObjet> itemToDelete = new List<ItemObjet>();
// on veut les items qui sont seulement présents dans la nouvelle zone
// pas les éléments présents dans l'intersection
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);La suite est la même. Dans les deux cas, à la fin des traitements on va sauvegarder la valeur courante de la fenêtre visible.
II. Utilisation▲
Cet algo est utilisable autant sur Windows 8.1 que sur Windows Phone 8.1 cela grâce à l'utilisation des Portable librairies.
II-A. Windows 8.1▲
J'ai défini l'outil de cluster dans le code XAML avec une carte de type Bing map. Ainsi que des DataTemplate pour les clusterPushPin et les 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>L'abonnement à l'événement ViewChangeEnded est suffisant pour recevoir une notification lorsque la carte a subi une modification (zoom ou centre). L'événement devra être traité de la façon suivante :
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));II-B. 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>Dans le cas de Windows Phone, l'abonnement à CenterChanged est suffisant. En effet, même lors d'un zoom, dans la plus grande majorité des cas, le centre de la carte changera.
Comme dans le cas d'ajout d'items dans une ObservableCollection, cet événement est levé tout au long de la modification et pas uniquement lorsque le changement prend fin. De la même manière, j'ai utilisé ici un DispatcherTimer.
Ensuite le traitement devient le même !
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));III. Conclusion▲
L'utilisation d'une carte dans les applications peut être une bonne chose pour permettre facilement à l'utilisateur de localiser des points d'intérêt. Cependant, une carte trop chargée est illisible.
Le clustering de points devient donc une nécessité. De plus, avec la possibilité de portabilité du code, une solution « universelle » permet un réel gain de temps sur le temps de travail.
Toutes les sources de cet article sont disponibles à cette adresse.
IV. Remerciements▲
Cet article a été publié avec l'aimable autorisation de SOAT, société d'expertise et de conseil en informatique.
Nous tenons à remercier Claude Leloup pour la relecture orthographique et Marie-Hélène Delacroix pour la mise au gabarit.
