El objetivo de esta agrupación es simplificar la visualización de los símbolos de los puntos: cuando muchos estén cerca unos de otros en el mapa, se sustituirán por un único símbolo para indicar un grupo.
Los requisitos apuntan a la necesidad de una solución sencilla, adaptativo solución: los símbolos de los puntos pueden actualizarse y, a medida que el usuario se acerque, aparecerán diferentes símbolos en distintos lugares de la extensión del mapa (o de la pantalla).
Un candidato excelente es claramente un región quadtree .
Existe un método más sencillo que actuará como un cuadríclo de regiones. Requiere menos codificación, no hay creación anticipada de una estructura de datos, pero se paga un (pequeño) precio al tener que realizar algunos cálculos sobre la marcha durante el zoom y la panorámica. Sólo hay que cuadricular el mapa . En concreto, supongamos que hay n símbolos de puntos que se dibujarán dentro de la extensión actual del mapa que tiene una longitud de dx y una altura de dy . En relación con el origen del mapa, los símbolos deben dibujarse en coordenadas ( x[i] , y[i] ), i \= 1, 2, ..., n . Seleccionando un tamaño de celda de cuadrícula de c divide el mapa en una cuadrícula de celdas. La celda en la que la ubicación ( x , y ) está en la fila j ( y ) = Piso[ y / c ] y la columna j ( x ) (contando desde 0, con filas que van de abajo a arriba y columnas de izquierda a derecha). Se puede considerar que cualquier celda que reciba dos o más puntos es un "cluster". El símbolo del clúster puede dibujarse en el centro de la celda, que tiene coordenadas.( j + c /2, k + c /2).
Esto nos lleva a la siguiente solución, presentada en pseudocódigo:
m = Floor(dy/c)+1
n = Floor(dx/c)+1
Dimension a[m,n] = 0
For each (x[i], y[i]) to be displayed:
Increment( a[ j(y[i]), j(x[i]) ] )
End for
For each (x[i], y[i]) to be displayed:
row = j(y[i])
col = j(x[i])
If a[row, col] > 1:
Draw a symbol for a cluster of k points at (c*(col+0.5), c*(row+0.5))
a[row, col] = 0
Else
Draw a point symbol at (x[i], y[i])
End if
End for
Está claro que la carga computacional del algoritmo es O(# de puntos) en tiempo y O(dx*dy/c^2) en almacenamiento. Los compromisos que implica la selección del tamaño de las celdas c son:
-
c debe ser lo más grande posible: El almacenamiento es inversamente proporcional a c ^2: valores pequeños de c significan grandes cantidades de RAM. (El almacenamiento puede reducirse a O(# de puntos) utilizando matrices dispersas o diccionarios).
-
c debe ser lo más grande posible: Dos símbolos (puntos o racimos) nunca estarán más cerca que c /2.
-
c debe ser lo más pequeño posible: cada símbolo de conglomerado representa lugares no más allá de c /sqrt(2) lejos de él.
-
c debe ser lo más pequeño posible: Los valores grandes de c tienden a crear muchos grupos y permiten que aparezcan pocos puntos individuales.
Hagamos un rápido análisis de (4). Como punto de partida, supongamos que las ubicaciones que hay que cartografiar se producen uniformemente de forma aleatoria e independiente unas de otras. El número de celdas es N ( c ) = (Floor( dx / c )+1) * (Floor( dy / c )+1), que -al menos para los valores más grandes de c --es directamente proporcional a c ^2. La distribución del recuento de células seguirá aproximadamente una ley de Poisson con intensidad lambda \= n / N ( c ) = n * c ^2 / ( dx * dy ). El número esperado de conglomerados es igual a
e ( c ) = n (1 - exp(-) lambda )(1 + lambda )).
Esto se reduce a medida que lambda se reduce a 0; es decir, a medida que el tamaño de las celdas c se hace cada vez más pequeño. El sentido de este análisis es que la fórmula anterior permite anticipar cuántos conglomerados puede haber, por lo que se puede seleccionar un valor inicial de c para lo cual e ( c ) está por debajo de un valor aceptable (sin dejar de ser lo suficientemente grande como para limitar las necesidades de RAM). No existe una solución de forma cerrada, pero se pueden encontrar algunas Newton-Raphson los pasos convergerán a uno rápidamente.
Este enfoque es tan dinámico -es lo suficientemente rápido como para que la retícula y la consiguiente agrupación puedan calcularse con cada ampliación y desplazamiento, y no requiere estructuras de datos precalculadas- que las deseadas "modificaciones incrementales" a medida que se actualizan los datos se producirán automáticamente.
