Los marcadores son algo bueno. Útil en cantidades razonables. Cuando hay demasiados, los beneficios desaparecen. ¿Qué hacer si desea marcar los resultados de búsqueda en el mapa, en qué decenas de miles de objetos? En el artículo, le diré cómo resolvemos este problema en una tarjeta WebGL sin comprometer su apariencia y rendimiento.

Antecedentes

En 2016, 2GIS lanzó su primer proyecto WebGL, Pisos: planos de edificios en 3D.

Pisos del centro comercial Novosibirsk Aura

Inmediatamente después del lanzamiento de Floors, nuestro equipo comenzó a desarrollar un motor cartográfico tridimensional completo en WebGL. El motor fue desarrollado junto con la nueva versión 2gis.ru y ahora está en estado beta público .

Cuadrado rojo dibujado en WebGL. Los planes de construcción ahora están integrados directamente en el mapa.

Tarea de generalización de firma

Cualquiera que quiera escribir su propio motor de mapas tarde o temprano se enfrentará al problema de colocar firmas en el mapa. Hay muchos objetos en el mapa, y es imposible firmar cada uno para que las firmas no se superpongan.

¿Qué pasará si en Novosibirsk todos los objetos se firman a la vez?

Para resolver este problema, se requiere la generalización de las firmas. La generalización en el sentido general es la transformación de los datos del mapa para que sea adecuada para su visualización en pequeñas escalas. Se puede hacer por diferentes métodos. Para las firmas, generalmente se usa el método de selección: del número total, se selecciona un subconjunto de las firmas más prioritarias que no se cruzan entre sí.

La prioridad de la firma está determinada por su tipo, así como por la escala del mapa actual. Por ejemplo, a pequeña escala, se necesitan firmas de ciudades y países, y a gran escala, las firmas de carreteras y los números de casas se vuelven mucho más importantes. A menudo, la prioridad del nombre de un asentamiento está determinada por el tamaño de su población. Cuanto más grande es, más importante es la firma.

Se requiere generalización no solo para las firmas, sino también para los marcadores que marcan los resultados de búsqueda en el mapa. Por ejemplo, cuando se busca "tienda" en Moscú, hay más de 15,000 resultados. Marcarlos a todos a la vez en el mapa es obviamente una mala idea.

Todas las tiendas de Moscú en el mapa. No hay forma de hacerlo sin generalización

Cualquier interacción del usuario con el mapa (movimiento, zoom, giro e inclinación) conduce a un cambio en la posición de los marcadores en la pantalla, por lo que debe poder recalcular la generalización sobre la marcha. Por lo tanto, debe ser rápido.

En este artículo, utilizando el ejemplo de generalización de marcadores, mostraré diferentes formas de resolver este problema, que se utilizaron en diferentes momentos en nuestros proyectos.

Enfoque general de generalización

1. Proyecte cada marcador en el plano de la pantalla y calcule un límite: el área rectangular que ocupa en la pantalla.
2. Ordenar marcadores por prioridad.
3. Examine secuencialmente cada marcador y colóquelo en la pantalla si no se cruza con otros marcadores colocados delante de él.

Con el punto 1, todo está claro: es solo un cálculo. Con el ítem 2, también tuvimos suerte: la lista de marcadores que nos llega desde el backend ya está ordenada por prioridad por algoritmos de búsqueda. Los resultados más relevantes que probablemente sean de interés para el usuario se encuentran en la parte superior de los resultados.

El problema principal está en el párrafo 3: el tiempo de cálculo de la generalización puede depender en gran medida de cómo se implemente.

Para buscar intersecciones entre marcadores, necesitamos alguna estructura de datos que:

1. Almacena los límites de los marcadores agregados a la pantalla.
2. Tiene un método de insert(marker) para agregar un marcador a la pantalla.
3. Tiene un método de collides(marker) para verificar la intersección del marcador con los que ya se agregaron a la pantalla.

Considere varias implementaciones de esta estructura. Todos los ejemplos adicionales se escribirán en TypeScript, que usamos en la mayoría de nuestros proyectos. En todos los ejemplos, los marcadores estarán representados por objetos de la siguiente forma:

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

Todos los enfoques considerados serán implementaciones de la siguiente interfaz:

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

Para comparar el rendimiento, se medirá el tiempo de ejecución del siguiente código:

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

La matriz de markers contendrá 100,000 elementos 30x50 colocados aleatoriamente en un plano de tamaño 1920x1080.

El rendimiento se medirá en el Macbook Air 2012.

Las pruebas y los ejemplos de código proporcionados en el artículo también se publican en GitHub .

Implementación ingenua

Para comenzar, considere la opción más simple, cuando se verifica la intersección del marcador con los demás en un ciclo 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; } } 

Tiempo de cálculo de generalización para 100.000 marcadores: 420 ms . Demasiado Incluso si el cálculo de la generalización se realiza en un trabajador web y no bloquea el hilo principal, dicha demora se notará a simple vista, especialmente porque esta operación debe realizarse después de cada movimiento de la tarjeta. Además, en dispositivos móviles con un procesador débil, el retraso puede ser aún mayor.

Implementación de R-tree

