Marker sind eine gute Sache. Nützlich in angemessenen Mengen. Wenn es zu viele von ihnen gibt, verschwinden die Vorteile. Was tun, wenn Sie Suchergebnisse auf der Karte markieren möchten, in denen Zehntausende von Objekten vorhanden sind? In dem Artikel werde ich Ihnen erklären, wie wir dieses Problem auf einer WebGL-Karte lösen, ohne deren Aussehen und Leistung zu beeinträchtigen.

Hintergrund

2016 startete 2GIS sein erstes WebGL-Projekt, Floors: 3D-Grundrisse von Gebäuden.

Fußböden des Nowosibirsker Einkaufszentrums Aura

Unmittelbar nach der Veröffentlichung von Floors begann unser Team mit der Entwicklung einer vollwertigen dreidimensionalen kartografischen Engine für WebGL. Die Engine wurde in Verbindung mit der neuen Version 2gis.ru entwickelt und befindet sich nun im öffentlichen Beta- Status.

Rotes Quadrat auf WebGL gezeichnet. Baupläne werden jetzt direkt in die Karte integriert.

Aufgabe zur Verallgemeinerung von Signaturen

Jeder, der seine eigene Karten-Engine schreiben möchte, wird früher oder später mit dem Problem konfrontiert sein, Signaturen auf der Karte zu platzieren. Es gibt viele Objekte auf der Karte, und es ist unmöglich, jedes zu signieren, damit sich die Signaturen nicht überschneiden.

Was passiert, wenn in Nowosibirsk alle Objekte gleichzeitig signiert sind?

Um dieses Problem zu lösen, ist eine Verallgemeinerung der Signaturen erforderlich. Verallgemeinerung im allgemeinen Sinne ist die Transformation von Kartendaten, so dass sie für die Anzeige in kleinen Maßstäben geeignet sind. Dies kann mit verschiedenen Methoden erfolgen. Für Signaturen wird normalerweise die Auswahlmethode verwendet: Aus der Gesamtzahl wird eine Teilmenge der Signaturen mit der höchsten Priorität ausgewählt, die sich nicht überlappen.

Die Signaturpriorität wird durch ihren Typ sowie den aktuellen Kartenmaßstab bestimmt. Beispielsweise werden im kleinen Maßstab Unterschriften von Städten und Ländern benötigt, und im großen Maßstab werden Straßensignaturen und Hausnummern viel wichtiger. Oft wird die Priorität des Namens einer Siedlung durch die Größe ihrer Bevölkerung bestimmt. Je größer es ist, desto wichtiger ist die Signatur.

Eine Verallgemeinerung ist nicht nur für Signaturen erforderlich, sondern auch für Markierungen, die die Suchergebnisse auf der Karte markieren. Wenn Sie beispielsweise in Moskau nach einem „Geschäft“ suchen, erhalten Sie mehr als 15.000 Ergebnisse. Es ist offensichtlich eine schlechte Idee, sie alle gleichzeitig auf der Karte zu markieren.

Alle Moskauer Geschäfte auf der Karte. Ohne Verallgemeinerung geht es nicht

Jede Benutzerinteraktion mit der Karte (Bewegen, Zoomen, Drehen und Neigen) führt zu einer Änderung der Position der Markierungen auf dem Bildschirm. Sie müssen daher in der Lage sein, die Generalisierung im laufenden Betrieb neu zu berechnen. Deshalb muss es schnell gehen.

In diesem Artikel werde ich am Beispiel der Marker-Generalisierung verschiedene Möglichkeiten zur Lösung dieses Problems zeigen, die zu unterschiedlichen Zeiten in unseren Projekten verwendet wurden.

Allgemeiner Ansatz zur Verallgemeinerung

1. Projizieren Sie jeden Marker auf die Ebene des Bildschirms und berechnen Sie dafür eine Grenze - den rechteckigen Bereich, den er auf dem Bildschirm einnimmt.
2. Sortieren Sie die Marker nach Priorität.
3. Untersuchen Sie nacheinander jeden Marker und platzieren Sie ihn auf dem Bildschirm, wenn er sich nicht mit anderen davor platzierten Markern schneidet.

Mit Punkt 1 ist alles klar - es ist nur eine Berechnung. Mit Punkt 2 hatten wir auch Glück: Die Liste der Marker, die vom Backend zu uns kommen, ist bereits nach Priorität nach Suchalgorithmen sortiert. Die relevantesten Ergebnisse, die für den Benutzer am wahrscheinlichsten von Interesse sind, stehen ganz oben in den Ergebnissen.

