CodeChallenger: Proyectando grandes Datasets en Google Maps

Proyectar información georeferenciada de nuestro sistema con Google Maps es un proceso que se logra con relativa facilidad. Sin embargo cuando el volumen de información que se muestra comienza a crecer, el mapa se vuelve prácticamente inservible pues es imposible localizar algo con facilidad.

Es en este punto cuando se comienza a buscar alguna solución a este “agradable” problema. Rápidamente te das cuenta que necesitas de alguna forma “agrupar” (cluster en inglés) información y por ahí comienzas a trabajar.

Muchos métodos de agrupamiento en el fondo se parecen. Básicamente se trata de agrupar datos siguiendo algún criterio. Para esto se necesita alguna ecuación que nos indique cuán parecidos son 2 elementos, se define un umbral y los datos que no sobrepasen dicho umbral conforman el clúster. En nuestro caso, el criterio que se sigue es hallar la distancia que existe entre 2 puntos, si esa distancia es menor que un umbral que se defina entonces se agrupan. En la siguiente figura se muestra el resultado final, también se puede ver en la dirección http://www.chil.es/yellowpages

Existe una biblioteca capaz de agrupar datos pero lo hace del lado del cliente lo cual no resulta beneficioso debido a la gran cantidad de datos que es necesario enviar en la respuesta HTTP.

Pues bien, manos a la obra. Lo primero que se necesita es hallar la distancia entre los puntos, esto se consigue a través de la fórmula de Haversine. Sucede que en nuestro caso necesitamos la distancia pero en píxeles, para esto usamos la proyección de Mercator. La siguiente clase encapsula los métodos necesarios para trabajar con las fórmulas de distancia:

public static class GeolocalizationUtils
{
    public const int Offset = 268435456; //It is half of the earth circumference in pixels at zoom level 21
  
    public const double Radius = 85445659.4471; // offset / pi()
  
    public const double EartRadiusInMiles = 3956.0;
  
    public static double ToRadian(double val)
    {
        return val * (Math.PI / 180);
    }
  
    public static double DiffRadian(double val1, double val2)
    {
        return ToRadian(val2) - ToRadian(val1);
    }
  
    public static double ConvertFromMetersToMiles(int meters)
    {
        return meters * 0.000621371192237334;
    }
  
    /// <summary>
    /// Evaluate the distance between two points on the Earth (miles)
    /// </summary>
    /// <param name="lat1">Latitude 1</param>
    /// <param name="lng1">Longitude 1</param>
    /// <param name="lat2">Latitude 2</param>
    /// <param name="lng2">Longitude 2</param>
    /// <returns></returns>
    public static double CalcDistance(double lat1, double lng1, double lat2, double lng2)
    {
        return EartRadiusInMiles * 2 * (Math.Asin(
                    Math.Min(1,
                        Math.Sqrt(
                            (
                                Math.Pow(Math.Sin((DiffRadian(lat1, lat2)) / 2.0), 2.0) +
                                Math.Cos(ToRadian(lat1)) * Math.Cos(ToRadian(lat2)) *
                                Math.Pow(Math.Sin((DiffRadian(lng1, lng2)) / 2.0), 2.0)
                            )
                        )
                    )
                )
            );
    }
  
    public static int LonToX(double lon)
    {
        return (int)Math.Round(Offset + Radius * lon * Math.PI / 180);
    }
  
    public static int LatToY(double lat)
    {
        return (int)Math.Round(Offset - Radius * Math.Log((1 + Math.Sin(lat * Math.PI / 180)) / (1 - Math.Sin(lat * Math.PI / 180))) / 2);
    }
  
    /// <summary>
    /// Evaluate the distance between two points (pixel)
    /// </summary>
    /// <param name="lat1">Latitude 1</param>
    /// <param name="lng1">Longitude 1</param>
    /// <param name="lat2">Latitude 2</param>
    /// <param name="lng2">Longitude 1</param>
    /// <param name="zoom">Zoom level</param>
    /// <returns></returns>
    public static int CalcPixelDistance(double lat1, double lng1, double lat2, double lng2, int zoom)
    {
        var x1 = LonToX(lng1);
        var y1 = LatToY(lat1);
  
        var x2 = LonToX(lng2);
        var y2 = LatToY(lat2);
  
        return (int)Math.Sqrt(Math.Pow(x1 - x2, 2) + Math.Pow(y1 - y2, 2)) >> (21 - zoom);
    }
}

Ahora definimos la interfaz que deberá implementar nuestro algoritmo de clúster:

