Les marqueurs sont une bonne chose. Utile en quantité raisonnable. Quand il y en a trop, les bénéfices disparaissent. Que faire si vous souhaitez marquer des résultats de recherche sur la carte, dans laquelle des dizaines de milliers d'objets? Dans l'article, je vais vous expliquer comment résoudre ce problème sur une carte WebGL sans compromettre son apparence et ses performances.

Contexte

En 2016, 2GIS a lancé son premier projet WebGL, Floors: 3D floor plans of buildings.

Planchers du centre commercial Novosibirsk Aura

Immédiatement après la sortie de Floors, notre équipe a commencé à développer un moteur cartographique tridimensionnel à part entière sur WebGL. Le moteur a été développé conjointement avec la nouvelle version 2gis.ru et est maintenant en version bêta publique .

Carré rouge dessiné sur WebGL. Les plans de construction sont désormais intégrés directement dans la carte.

Tâche de généralisation de signature

Quiconque veut écrire son propre moteur de carte sera tôt ou tard confronté au problème de placer des signatures sur la carte. Il y a beaucoup d'objets sur la carte, et il est impossible de signer chacun pour que les signatures ne se chevauchent pas.

Que se passera-t-il si à Novossibirsk tous les objets sont signés en même temps

Pour résoudre ce problème, une généralisation des signatures est requise. La généralisation au sens général est la transformation des données cartographiques afin qu'elles conviennent à un affichage à petite échelle. Cela peut être fait par différentes méthodes. Pour les signatures, la méthode de sélection est généralement utilisée: à partir du nombre total, un sous-ensemble des signatures de priorité la plus élevée qui ne se chevauchent pas est sélectionné.

La priorité de la signature est déterminée par son type, ainsi que l'échelle actuelle de la carte. Par exemple, à petite échelle, les signatures des villes et des pays sont nécessaires, et à grande échelle, les signatures routières et les numéros de maison deviennent beaucoup plus importants. Souvent, la priorité du nom d'une colonie est déterminée par la taille de sa population. Plus elle est grande, plus la signature est importante.

La généralisation est requise non seulement pour les signatures, mais aussi pour les marqueurs qui marquent les résultats de la recherche sur la carte. Par exemple, lors de la recherche de «magasin» à Moscou, il y a plus de 15 000 résultats. Les marquer tous sur la carte d'un seul coup est évidemment une mauvaise idée.

Tous les magasins de Moscou sur la carte. Il n'y a aucun moyen de se passer de la généralisation

Toute interaction de l'utilisateur avec la carte (déplacement, zoom, rotation et inclinaison) entraîne un changement de position des marqueurs sur l'écran, vous devez donc être en mesure de recalculer la généralisation à la volée. Par conséquent, cela doit être rapide.

Dans cet article, en utilisant l'exemple de la généralisation des marqueurs, je vais montrer différentes façons de résoudre ce problème, qui ont été utilisées à différents moments dans nos projets.

Approche générale de la généralisation

1. Projetez chaque marqueur sur le plan de l'écran et calculez pour lui une limite - la zone rectangulaire qu'il occupe sur l'écran.
2. Trier les marqueurs par priorité.
3. Examinez séquentiellement chaque marqueur et placez-le sur l'écran s'il ne recoupe pas d'autres marqueurs placés devant lui.

Avec le point 1, tout est clair - ce n'est qu'un calcul. Avec le point 2, nous avons également eu de la chance: la liste des marqueurs qui nous vient du backend est déjà triée par priorité par les algorithmes de recherche. Les résultats les plus pertinents susceptibles d'intéresser l'utilisateur se trouvent en haut des résultats.

Le principal problème se trouve au paragraphe 3: le temps de calcul de la généralisation peut dépendre grandement de la façon dont elle est mise en œuvre.

Pour rechercher des intersections entre les marqueurs, nous avons besoin d'une structure de données qui:

1. Stocke les limites des marqueurs ajoutés à l'écran.
2. A une méthode d' insert(marker) pour ajouter un marqueur à l'écran.
3. Il a une méthode de collides(marker) pour vérifier le marqueur pour l'intersection avec ceux déjà ajoutés à l'écran.

Considérez plusieurs implémentations de cette structure. Tous les autres exemples seront écrits en TypeScript, que nous utilisons dans la plupart de nos projets. Dans tous les exemples, les marqueurs seront représentés par des objets de la forme suivante:

 interface Marker { minX: number; maxX: number; minY: number; maxY: number; } 