Das Hauptproblem ist in Absatz 3: Der Zeitpunkt der Berechnung der Verallgemeinerung kann stark davon abhängen, wie sie implementiert wird.

Um nach Schnittpunkten zwischen Markierungen zu suchen, benötigen wir eine Datenstruktur, die:

1. Speichert die Grenzen der Markierungen, die dem Bildschirm hinzugefügt wurden.
2. Verfügt über eine insert(marker) , um dem Bildschirm einen Marker hinzuzufügen.
3. Es gibt eine collides(marker) , um die Markierung auf Schnittpunkte mit den bereits zum Bildschirm hinzugefügten zu überprüfen.

Betrachten Sie mehrere Implementierungen dieser Struktur. Alle weiteren Beispiele werden in TypeScript geschrieben, das wir in den meisten unserer Projekte verwenden. In allen Beispielen werden Markierungen durch Objekte der folgenden Form dargestellt:

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

Alle berücksichtigten Ansätze sind Implementierungen der folgenden Schnittstelle:

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

Um die Leistung zu vergleichen, wird die Ausführungszeit des folgenden Codes gemessen:

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

Das markers enthält 100.000 30 x 50 Elemente, die zufällig auf einer Ebene mit einer Größe von 1920 x 1080 platziert werden.

Die Leistung wird auf dem 2012 Macbook Air gemessen.

Die im Artikel bereitgestellten Tests und Codebeispiele werden auch auf GitHub veröffentlicht .

Naive Umsetzung

Betrachten Sie zunächst die einfachste Option, wenn die Markierung in einem einfachen Zyklus auf Schnittpunkte mit den anderen überprüft wird.

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

Verallgemeinerungsberechnungszeit für 100.000 Marker: 420 ms . Zu viel. Selbst wenn die Berechnung der Verallgemeinerung in einem Web-Worker durchgeführt wird und den Haupt-Thread nicht blockiert, ist eine solche Verzögerung für das Auge erkennbar, zumal dieser Vorgang nach jeder Kartenbewegung ausgeführt werden muss. Darüber hinaus kann auf Mobilgeräten mit einem schwachen Prozessor die Verzögerung noch größer sein.

R-Tree-Implementierung

Da in einer naiven Implementierung jeder Marker auf Schnittpunkte mit allen vorherigen überprüft wird, ist die Komplexität dieses Algorithmus im schlimmsten Fall quadratisch. Sie können es verbessern, indem Sie die R-Tree-Datenstruktur anwenden. Nehmen Sie als Implementierung des R-Baums die RBush- Bibliothek:

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

Verallgemeinerungsberechnungszeit für 100.000 Marker: 173 ms . Deutlich besser. Wir haben diesen Ansatz in den Etagen verwendet (dies wurde in meinem vorherigen Artikel erwähnt ).

Visualisierung der Speicherung von Punkten im R-Baum. Durch die hierarchische Unterteilung der Ebene in Rechtecke können Sie den Suchbereich schnell eingrenzen und nicht alle Objekte sortieren

Implementierung des Kollisionspuffers

Das Zeichnen einer Karte ist eine viel kompliziertere Aufgabe als das Zeichnen eines Plans eines Gebäudes. Dies äußert sich auch in der Verallgemeinerung. Selbst in den größten Einkaufszentren der Welt befinden sich 1.000 Organisationen selten auf derselben Etage. Gleichzeitig kann eine einfache Suchabfrage in einer Großstadt Zehntausende von Ergebnissen liefern.

Als wir mit der Entwicklung einer WebGL-Karte begannen, begannen wir zu überlegen: Ist es immer noch möglich, die Generalisierung zu beschleunigen? Eine interessante Idee bot uns der für uns funktionierende Stellarator an : Verwenden Sie anstelle des R-Baums einen Puffer, in dem der Status jedes Pixels des Bildschirms (beschäftigt oder nicht beschäftigt) gespeichert wird. Wenn Sie eine Markierung auf dem Bildschirm einfügen, füllen Sie die entsprechende Stelle im Puffer aus und überprüfen Sie beim Überprüfen der Einfügemöglichkeit die Pixelwerte im gewünschten Bereich.

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

Verallgemeinerungsberechnungszeit für 100.000 Marker: 46 ms .