public interface IClusterProcessor
{
    /// <summary>
    /// Cluster a list of items
    /// </summary>
    /// <typeparam name="E"></typeparam>
    /// <param name="items">The list of items to cluster</param>
    /// <param name="zoom">The zoom of the map</param>
    /// <param name="pixelThreshold">Pixel threshold distance</param>
    /// <param name="threshold">Threshold in meters for items in the same place</param>
    /// <returns></returns>
    ClusterResult<E> DoCluster<E>(IEnumerable<E> items, int zoom, int pixelThreshold = 40, int threshold = 5) where E : IGeolocalizable;
}

La interface solo consta de un método. A este método se le debe suministrar una colección de objetos que implementen la interface IGeolocalizable, la cual se define de la siguiente forma:

public interface IGeolocalizable
{
    double Latitude { get; set; }
  
    double Longitude { get; set; }
}

Así mismo el método retornará el resultado en una instancia de ClusterResult que se define de la siguiente manera:

public class ClusterResult<T>
    where T : IGeolocalizable
{
    public IEnumerable<T> Items { get; set; }
  
    public IEnumerable<Cluster<T>> Clusters { get; set; }
}

En la propiedad Items quedarán los elementos que no se han agrupado y en la propiedad Clusters quedarán los distintos clústeres que se han de ir encontrando. De esta manera la clase Cluster se define de la siguiente manera:

public class Cluster<T> : IGeolocalizable
{
    public double Latitude { get; set; }
  
    public double Longitude { get; set; }
  
    public IEnumerable<T> Items { get; set; }
  
    public bool IsClusterInOnePoint { get; set; }
  
    public object ToJson()
    {
        return new
        {
            lat = Latitude,
            lng = Longitude,
            itemsInCluster = Items.Count(),
            isClusterInOnePoint = IsClusterInOnePoint
        };
    }
}

Las propiedades Latitude y Longitude indican las coordenadas del mapa donde se encuentra el clúster. En la propiedad Items se almacenan los distintos elementos que hay en el clúster. Por último la propiedad IsClusterInOnePoint la utilizamos para indicar que los elementos están tan cerca (este umbral se específica cuando se invoca el clúster que por defecto es 5 metros) que pueden se considerados como un solo punto. La implementación de la interface IClusterProcessor queda de la siguiente forma:

public ClusterResult<E> DoCluster<E>(IEnumerable<E> items, int zoom, int pixelThreshold = 40, int threshold = 5)
    where E : IGeolocalizable
{
    var itemsWithoutCluster = new List<E>();
    var clusters = new List<Cluster<E>>();
    var list = items.ToList();
    var thresholdInMiles = GeolocalizationUtils.ConvertFromMetersToMiles(threshold);
    
    while (list.Count > 0)
    {
        var item = list[0];
        list.Remove(item);
        if (item.Latitude <= 0 || item.Longitude <= 0)
            continue;
  
        var count = 1;
        var isClusterInOnePoint = true;
        var clusteredItems = new List<E>();
  
        for (var i = 0; i < list.Count; i++)
        {
            var pixelDistance = GeolocalizationUtils.CalcPixelDistance(item.Latitude, item.Longitude, list[i].Latitude, list[i].Longitude, zoom);
  
            if (pixelThreshold > pixelDistance)
            {
                if (isClusterInOnePoint)
                {
                    var d = GeolocalizationUtils.CalcDistance(item.Latitude, item.Longitude, list[i].Latitude, list[i].Longitude);
                    isClusterInOnePoint = d <= thresholdInMiles;
                }
  
                clusteredItems.Add(item);
                count++;
                list.RemoveAt(i);
                i--;
            }
        }
  
        if (count == 1) //No Cluster was found...
            itemsWithoutCluster.Add(item);
        else
            clusters.Add(new Cluster<E>
            {
                Latitude = item.Latitude,
                Longitude = item.Longitude,
                IsClusterInOnePoint = isClusterInOnePoint,
                Items = clusteredItems
            });
    }
  
    return new ClusterResult<E> 
    {
        Clusters = clusters,
        Items = itemsWithoutCluster
    };
}

El algoritmo es muy sencillo. Se va recorriendo la lista, se escoge el primer elemento (E1), se elimina de la lista y se halla la distancia que existe entre E1 y el resto de elementos de la lista (En). Si la distancia es menor que el umbral que se especifica en el parámetro pixelThresold se elimina En y se conforma un clúster entre E1 y En, sucesivamente se le van añadiendo al clúster los elementos que no sobrepasan el umbral. Si la distancia entre todos los elementos que conforman el clúster es menor que el umbral especificado en el parámetro threshold entonces podemos decir que el clúster está solo en un punto, para esto se establece la propiedad IsClusterInOnePoint en “true”. El proceso continua hasta que la lista inicial esté totalmente vacía.