Toutes les approches envisagées seront des implémentations de l'interface suivante:

 interface CollisionDetector { insert(item: Marker): void; collides(item: Marker): boolean; } 

Pour comparer les performances, le temps d'exécution du code suivant sera mesuré:

 for (const marker of markers) { if (!impl.collides(marker)) { impl.insert(marker); } } 

Le tableau de markers contiendra 100 000 éléments 30x50 placés au hasard sur un plan de taille 1920x1080.

Les performances seront mesurées sur le Macbook Air 2012.

Les tests et exemples de code fournis dans l'article sont également publiés sur GitHub .

Implémentation naïve

Pour commencer, considérez l'option la plus simple, lorsque le marqueur est vérifié pour l'intersection avec les autres dans un cycle simple.

 class NaiveImpl implements CollisionDetector { private markers: Marker[]; constructor() { this.markers = []; } insert(marker: Marker): void { this.markers.push(marker); } collides(candidate: Marker): boolean { for (marker of this.markers) { if ( candidate.minX <= marker.maxX && candidate.minY <= marker.maxY && candidate.maxX >= marker.minX && candidate.maxY >= marker.minY ) { return true; } } return false; } } 

Temps de calcul de généralisation pour 100 000 marqueurs: 420 ms . Trop. Même si le calcul de généralisation se fait dans un Web Worker et ne bloque pas le thread principal, un tel retard sera perceptible à l'oeil, d'autant plus que cette opération doit être effectuée après chaque mouvement de carte. De plus, sur les appareils mobiles avec un processeur faible, le délai peut être encore plus important.

Implémentation de R-tree

Étant donné que dans une implémentation naïve, chaque marqueur est vérifié pour l'intersection avec tous les précédents, dans le pire des cas, la complexité de cet algorithme est quadratique. Vous pouvez l'améliorer en appliquant la structure de données de l'arborescence R. En tant qu'implémentation de l'arborescence R, prenez la bibliothèque RBush :

 import * as rbush from 'rbush'; export class RTreeImpl implements CollisionDetector { private tree: rbush.RBush<Marker>; constructor() { this.tree = rbush(); } insert(marker: Marker): void { this.tree.insert(marker); } collides(candidate: Marker): boolean { return this.tree.collides(candidate); } } 

Temps de calcul de généralisation pour 100 000 marqueurs: 173 ms . Beaucoup mieux. Nous avons utilisé cette approche dans les étages (cela a été mentionné dans mon article précédent ).

Visualisation du stockage des points dans l'arborescence R. La division hiérarchique du plan en rectangles vous permet de rétrécir rapidement la zone de recherche et de ne pas trier tous les objets

Implémentation du tampon de collision

Dessiner une carte est une tâche beaucoup plus compliquée que de dessiner le plan d'un bâtiment. Cela se manifeste également dans la généralisation. Même dans les plus grands centres commerciaux du monde, 1 000 organisations sont rarement au même étage. Dans le même temps, une simple requête de recherche dans une grande ville peut renvoyer des dizaines de milliers de résultats.

Lorsque nous avons commencé à développer une carte WebGL, nous avons commencé à penser: est-il encore possible d'accélérer la généralisation. Une idée intéressante nous a été proposée par le stellarateur qui a fonctionné pour nous: au lieu de l'arborescence R, utilisez un tampon dans lequel stocker l'état de chaque pixel de l'écran (occupé ou non occupé). Lors de l'insertion d'un marqueur sur l'écran, «remplissez» l'emplacement correspondant dans le tampon, et lors de la vérification de la possibilité de coller, vérifiez les valeurs des pixels dans la zone requise.

 class CollisionBufferByteImpl implements CollisionDetector { private buffer: Uint8Array; private height: number; constructor(width: number, height: number) { this.buffer = new Uint8Array(width * height); this.height = height; } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { buffer[i * this.height + j] = 1; } } } collides(candidate: Marker): boolean { const { minX, minY, maxX, maxY } = candidate; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { if (buffer[i * this.height + j]) { return true; } } } return false; } } 

Temps de calcul de généralisation pour 100 000 marqueurs: 46 ms .

Pourquoi si vite? Cette approche semble naïve à première vue, et les boucles imbriquées dans les deux méthodes ne sont pas comme du code rapide. Cependant, si vous regardez de plus près le code, vous remarquerez que le temps d'exécution des deux méthodes ne dépend pas du nombre total de marqueurs. Ainsi, pour une taille fixe de marqueurs WxH, on obtient la complexité O (W * H * n), c'est-à-dire linéaire!