Warum so schnell? Dieser Ansatz erscheint auf den ersten Blick naiv, und verschachtelte Schleifen in beiden Methoden sind nicht wie schneller Code. Wenn Sie sich den Code jedoch genauer ansehen, werden Sie feststellen, dass die Ausführungszeit beider Methoden nicht von der Gesamtzahl der Marker abhängt. Somit erhalten wir für eine feste Größe von WxH-Markern die Komplexität O (W * H * n), dh linear!

Optimierter Kollisionspuffer-Ansatz

Sie können den vorherigen Ansatz sowohl hinsichtlich der Geschwindigkeit als auch des belegten Speichers verbessern, wenn Sie sicherstellen, dass ein Pixel im Speicher nicht durch ein Byte, sondern durch ein Bit dargestellt wird. Der Code nach dieser Optimierung ist jedoch merklich kompliziert und wächst mit ein bisschen 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; } } 

Verallgemeinerungsberechnungszeit für 100.000 Marker: 16 ms . Wie Sie sehen, rechtfertigt sich die Komplexität der Logik und ermöglicht es uns, die Berechnung der Generalisierung um fast das Dreifache zu beschleunigen.

Einschränkungen des Kollisionspuffers

Es ist wichtig zu verstehen, dass der Kollisionspuffer keinen vollständigen Ersatz für den R-Baum darstellt. Es hat viel weniger Funktionen und mehr Einschränkungen:

1. Sie können nicht verstehen, womit sich der Marker genau schneidet. Der Puffer speichert nur Daten darüber, welche Pixel belegt sind und welche nicht. Daher ist es unmöglich, eine Operation zu implementieren, die eine Liste von Markierungen zurückgibt, die sich mit den angegebenen überschneiden.
2. Zuvor hinzugefügte Markierung kann nicht gelöscht werden. Der Puffer speichert keine Daten darüber, wie viele Markierungen sich in einem bestimmten Pixel befinden. Daher ist es unmöglich, den Vorgang des Entfernens eines Markers aus dem Puffer korrekt zu implementieren.
3. Hohe Empfindlichkeit gegenüber der Größe der Elemente. Wenn Sie versuchen, dem Kollisionspuffer Markierungen hinzuzufügen, die den gesamten Bildschirm einnehmen, sinkt die Leistung erheblich.
4. Arbeitet in einem begrenzten Bereich. Die Größe des Puffers wird beim Erstellen festgelegt, und es ist unmöglich, einen Marker darin zu platzieren, der über diese Größe hinausgeht. Bei diesem Ansatz müssen daher Markierungen, die nicht auf dem Bildschirm angezeigt werden, manuell gefiltert werden.

Alle diese Einschränkungen haben die Lösung des Problems der Marker-Generalisierung nicht beeinträchtigt. Jetzt wird diese Methode erfolgreich für Marker in der Beta-Version von 2gis.ru verwendet.

Um die Hauptsignaturen auf der Karte zu verallgemeinern, sind die Anforderungen jedoch komplexer. Für sie muss beispielsweise sichergestellt werden, dass das POI-Symbol seine eigene Signatur nicht „töten“ kann. Da der Kollisionspuffer nicht unterscheidet, mit was genau der Schnittpunkt passiert ist, kann eine solche Logik nicht implementiert werden. Daher mussten sie eine Lösung bei RBush hinterlassen.

Fazit

Der Artikel zeigt den Weg, den wir von der einfachsten Lösung zu der jetzt verwendeten gegangen sind.

Die Verwendung des R-Baums war der erste wichtige Schritt, mit dem wir die naive Implementierung um ein Vielfaches beschleunigen konnten. In Floors funktioniert es hervorragend, aber tatsächlich nutzen wir nur einen kleinen Bruchteil der Funktionen dieser Datenstruktur.

Nachdem wir den R-Baum aufgegeben und durch ein einfaches zweidimensionales Array ersetzt haben, das genau das tut, was wir brauchen, und sonst nichts, konnten wir die Produktivität noch weiter steigern.

Dieses Beispiel hat uns gezeigt, wie wichtig es ist, aus mehreren Optionen eine Lösung für ein Problem auszuwählen, um die Einschränkungen der einzelnen Optionen zu verstehen und zu erkennen. Einschränkungen sind wichtig und nützlich, und Sie sollten keine Angst davor haben: Wenn Sie sich geschickt auf etwas Unbedeutendes beschränken, können Sie im Gegenzug dort, wo es wirklich benötigt wird, enorme Vorteile erzielen. Zum Beispiel, um die Lösung eines Problems zu vereinfachen oder um sich vor einer ganzen Klasse von Problemen zu schützen oder um, wie in unserem Fall, die Produktivität mehrmals zu verbessern.