El Blog de Tagzania

FASE 2: Problema & Solución

Los cálculos de distancia en linea y poligonos seguían siendo costosos para nuestro servidor.

Por lo que utilizamos el siguiente criterio (postgis), para que todas las busquedas fueran lo más rápidas posibles: de punto a punto.

– Un punto no tiene problema alguno.

– Una linea ==> ST_StartPoint(line)

– Un poligono ==> ST_Centroid(polygon)

** Funciones Postgis – ya que en Geodjango no existe el startpoint de lineas.

Así:

SELECT a.* FROM items AS a WHERE a.id != %s

ORDER BY (

CASE WHEN a.item_type='POINT' THEN ST_Distance(

(SELECT CASE b.item_type WHEN 'POINT' THEN b.point

WHEN 'POLYLINE' THEN ST_StartPoint(b.geometry)

ELSE ST_Centroid(b.geometry)END FROM items AS b WHERE b.id= %s), a.point)

WHEN a.item_type='POLYLINE' THEN ST_Distance(

(SELECT CASE c.item_type WHEN 'POINT' THEN c.point

WHEN 'POLYLINE' THEN ST_StartPoint(b.geometry)

ELSE ST_Centroid(b.geometry)END FROM items AS c WHERE c.id= %s), ST_StartPoint(a.geometry)

WHEN a.item_type='POLYGON' THEN ST_Distance(

(SELECT CASE c.item_type WHEN 'POINT' THEN c.point

WHEN 'POLYLINE' THEN ST_StartPoint(b.geometry)

ELSE ST_Centroid(b.geometry)END FROM items AS c WHERE c.id= %s), ST_Centroid(a.geometry)

) END) LIMIT %s;

Pero el precálculo de StartPoint y Centroid por cada vez que se acceda a esta consulta seguía siendo costoso para el sistema.

Solución: Tomamos la decisión de crear un punto central (center_point) por cada elemento (POI), y así facilitar la operación de cálculo de distancias.

center_point = models.PointField(blank=True, null = True)

POINT =>> center_point = self.point

LINE =>> center_point = fromstr('POINT(' + line_coords[0]+ ')')

POLYGON =>> center_point = self.polygon.centroid

Con lo que ademas conseguiamos que geodjango aplicase directamente su función de distancia:

tzp = get_object_or_404(items, id = ***)

near_items = Items.objects.distance(tzp.center_point).order_by(’distance’)

RESUMIENDO:

Cada vez que insertemos una geometría, debemos realizar estos precálculos para que las consultas sean más agiles a la hora de buscar los puntos mas cercanos a este que estamos insertando.

1.- Simplificar tanto lineas(polyline) como los poligonos(polygon). SIMPLIFY()

2.- Crear un punto central por cada geometría. (center_point)

De esta manera conseguimos que la busqueda sea más ágil, aunque después, estas geometrías sean muy complicadas en cuanto a cantidad de intersecciones, … pero esto ya pasa a manos del navegador.

¡Nuestro servidor respira!

FASE 1: Problema & Solución

En los comienzos se realizaban consultas SQL sobre diferentes geometrías. Algo así:

SELECT a.* FROM items AS a WHERE a.id != %s

ORDER BY (

CASE WHEN a.item_type='POINT' THEN ST_Distance(

(SELECT CASE b.item_type WHEN 'POINT' THEN b.point  ELSE b.geometry END

FROM items AS b WHERE b.id= %s), a.point)

    WHEN a.item_type='POLYLINE' THEN ST_Distance(

(SELECT CASE c.item_type WHEN 'POINT' THEN c.point ELSE b.geometry END

FROM items AS c WHERE c.id= %s), ST_StartPoint(a.geometry)

    WHEN a.item_type='POLYGON' THEN ST_Distance(

(SELECT CASE c.item_type WHEN 'POINT' THEN c.point ELSE b.geometry END

FROM items AS c WHERE c.id= %s), ST_Centroid(a.geometry)

) END) LIMIT %s;

Nos dimos cuenta que teniamos lineas de mas de 5000 intersecciones/puntos, por lo que realizar el cálculo de distancia sobre cada intersección/punto de esa linea, era demasiado costoso para el servidor. Y a la hora de visualizarlo en el mapa, tardaba demasiado en dibujarlo.

Solución: Decidimos guardar la versión simplificada ( geodjango – simplify() ) de cada geometría. Crear un elemento neutro, en caso de lineas y poligonos, de modo simplificado. Utilizando diferentes criterios de tolerancia, a cuanto más puntos más tolerancia, menos intersecciones/puntos.

simple_line = models.LineStringField(blank=True, null=True)
simple_polyline = models.PolygonField(blank=True, null=True)

…

if len(self.line.array) > 1000:

self.simple_line = self.line.simplify(tolerance = 0.0013)

else:

if len(self.line.array) > 400:

tzp.simple_line = self.line.simplify(tolerance = 0.0011)

else:

self.simple_line = self.line.simplify(tolerance = 0.0002)

Pero esto tampoco terminaba de ir del todo bien …

Segiamos mejorando ….

Próximamente la parte (III)

En esta nueva etapa de Tagzania hemos apostado por la nueva tecnología que nos aporta el framework de Django. Dentro de esta encontramos una aplicación complementaria que nos hace las veces de ayuda para todas esas funciones de GIS que tanto necesitamos, GeoDjango.

Pero esta no es una clase de todas estas tecnologías.

Venimos a hablar de los diferentes problemas y soluciones que hemos tenido en todo este camino, al manejar todas las geometrías (point, line, polygon) que tratamos en nuestra aplicación.

Una de nuestras mayores necesidades es: “Encontrar los POI (Point of interest) mas cercanos a un punto concreto” (Nearest Neighbourds of geometry).

En el caso de Tagzania: utilizamos puntos, lineas y poligonos para la representación de POIs (puntos de interes).

class Item(models.Model):

point = models.PointField(blank=True, null = True) 

line = models.LineStringField(blank=True, null = True)

polygon = models.PolygonField(blank=True, null = True)

Todo ello conlleva procesos de cálculos complejos respecto a geometrías diferentes. Respecto a las lineas y los poligonos, las funciones como ST_Distance(geometry, geometry) tienen una carga excesiva en nuestro servidor.

Las diferentes funciones de GeoDjango solventan prácticamente la mayoría de nuestras necesidades, aúnque, aún falten funciones de postgis por implementar. Hemos probado las funciones de distancia (self.geometry.distance()) y resultan ser efectivas para distancias entre puntos, pero no para distancias entre geometrías que no sean puntos, por jemeplo: distancia entre una linea y un punto, tardaba demasiado…

Teniamos problemas de carga … (más información en la segunda parte)

Estamos trabajando a tope mejorando la nueva versión de Tagzania, resolviendo algunos bugs y optimizaciones. Gracias por vuestros comentarios y estad atentos ya que se acercan novedades.

Pero queríamos hacer una paradiña para tomar un poco de aire y enseñaros un pequeño hack en Tagzania.

Tagzania usa Mapstraction

En la mayor parte de los mapas de Tagzania, no utilizamos directamente el API de Google Maps. En su lugar utilizamos una inteligente librería llamada Mapstraction.

De su sitio web:

Mapstraction es una librería que provee un API común para varios APIs de mapas con javascript para permitir cambiar de uno al otro fácilmente. Los desarrolladores pueden escribir su aplicación una vez, y después cambiar fácilmente de proveedor de mapas basándose en las necesidades del projecto, términos y condiciones de uso o nuevas funcionalidades.

Suena bien, ¿no? Gracias a Mapstraction podemos enchufar cualquier servicio de mapas a Tagzania. Así que ahora puedes ver tus lugares de Tagzania con mapas de Yahoo, Microsoft u OpenStreetMaps.

Por ahora, puedes probarlo sólo con añadir un parámetro al final de tu URL de Tagzania, y recibirás la capa de mapas que corresponda.  Por ejemplo:

• San Sebastián en Google
• San Sebastián en OpenStreetmap
• San Sebastián en Yahoo
• San Sebastián en Microsoft
• San Sebastián en Freeearth
• … y algún otro que tendrás que adivinar

Así que si alguno de los sistemas de mapas tiene mejor cobertura en tu zona, puedes modificar la URL de Tagzania, agregando ?map=yahoo o ?map=microsoft o ?map=openstreetmap . Por ejemplo, mira la Ciudad Prohibida de Pekín cartografiada en OpenStreetMap.

Por ahora tendréis que hackear la URL para esto, pero estamos pensando ya en cómo implementar esto para todos los usuarios. Podría ser una opción en las preferencias, un combo en cada página o quizá dependiendo de lo que seleccione el que añada el lugar en Tagzania.