La lista que le debemos suministrar al método DoCluster debemos obtenerla de algún sitio, por ejemplo de una clase de servicio como se muestra a continuación:

public IEnumerable<User> GetByBounds(CoordsBound bound)
{
    return repository.GetFilteredElements(u =>
        (u.Longitude > bound.SouthWest.Longitude && u.Longitude < bound.NorthEast.Longitude) &&
        (u.Latitude <= bound.NorthEast.Latitude && u.Latitude >= bound.SouthWest.Latitude));
} 

Ahora solo nos queda ponerlo todo en marcha, esto lo hacemos en un método de una clase controladora de ASP.NET MVC de la siguiente forma:

public ActionResult GetGeolocalizedUsers(string northEast, string southWest, int zoom)
{
    var coordsBound = CoordsBound.Parse(southWest, northEast);
    IEnumerable<User> users = userService.GetByBounds(coordsBound);
    var clusterResult = clusterProcessor.DoCluster(users, zoom, 40, 5);
    
    var result = new ArrayList();
    
    foreach (var user in clusterResult.Items)
    {
        result.Add(user.ToJson());
    }
  
    foreach (var cluster in clusterResult.Clusters)
    {
        result.Add(cluster.ToJson());
    }
  
    return Json(result);
}

Primero se filtra la lista de usuarios según su posición geográfica. Luego se hace un clúster de esta selección y se envían los datos al cliente en formato JSON. Este código solo funciona en .NET 4.0 pues hace uso de la covarianza, nótese que la clase del servicio retorna una colección de User y necesitamos una colección de IGeolocalizable para aplicar el clúster, es ahí donde entra en juego la covarianza ya que User implementa IGeolocalizable.

Por ahora es suficiente, con esto quedaría solo proyectar la información en el mapa del lado del cliente lo cual queda fuera del alcance de esta entrada y que quizás en otro post comentemos.

Antes de finalizar comentar de otra técnica que se puede usar si no se quiere hacer clúster. Es posible obtener una serie de imágenes con la información que se quiere proyectar en el mapa y superponerlas a las imágenes del mapa que nos proporciona Google, esto se consigue trabajando con los “tiles” de Google Maps. Es de esta última forma como trabaja Panoramio pero esto lo mostraré en otro post, por ahora ya es algo para empezar y comenzar a divertirse con Google Maps o Bing (todo lo aquí explicado se aplica también a Bing).

3 comentarios:

R.R. Libera13 de diciembre de 2011, 20:06
Hector! Justo estoy trabajando en algo similar, tengo un dataset enorme (varias decenas de millones de registros) de tecnicos que reportan su posicion cada minuto; y se necesita reportar con umbrales variables de tiempo y diatancia para diferentes propositos.
Por ejemplo, en ciertos casos necesitas ver solo el recorrido del tecnico reportando puntos cada X metros (ignorando el resto) y/o cada Y minutos.
Estoy mirando el sorporte para spatial data en SQLServer 2008 con la esperanza de encontrar algo mas eficiente ahi, de lo contrario no me quedara otra que procesar todos los registros que entren en el marco de la consulta.
Un abrazo bro! Y sigue posteando!
ResponderEliminar
Respuestas
Héctor Luis Collado Fernández14 de diciembre de 2011, 1:05
Es raciel no????? sql server tiene buen soporte para datos geospatial y tiene muchos métodos implementados, de todas formas hay una librería q se llama SharpMap (o algo así) q tiene el mismo API (o bastante parecido, creo q es una recomendación estándar) q el de Sql Server, pero bueno... es cuestión de probar y tener suerte, jejeje, un abrazo h
pd: lo de postear lo tengo q retomar en breve, jajaja
ResponderEliminar
Respuestas
R.R. Libera14 de diciembre de 2011, 6:49
Si! Soy yo. Sigue posteando, que de ultima no te perjudica, y te ayuda a poner las ideas mas en claro.
Mira esto: http://channel9.msdn.com/Shows/HanselminutesOn9/Hanselminutes-on-9-Social-Networking-for-Developers-Part-1-Every-Developer-Needs-a-Blog

Yo hace tiempo quiero publicar algunas cosas, pero soy muy vago... pero ya me lo puse como objetivo.

Un abrazo, y sigue con el buen trabajo que estas haciendo!
ResponderEliminar
Respuestas

Añadir comentario

lunes, 18 de abril de 2011

Proyectando grandes Datasets en Google Maps

3 comentarios: