¿Difundir/dispersar puntos superpuestos?

Question

Tengo un conjunto de 150 sitios a nivel mundial, y quiero mapearlos y colorearlos según una variable dada. Desafortunadamente, están distribuidos de manera muy no uniforme, con muchos de ellos en pequeños grupos de solo unos pocos metros. Esto significa que con marcadores de un tamaño razonable en un mapa, los marcadores se superponen mucho y muchos de ellos no se pueden ver. Me gustaría encontrar una manera de dispersar los marcadores (con líneas que los conecten a su posición original), para que cada marcador pueda ser visto sin superposición. La posición exacta no es súper importante aquí, pero sí la posición global aproximada.

Estoy utilizando python con basemap/matplotlib, y he probado un enfoque tipo fuerza dirigida que funciona más o menos, pero no muy bien. Aquí tienes un ejemplo:

Como se puede ver, los puntos europeos no se separan muy bien.
El código para esa dispersión es:

def spread_points(lat_lon, d=5, max_iter=300):

    new_lat_lon = lat_lon.copy(deep=True)

    dists = scipy.spatial.distance_matrix(new_lat_lon, new_lat_lon)
    too_close = (0 < dists) & (dists < d)

    itr = 0
    while too_close.any() and itr < max_iter:
        itr += 1

        neighbour_means = []

        for i in range(len(new_lat_lon)):
            # para cada punto, encontrar todos los puntos "demasiado cerca" y tomar su promedio.
            group_ind = too_close[i]
            if not group_ind.any():
                # no hay vecinos demasiado cercanos, usar el propio.
                neighbour_means.append(new_lat_lon.iloc[i])
                continue
            group_ind[i] = True
            neighbour_means.append(new_lat_lon[group_ind].mean())

        max_diff = 0
        for i in range(len(new_lat_lon)):
            dir_grp_mean = (new_lat_lon.iloc[i] - neighbour_means[i])
            grp_dist = norm(dir_grp_mean)
            if grp_dist == 0:
                dir_grp_unit = 0
                grp_force = 0
            else:
                dir_grp_unit = dir_grp_mean / grp_dist
                grp_force = np.sqrt(d / grp_dist)

            # mover cada punto lejos del promedio y hacia su posición original y hacer temblar un poco
            new_loc = new_lat_lon.iloc[i] \
                + grp_force * dir_grp_unit \
                - (new_lat_lon.iloc[i] - lat_lon.iloc[i]) / d \
                + np.random.randn(2) * 0.01 * d
            if not np.isfinite(new_loc).all():
                import ipdb
                ipdb.set_trace()
            max_diff = max(max_diff, norm(new_loc - new_lat_lon.iloc[i]))
            new_lat_lon.iloc[i] = new_loc

        if max_diff < d / 100:
            logger.info("Salida después de {i} iteraciones - las diferencias son pequeñas")
            break

        dists = scipy.spatial.distance_matrix(new_lat_lon, new_lat_lon)
        too_close = (0 < dists) & (dists < d)

    if itr == max_iter:
        logger.info("alcanzó max_iter")

    return new_lat_lon

Hay otro algoritmo en Inkscape llamado removeoverlaps, que parece que podría funcionar, pero estoy teniendo dificultades para entender cómo funciona. Edición: Los resultados realmente no son ideales de todos modos, porque mueve los puntos horizontalmente primero y luego verticalmente, lo que resulta en un diseño extraño:

Sería mucho mejor si los puntos se dispersaran radialmente...

¿Hay otros algoritmos para este tipo de operación que ya existan o que serían fáciles de implementar en python?

Answer 1

Usando el comentario de FelixIP como punto de partida, creé una cuadrícula hexagonal y luego moví cada punto a la celda de la cuadrícula más cercana. Para evitar empujar, utilicé un hash de los nombres de los sitios para ordenar los sitios de manera pseudoaleatoria, de modo que el mapa sea el mismo cada vez.

Los resultados se ven así:

El código de este gráfico está disponible en https://gist.github.com/naught101/d364b176b0646da9bf58198d79a0197d, y requiere un dataframe de pandas con columnas lat, lon, c (color), e indexado por el nombre del sitio.

El tamaño de la cuadrícula es arbitrario, elegí valores que se adaptarían al tamaño del gráfico.

Esta solución no es perfecta. Muestra todos los puntos en aproximadamente las posiciones correctas, pero también mueve puntos que no necesitan ser movidos.