Approche de tampon de collision optimisée

Vous pouvez améliorer l'approche précédente à la fois en vitesse et en mémoire occupée, si vous vous assurez qu'un pixel est représenté en mémoire non pas par un octet, mais par un bit. Le code après cette optimisation, cependant, est visiblement compliqué et se développe avec un peu de magie:

 export class CollisionBufferBitImpl implements CollisionDetector { private width: number; private height: number; private buffer: Uint8Array; constructor(width: number, height: number) { this.width = Math.ceil(width / 8) * 8; this.height = height; this.buffer = new Uint8Array(this.width * this.height / 8); } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; if (start === end) { buffer[start] = buffer[start] | (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { buffer[start] = buffer[start] | (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { buffer[i] = 255; } buffer[end] = buffer[end] | (255 << (8 - (maxX & 7))); } } } collides(marker: Marker): boolean { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; let sum = 0; if (start === end) { sum = buffer[start] & (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { sum = buffer[start] & (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { sum = buffer[i] | sum; } sum = buffer[end] & (255 << (8 - (maxX & 7))) | sum; } if (sum !== 0) { return true; } } return false; } } 

Temps de calcul de généralisation pour 100 000 marqueurs: 16 ms . Comme vous pouvez le voir, la complexité de la logique se justifie et nous permet d'accélérer le calcul de la généralisation de près de trois fois.

Limitations du tampon de collision

Il est important de comprendre que le tampon de collision n'est pas un remplacement complet de l'arborescence R. Il a beaucoup moins de fonctionnalités et plus de restrictions:

1. Vous ne pouvez pas comprendre exactement ce que le marqueur recoupe. Le tampon ne stocke que des données sur les pixels occupés et ceux qui ne le sont pas. Par conséquent, il est impossible d'implémenter une opération qui renvoie une liste de marqueurs qui se croisent avec le donné.
2. Impossible de supprimer le marqueur ajouté précédemment. Le tampon ne stocke pas de données sur le nombre de marqueurs dans un pixel donné. Par conséquent, il est impossible d'implémenter correctement l'opération de suppression d'un marqueur du tampon.
3. Haute sensibilité à la taille des éléments. Si vous essayez d'ajouter des marqueurs qui occupent la totalité de l'écran au tampon de collision, les performances chuteront considérablement.
4. Fonctionne dans une zone limitée. La taille du tampon est définie lors de sa création, et il est impossible d'y placer un marqueur qui dépasse cette taille. Par conséquent, lorsque vous utilisez cette approche, il est nécessaire de filtrer manuellement les marqueurs qui n'apparaissent pas à l'écran.

Toutes ces restrictions n'ont pas interféré avec la solution du problème de la généralisation des marqueurs. Maintenant, cette méthode est utilisée avec succès pour les marqueurs dans la version bêta de 2gis.ru.

Cependant, pour généraliser les principales signatures sur la carte, les exigences sont plus complexes. Par exemple, pour eux, il est nécessaire de s'assurer que l'icône POI ne peut pas «tuer» sa propre signature. Étant donné que le tampon de collision ne distingue pas exactement avec quoi l'intersection s'est produite, il ne permet pas de mettre en œuvre une telle logique. Par conséquent, ils ont dû laisser une solution à RBush.

Conclusion

L'article montre le chemin que nous sommes passés de la solution la plus simple à celle utilisée maintenant.

L'utilisation de l'arborescence R a été la première étape importante qui nous a permis d'accélérer plusieurs fois la mise en œuvre naïve. Cela fonctionne très bien dans les étages, mais en fait, nous n'utilisons qu'une petite fraction des capacités de cette structure de données.

Après avoir abandonné l'arbre R et le remplacer par un simple tableau bidimensionnel, qui fait exactement ce dont nous avons besoin, et rien d'autre, nous avons obtenu une augmentation encore plus grande de la productivité.

Cet exemple nous a montré combien il est important de choisir une solution à un problème parmi plusieurs options, de comprendre et de réaliser les limites de chacune d'entre elles. Les limites sont importantes et utiles, et vous ne devriez pas en avoir peur: en vous limitant habilement à quelque chose d'insignifiant, vous pouvez obtenir d'énormes avantages en retour là où cela est vraiment nécessaire. Par exemple, pour simplifier la résolution d'un problème, ou pour vous protéger de toute une classe de problèmes, ou, comme dans notre cas, pour améliorer plusieurs fois la productivité.