Trop de pictos sur votre carte ?

13.03.2012

Un des frameworks les plus utilisés dans le kit de développement iOS est certainement Map Kit. Comme vous le savez sans doute, celui-ci propose une solution simple pour embarquer et annoter une carte dans une application. Dans cet article, nous vous présentons une méthode innovante pour tirer au mieux parti des possibilités de ce framework.

Utilisation de Map Kit

En général l’utilisation de Map Kit se résume à quelques étapes :

  1. Instancier une annotation (un objet modèle qui implémente le protocole MKAnnotation)
  2. Ajouter notre annotation à la carte (une instance de MKMapView)
  3. Décrire au délégué de la carte ce à quoi notre annotation va ressembler une fois sur la carte

Tout ceci est plutôt simple. Malheureusement cette approche n’est plus valide lorsque nous avons à afficher des centaines d’annotations. Ceci pour deux raisons :

  • Les performances seront mauvaises (affichage saccadé de la carte)
  • Le résultat sera difficile à utiliser (la plupart des annotations se recouvreront entre elles, ce qui rendra difficile leur sélection)

Récemment, lorsque nous avons développé une application manipulant un réseau ferroviaire, nous avons eu à afficher plusieurs milliers de gares sur une carte. Ayant estimé que l’implémentation décrite ci-dessus n’était pas assez performante, nous avons réfléchi à la meilleure solution nous permettant d’afficher ces annotations. Nous vous proposons notre réponse.

La clusterisation

La solution a pour nom clusterisation. Le concept est simple : il s’agit de regrouper des annotations (par exemple des photos, ou ici des gares) qui sont proches les unes des autres. Mais qu’appelle-t-on proche ? C’est tout le problème.

En fait, vous avez sans doute déjà utilisé de la clusterisation sans le savoir : vous pouvez le trouver au sein de l’application Photos embarquée dans votre iPhone.

Malheureusement pour nous, Apple n’a pas estimé qu’il était bon d’exposer cette fonctionnalité dans une API publique. Nous sommes donc livrés à nous-mêmes pour résoudre notre problème !

État de l’art

On trouve quelques implémentations de clusterisation sur Internet. Certaines sont payantes (Superpin ou DTClusterMaker), et d’autres sont des projets open source (REVClusterMap). Bien que celles-ci pourraient être acceptables dans certains cas, aucune d’entre elles ne nous a vraiment satisfait.

La clusterisation est un champ de recherche encore actif, et de nombreuses solutions ont déjà été proposées. Cependant, nous nous sommes fixé trois contraintes :

  • la complexité de l’algorithme devait rester faible afin de permettre un affichage rapide de la carte ainsi qu’une grande réactivité lors du zoom ou du déplacement sur la carte.
  • nous voulions être capables d’effectuer des transitions animées lorsqu’une annotation se divise ou quand plusieurs annotations se regroupent en une seule (comme dans l’application Photos). L’algorithme retenu doit donc pouvoir donner des résultats prévisibles et reproductibles (le hasard ne doit donc pas rentrer en jeu lors du choix des clusters).
  • nous voulions que la répartition des clusters d’annotations reflète la densité des annotations qu’ils représentent (pas d’effet grille comme dans Superpin (à gauche) ou REVClusterMap (à droite)).

Effet de grille dans Superpin et dans REVClusterMap

Discussion

Nous avons envisagé plusieurs approches pendant notre recherche :

  • Méthode parfaite (algorithme naïf) : nous avons commencé par évaluer deux à deux la distance entre toutes les annotations afin de minimiser celle-ci. La complexité de l’algorithme résultant était bien trop mauvaise pour être retenue.
  • K-means : l’algorithme des k-moyennes (ou k-means en anglais) est une méthode classique de clusterisation, utilisée dans de nombreux domaines dont les statistiques et le traitement d’image. Son implémentation habituelle est un simple algorithme itératif. Malheureusement, celui-ci est coûteux en ressources de calcul et il s’est avéré trop lent pour nos appareils mobiles sous iOS. Par ailleurs, cet algorithme n’est pas déterministe (il y a une composante de hasard), et nous ne pouvons donc pas effectuer d’animation au zoom ou au déplacement sur la carte.
  • Quadtree : Utiliser une structure en quadtree est également une approche intéressante (utilisée par exemple dans Superpin). L’idée derrière cette méthode est de construire un arbre où chaque nœud correspond à une division d’une portion de l’espace en quatre parties. Cette étape peut être effectuée dans une étape de pré-calcul potentiellement longue. La mise à jour des clusters d’annotations sur la carte au moindre déplacement se fait par un simple parcours de l’arbre et est donc très performant. Un gros problème subsiste : les clusters forment une grille comme nous l’avons vu plus haut.

Notre implémentation

Nous avons finalement retenu une variante du quadtree élaborée par nos soins. Nous utilisons pour cela un k-d tree, qui dans le cas présent consiste en un arbre binaire où l’espace bi-dimensionnel est arbitrairement partitionné en deux de manière récursive par une ligne. L’intérêt de cette structure de données est que nous décidons nous-mêmes de la répartition des clusters de part et d’autre de la ligne de séparation. Ainsi, on pourrait choisir de construire un arbre parfaitement équilibré en gardant le même nombre d’annotations de part et d’autre de la ligne de séparation, mais ce n’est pas le résultat attendu. À la place, voici ce que nous avons retenu pour chaque étape de la construction :

  • Nous effectuons une Analyse en Composantes Principales pour estimer le vecteur principal qui décrit la distribution de nos annotations.
  • Nous calculons la moyenne des coordonnées des annotations et obtenons ainsi leur barycentre.
  • Pour chaque annotation (x,y), nous calculons le produit scalaire entre le vecteur principal p et le vecteur u(x-xMoyenne, y-yMoyenne), xMoyenne et yMoyenne étant les coordonnées de notre barycentre. Le signe de ce produit scalaire nous donne alors directement le demi-espace auquel va appartenir notre point.

Une fois le k-d tree construit, il ne nous reste plus qu’à parcourir l’arbre à la recherche des clusters correspondant à la région de la carte que nous allons vouloir afficher. Nous effectuons sur cet arbre un parcours en largeur à travers tous les clusters contenus dans la région considérée, jusqu’à ce que nous atteignions un nombre maximal donné de clusters exposé comme paramètre de notre API. Ainsi, à chaque zoom ou déplacement sur la carte, nous n’afficherons jamais plus d’annotations que nécessaire. Par ailleurs, nous obtenons un sympathique effet de regroupement ou de division des annotations entre elles, car notre structure est parfaitement cohérente à tous les niveaux de l’arbre.

Conclusion

Et voilà ! Retenons de tout ceci que le SDK iOS n’attend qu’une chose : que nous expérimentions avec et que nous repoussions ses limites. C’est un vrai défi (mais également un grand plaisir) de chercher à étendre les possibilités de tous les frameworks que nous avons sous la main.

Si vous souhaitez voir notre clusterisation en action, vous pouvez télécharger l’application gratuite pour laquelle nous avons développé cette méthode : RailTime . Vous pouvez voir dans la capture d’écran ci-dessous comme les gares et les clusters des gares reproduisent la forme des lignes de train. Un quadtree ne nous aurait pas permis d’obtenir un tel résultat.

Nous espérons que ce petit article de recherche vous a plu et que vous retiendrez quelques uns des aspects techniques présentés. Si c’est le cas, n’hésitez pas à réagir à ce post sur Twitter : notre compte est @applidium.

[MISE À JOUR] Nous avons publié notre bibliothèque sous licence BSD !