La optimización de un vecino más cercano cálculo utilizando PostGIS

Question

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

Hasta ahora tengo la gran ayuda de Mike Toews' respuesta (que cito con un cambio menor) 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

A continuación, he calculado el mínimo:

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

Sin embargo, mi reto es para calcular esto para un gran número de polígonos (1,000,000). Como el cálculo anterior se compara cada polígono a cada polígono, me pregunté cómo podría mejorar el cálculo, de forma que no tengo que realizar 10^12 cálculos.

Uno pensaba que yo tenía era la de búfer de cada polígono y, a continuación, para calcular la más cercana a los vecinos de todos los valores del buffer para que el polígono, y registrar el mínimo. No estoy seguro de si es el mejor enfoque, o si hay una función en PostGIS que me debe utilizar.

---

EDIT: el Uso de uno de Nicklas sugerencias, estoy experimentando con el 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

Esto devuelve una tabla de ID de cada polígono, y si es dentro de una cierta distancia o no. Es posible construir una IF/ELSE tipo de declaración utilizando SQL? (He leído acerca del uso de la CASE condición) O debo tratar de unirse a la mesa de lo que producen a la tabla original y, a continuación, ejecutar la consulta de nuevo el uso de ST_Distance?

Answer 1

Hay un gran "Vecino más Cercano" en el BostonGIS página.

---

EDITAR:

¿

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)

Sobre el CASO de la declaración:

SELECT a,
   CASE WHEN a=1 THEN 'one'
        WHEN a=2 THEN 'two'
        ELSE 'other'
   END
FROM test;

Answer 2

Hola

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

Primero, usted ha dicho que usted está considerando el uso de un tampón para encontrar polígonos en algunas rango mínimo para evitar el cálculo de todas las combinaciones.

Como se discutió en otro enlace de Boston sig de la manera correcta de hacerlo en PostGIS es el uso de ST_Dwithin. ST_Dwithin utiliza el índice para encontrar a los vecinos en un cierto rango.

Depende del conjunto de datos, por supuesto, si es suficiente el uso de un valor fijo para st_DWithin para todos los polígonos o si usted necesita para hacer algo como underdark y wildintellect están discutiendo.

Una segunda cosa es usar PostGIS 1.5+ aquí. Eso es porque polígono a polígono cálculos es mucho más rápido desde 1.5 en el caso de las cajas delimitadoras no se cruzan. Usted puede leer más acerca de esto aquí..

La tercera cosa a mencionar es el futuro.

En PostgreSQL 9.1 habrá algo que se llama knn-gist. Es un índice que no sólo puede responder sí o no, sino también devolver el resultado ordenado directamente desde el índice. Usted puede leer sobre esto aquí.

Pero todavía habrá un montón de trabajo que hacer en el PostGIS lado antes de knn esencia va a ayudar para cosas como esta. Hay un billete para que aquí.

Saludos

Nicklas

Answer 3

Las siguientes páginas relacionadas con Nathan Kerr es una de máster el trabajo de explicar en esta directos de emisión. Mi compañero de trabajo trató de la Bostongis método aquí y aquí, pero tenía algunos problemas para conseguir que funcione bien.

Otro enfoque para pensar que es similar a la de búfer es hacer una expansión/contracción rectángulo. Básicamente paso 1 hacer un cuadro delimitador (es una recta +x unidades de su original polígono del bbox) se intersecan que crees que va a coger al menos una intersección. Por los datos que tengo un cruzan realizar una sub consulta que las pruebas de esos partidos para los más cercanos. Para los datos que no se corresponden con expanda el cuadro delimitador y la repetición.

Es claramente un recurrente problema de programación, y podría ser mejor hecho en Python con Shapely de 100% directamente en postgis.