Optimizar un cálculo de vecino más cercano usando PostGIS

13

Estoy usando PostGIS para calcular los vecinos más cercanos de polígonos. Lo que quiero calcular es la distancia mínima desde cada polígono hasta el polígono más cercano.

Hasta ahora he recibido una gran ayuda de la respuesta de Mike Toews (que cito con un pequeño cambio) aquí:

SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_Distance(a.the_geom, b.the_geom) AS distance_between_a_and_b
FROM 
  public."TestArea" AS a, public."TestArea" AS b
WHERE
  a.hgt !=  b.hgt AND ST_Distance(a.the_geom, b.the_geom) < 400

Luego calculé el mínimo:

SELECT a_hgt, MIN(distance_between_a_and_b)
FROM public."lon_TestArea"
GROUP BY a_hgt

Sin embargo, mi desafío es calcular esto para una gran cantidad de polígonos (1,000,000). Como el cálculo anterior compara cada polígono con cualquier otro polígono, me pregunté cómo podría mejorar el cálculo para no tener que realizar 10 ^ 12 cálculos.

Uno pensaba que tenía que almacenar cada polígono en el búfer y luego calcular los vecinos más cercanos de todos los valores dentro del búfer para ese polígono y registrar el mínimo. No estoy seguro de si ese es el mejor enfoque, o si hay una función en PostGIS que debería estar usando.


EDITAR: Utilizando una de las sugerencias de Nicklas, estoy experimentando con ST_Dwithin():

CREATE TABLE mytable_withinRange AS SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_DWithin(a.the_geom, b.the_geom, 400)
FROM 
  public."lon_TestArea" AS a, public."lon_TestArea" AS b

ingrese la descripción de la imagen aquí

Esto devuelve una tabla de la ID de cada polígono, y si está dentro de una cierta distancia o no. ¿Es posible construir una IF/ELSEdeclaración de tipo usando SQL? (Leí sobre el uso de la CASEcondición) ¿O debería intentar unir la tabla que produzco a la tabla original y luego volver a ejecutar la consulta usando ST_Distance?

djq
fuente
Eche un vistazo al segundo ejemplo en el enlace gis de boston en mi respuesta. debe usar st_dwithin en la parte where de la consulta.
Nicklas Avén

Respuestas:

7

Hay una gran sección de "Vecino más cercano" en la página de BostonGIS .


EDITAR:

Qué tal si

CREATE TABLE mytable_withinRange AS SELECT 
 a.hgt AS a_hgt,
 b.hgt AS b_hgt
FROM 
 public."lon_TestArea" AS a, public."lon_TestArea" AS b
WHERE 
 ST_DWithin(a.the_geom, b.the_geom, 400)

Con respecto a la declaración CASE :

SELECT a,
   CASE WHEN a=1 THEN 'one'
        WHEN a=2 THEN 'two'
        ELSE 'other'
   END
FROM test;
bajo oscuro
fuente
¿Sabes si la línea WHERE ST_DWithin(a.the_geom, b.the_geom, 400)evitará distancias mayores 400que las calculadas o simplemente registradas? Además, ¿se puede usar una declaración de caso para cálculos numéricos? por ejemplo:CASE WHEN ST_DWithin(a.the_geom, b.the_geom, 400) == TRUE THEN ST_DWithin(a.the_geom, b.the_geom)
djq
1
@celenius Si la distancia es superior a 400 m, no se calculará nada en la parte seleccionada. No entiendo por qué quieres poner el caso en la mezcla.
Nicklas Avén
@Nicklas ok, entiendo. Pensé que podría haber significado que solo se almacenaban distancias inferiores a 400; Sin embargo, esto lo hace mucho más fácil que yo. ¡Gracias!
djq
3

Hola

Hay algunas cosas que se consideran para que las cosas se muevan más rápido, y algunas cosas que podrían ser posibles en el futuro.

Primero , mencionó que está considerando usar un búfer para encontrar polígonos en un rango mínimo para evitar calcular todas las combinaciones.

Como se discutió en otro enlace de Boston gis, la forma correcta de hacerlo en PostGIS es usar ST_Dwithin . ST_Dwithin usa el índice para encontrar los vecinos en un cierto rango.

Depende del conjunto de datos, por supuesto, si es suficiente usar un valor fijo para st_DWithin para todos los polígonos o si necesita hacer algo como discutir sobre underdark y wildintellect.

Una segunda cosa es usar PostGIS 1.5+ aquí. Esto se debe a que los cálculos de polígono a polígono son mucho más rápidos desde 1.5 si sus cuadros delimitadores no se cruzan. Puedes leer más sobre eso aquí. .

La tercera cosa a mencionar es el futuro.

En PostgreSQL 9.1 habrá algo llamado knn-gist. Ese es un índice que no solo puede responder sí o no, sino también devolver el resultado ordenado directamente desde el índice. Puedes leer sobre eso aquí .

Pero todavía habrá mucho trabajo por hacer en el lado de PostGIS antes de que knn gist ayude en cosas como esta. Hay un boleto para eso aquí.

Saludos

Nicklas

Nicklas Avén
fuente
Gracias por las sugerencias Nicklas; Como me ha resultado difícil poner en funcionamiento pgAdmin / PostGIS, creo que evitaré usar 1.5 en este momento. Parece que ST_Dwithin () es una forma de resolver esto.
djq
2
instalar 1.5 no afectará la relación entre postgresql y pgadmin. puede tener más de una versión de postgis en el servidor de la base de datos y luego cargar una de ellas en la base de datos. para que pueda tener una base de datos 1.4 y una 1.5, el mismo servidor de base de datos.
Nicklas Avén
1

Las siguientes páginas relacionadas con el trabajo de los maestros de Nathan Kerr proporcionan una buena idea de este problema directo. Mi compañero de trabajo probó el método Bostongis aquí y aquí , pero tuvo algunos problemas para que funcione correctamente.

Otro enfoque para pensar que es similar al búfer es hacer un rectángulo de expansión / contracción. Básicamente, pase 1 y haga un cuadro delimitador (es una unidad recta + x a la caja de su polígono original) intersección que cree que atrapará al menos una intersección. Para los datos que obtuvieron una intersección, realice una subconsulta que pruebe esas coincidencias para el más cercano. Para los datos, el error no coincide, expanda el cuadro delimitador y repita.

Es claramente un problema de programación recursivo, y podría hacerse mejor en Python con Shapely que 100% directamente en postgis.

intelecto salvaje
fuente