Algoritmo de agrupamiento espacial incremental

Estoy en busca de un algoritmo de agrupamiento espacial incremental . Aquí está mi caso de uso:

• los usuarios crean entradas con una posición inicial
• los usuarios pueden cambiar las posiciones de las entradas existentes

Ahora quiero implementar un servicio desacoplado que proporcione información de agrupación de estos datos. El servicio será notificado cada vez que se agregue una nueva entrada o se mueva una entrada existente. ¿Qué es un buen algoritmo de agrupación por lo tanto? Idealmente, debería escalar bien hasta grandes cantidades de datos y si hay una compensación entre la calidad del clúster y la complejidad del tiempo de ejecución, estoy de acuerdo con resultados degradantes y eventualmente resultados consistentes (los resultados obsoletos están bien por algún tiempo).

Para resumir mis requisitos:

• agrupamiento espacial basado en posiciones
• modificaciones incrementales en los cambios
• agregar nuevas posiciones
• cambiar posiciones existentes
• buen rendimiento en tiempo de ejecución

¡Gracias por adelantado!

El propósito de esta agrupación es simplificar la visualización de los símbolos de puntos: cuando muchos están muy juntos en el mapa, serán reemplazados por un solo símbolo para indicar un grupo.

Los requisitos apuntan a la necesidad de una solución simple y adaptativa : los símbolos de puntos pueden actualizarse y, a medida que el usuario se acerca, aparecerán diferentes símbolos en diferentes lugares en la extensión del mapa (o pantalla).

Un excelente candidato es claramente una región quadtree .

Hay un método más simple que actuará como un quadtree de región. Requiere menos codificación, sin creación anticipada de una estructura de datos, pero usted paga un precio (pequeño) al tener que realizar algunos cálculos sobre la marcha durante el zoom y la panorámica. Solo cuadricula el mapa . Específicamente, suponga 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 las coordenadas ( x [i] , y [i] ), i = 1, 2, ..., n . Al seleccionar un tamaño de celda de cuadrícula de c, se divide el mapa en una cuadrícula de celdas. La celda en la que la ubicación (x , y ) pertenece está en la fila j ( y ) = Piso [ y / c ] y columna j ( x ) (contando desde 0, con filas de abajo hacia arriba y columnas de izquierda a derecha). Puede considerar cualquier celda que reciba dos o más puntos como un "grupo". El símbolo del grupo se puede dibujar en el centro de la celda, que tiene coordenadas ( j + c / 2, k + c / 2).

Esto 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

Claramente, la carga informática del algoritmo es O (# de puntos) en el tiempo y O (dx * dy / c ^ 2) en el almacenamiento. Las compensaciones involucradas en la selección del tamaño de celda c son:

1. c debe ser lo más grande posible: el almacenamiento es inversamente proporcional a c ^ 2: los valores pequeños de c significan grandes cantidades de RAM. (El almacenamiento se puede reducir a O (# de puntos) mediante el uso de matrices dispersas o diccionarios).

2. c debe ser lo más grande posible: dos símbolos (puntos o grupos) nunca estarán más cerca que c / 2.

3. c debería ser lo más pequeño posible: cada símbolo de clúster representa ubicaciones no más allá de c / sqrt (2) lejos de él.

4. c debería 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 análisis rápido de (4). Como punto de partida, suponga que las ubicaciones a mapear ocurren uniformemente al azar e independientemente una de la otra. El número de celdas es N ( c ) = (Floor ( dx / c ) +1) * (Floor ( dy / c ) +1), que - al menos para valores mayores de c - es directamente proporcional a c ^ 2) La distribución de los recuentos celulares seguirá aproximadamente una ley de Poisson con intensidad lambda = n / N ( c ) = n * c ^ 2 / ( dx * dy) El número esperado de grupos es igual

e ( c ) = n (1 - exp (- lambda ) (1 + lambda )).

Esto se vuelve más pequeño a medida que lambda se reduce a 0; es decir, a medida que el tamaño de la celda c se hace cada vez más pequeño. El objetivo de este análisis es que la fórmula anterior le permite anticipar cuántos clústeres podría haber, por lo que puede seleccionar un valor inicial de c para el cual e ( c ) está por debajo de un valor aceptable (mientras es lo suficientemente grande como para limitar la RAM requisitos). No existe una solución de forma cerrada, pero algunos pasos de Newton-Raphson convergerán en uno rápidamente.

Este enfoque es tan dinámico: es lo suficientemente rápido que la cuadrícula y el agrupamiento consecuente se pueden calcular con cada zoom y panorámica, y no requiere estructuras de datos precalculadas, que las "modificaciones incrementales" deseadas a medida que se actualizan los datos ocurrirán automáticamente.

¿Estás buscando algo como http://dev.openlayers.org/releases/OpenLayers-2.10/examples/strategy-cluster-threshold.html ? Si es así, el código no debería ser demasiado difícil de seguir.