Dado que en una implementación ingenua se verifica la intersección de cada marcador con todos los anteriores, en el peor de los casos, la complejidad de este algoritmo es cuadrática. Puede mejorarlo aplicando la estructura de datos del árbol R. Como implementación del árbol R, tome la biblioteca 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); } } 

Tiempo de cálculo de generalización para 100.000 marcadores: 173 ms . Significativamente mejor. Utilizamos este enfoque en los pisos (esto fue mencionado en mi artículo anterior ).

Visualización de almacenamiento de puntos en el árbol R. La división jerárquica del plano en rectángulos le permite reducir rápidamente el área de búsqueda y no ordenar todos los objetos.

Implementación del buffer de colisión

Dibujar un mapa es una tarea mucho más complicada que dibujar un plano de un edificio. Esto también se manifiesta en generalización. Incluso en los centros comerciales más grandes del mundo, 1,000 organizaciones rara vez se encuentran en el mismo piso. Al mismo tiempo, una simple consulta de búsqueda en una gran ciudad puede arrojar decenas de miles de resultados.

Cuando comenzamos a desarrollar un mapa WebGL, comenzamos a pensar: ¿es posible acelerar la generalización? El stellarator que nos funcionó nos ofreció una idea interesante: en lugar del árbol R, use un búfer en el que almacenar el estado de cada píxel de la pantalla (ocupado o no ocupado). Cuando inserte un marcador en la pantalla, "complete" el lugar correspondiente en el búfer, y cuando verifique la posibilidad de pegar, verifique los valores de píxeles en el área requerida.

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

Tiempo de cálculo de generalización para 100.000 marcadores: 46 ms .

¿Por qué tan rápido? Este enfoque parece ingenuo a primera vista, y los bucles anidados en ambos métodos no son como el código rápido. Sin embargo, si observa más de cerca el código, notará que el tiempo de ejecución de ambos métodos no depende del número total de marcadores. Por lo tanto, para un tamaño fijo de marcadores WxH, obtenemos la complejidad O (W * H * n), es decir, lineal.

Enfoque optimizado del amortiguador de colisión

Puede mejorar el enfoque anterior tanto en velocidad como en memoria ocupada, si se asegura de que un píxel esté representado en la memoria no por un byte, sino por un bit. Sin embargo, el código después de esta optimización es notablemente complicado y crece demasiado con un poco de magia:

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

Tiempo de cálculo de generalización para 100.000 marcadores: 16 ms . Como puede ver, la complejidad de la lógica se justifica y nos permite acelerar el cálculo de la generalización en casi tres veces.

Limitaciones del colchón de colisión

Es importante comprender que el búfer de colisión no es un reemplazo completo para el árbol R. Tiene muchas menos características y más restricciones:

1. No puede entender con qué se cruza exactamente el marcador. El búfer solo almacena datos sobre qué píxeles están ocupados y cuáles no. Por lo tanto, es imposible implementar una operación que devuelva una lista de marcadores que se cruzan con los dados.
2. No se puede eliminar el marcador agregado previamente. El búfer no almacena datos sobre cuántos marcadores hay en un píxel dado. Por lo tanto, es imposible implementar correctamente la operación de eliminar un marcador del búfer.
3. Alta sensibilidad al tamaño de los elementos. Si intenta agregar marcadores que ocupan toda la pantalla al búfer de colisión, el rendimiento disminuirá drásticamente.
4. Trabaja en un área limitada. El tamaño del búfer se establece cuando se crea, y es imposible colocar un marcador que vaya más allá de este tamaño. Por lo tanto, cuando se utiliza este enfoque, es necesario filtrar manualmente los marcadores que no aparecen en la pantalla.

Todas estas restricciones no interfirieron con la solución del problema de la generalización de marcadores. Ahora este método se utiliza con éxito para los marcadores en la versión beta de 2gis.ru.

Sin embargo, para generalizar las firmas principales en el mapa, los requisitos son más complejos. Por ejemplo, para ellos es necesario asegurarse de que el ícono de PDI no pueda "matar" su propia firma. Como el búfer de colisión no distingue con qué ocurrió exactamente la intersección, no permite implementar dicha lógica. Por lo tanto, tuvieron que dejar una solución con RBush.

Conclusión

El artículo muestra el camino que pasamos de la solución más simple a la utilizada ahora.

El uso del árbol R fue el primer paso importante que nos permitió acelerar la implementación ingenua muchas veces. Funciona muy bien en Pisos, pero de hecho usamos solo una pequeña fracción de las capacidades de esta estructura de datos.

Después de abandonar el árbol R y reemplazarlo con una matriz bidimensional simple, que hace exactamente lo que necesitamos, y nada más, obtuvimos un aumento aún mayor en la productividad.

Este ejemplo nos mostró lo importante que es, elegir una solución a un problema entre varias opciones, para comprender y comprender las limitaciones de cada una de ellas. Las limitaciones son importantes y útiles, y no debe tenerles miedo: si se limita hábilmente a algo insignificante, puede obtener enormes beneficios a cambio donde realmente se necesitan. Por ejemplo, para simplificar la solución de un problema, o para protegerse de toda una clase de problemas o, como en nuestro caso, para mejorar la productividad varias veces.