PostGIS puntos más cercanos con ST_Distance, kNN

23

Necesito obtener en cada elemento de una tabla el punto más cercano de otra tabla. La primera tabla contiene señales de tráfico y la segunda las salas de entrada de la ciudad. Lo que pasa es que no puedo usar la función ST_ClosestPoint y tengo que usar la función ST_Distance y obtener el registro min (ST_distance) pero estoy bastante atrapado construyendo la consulta.

CREATE TABLE traffic_signs
(
  id numeric(8,0) ),
  "GEOMETRY" geometry,
  CONSTRAINT traffic_signs_pkey PRIMARY KEY (id),
  CONSTRAINT traffic_signs_id_key UNIQUE (id)
)
WITH (
  OIDS=TRUE
);

CREATE TABLE entrance_halls
(
  id numeric(8,0) ),
  "GEOMETRY" geometry,
  CONSTRAINT entrance_halls_pkey PRIMARY KEY (id),
  CONSTRAINT entrance_halls_id_key UNIQUE (id)
)
WITH (
  OIDS=TRUE
);

Necesito obtener la identificación del entrnce_hall más cercano de cada señal de tráfico.

Mi consulta hasta ahora:

SELECT senal.id,port.id,ST_Distance(port."GEOMETRY",senal."GEOMETRY")  as dist
    FROM traffic_signs As senal, entrance_halls As port   
    ORDER BY senal.id,port.id,ST_Distance(port."GEOMETRY",senal."GEOMETRY")

Con esto obtengo la distancia de cada señal de tráfico a cada entrada. Pero, ¿cómo puedo obtener solo la distancia mínima?

Saludos,

Egidi
fuente
¿Qué versión de PostgreSQL?
Jakub Kania

Respuestas:

41

Ya casi estás ahí. Hay un pequeño truco que consiste en utilizar el operador distintivo de Postgres , que devolverá la primera coincidencia de cada combinación; como está ordenando por ST_Distance, efectivamente devolverá el punto más cercano de cada sello a cada puerto.

SELECT 
   DISTINCT ON (senal.id) senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY")  as dist
FROM traffic_signs As senal, entrance_halls As port   
ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Si sabe que la distancia mínima en cada caso no es más que cierta cantidad x (y tiene un índice espacial en sus tablas), puede acelerar esto poniendo WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", distance), por ejemplo, si se sabe que todas las distancias mínimas son no más de 10 km, entonces:

SELECT 
   DISTINCT ON (senal.id) senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY")  as dist
FROM traffic_signs As senal, entrance_halls As port  
WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", 10000) 
ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Obviamente, esto debe usarse con precaución, ya que si la distancia mínima es mayor, simplemente no obtendrá una fila para esa combinación de senal y puerto.

Nota: El orden por orden debe coincidir con el distinto en orden, lo que tiene sentido, ya que distinto toma el primer grupo distinto según algún orden.

Se supone que tiene un índice espacial en ambas tablas.

EDITAR 1 . Hay otra opción, que es utilizar los operadores <-> y <#> de Postgres (cálculos de distancia entre el punto central y el cuadro delimitador, respectivamente) que hacen un uso más eficiente del índice espacial y no requieren el truco ST_DWithin para evitar n ^ 2 comparaciones. Hay un buen artículo de blog que explica cómo funcionan. Lo más importante a tener en cuenta es que estos dos operadores funcionan en la cláusula ORDER BY.

SELECT senal.id, 
  (SELECT port.id 
   FROM entrance_halls as port 
   ORDER BY senal.geom <#> port.geom LIMIT 1)
FROM  traffic_signs as senal;

EDITAR 2 . Como esta pregunta ha recibido mucha atención y los vecinos más cercanos (kNN) son generalmente un problema difícil (en términos de tiempo de ejecución algorítmico) en SIG, parece que vale la pena ampliar un poco el alcance original de esta pregunta.

La forma estándar de encontrar los vecinos más cercanos x de un objeto es usar una UNIÓN LATERAL (conceptualmente similar a una para cada bucle). Tomando descaradamente la respuesta de Dbaston , harías algo como:

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports
      ORDER BY signs.geom <-> ports.geom
     LIMIT 1
   ) AS closest_port

Entonces, si desea encontrar los 10 puertos más cercanos, ordenados por distancia, simplemente tiene que cambiar la cláusula LIMIT en la subconsulta lateral. Esto es mucho más difícil de hacer sin LATERAL JOINS e implica el uso de la lógica de tipo ARRAY. Si bien este enfoque funciona bien, se puede acelerar enormemente si sabe que solo tiene que buscar a una distancia determinada. En este caso, puede usar ST_DWithin (signs.geom, ports.geom, 1000) en la subconsulta, que debido a la forma en que funciona la indexación con el operador <->, una de las geometrías debería ser una constante, en lugar de una referencia de columna: puede ser mucho más rápido. Entonces, por ejemplo, para obtener los 3 puertos más cercanos, dentro de los 10 km, podría escribir algo como lo siguiente.

 SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports
      WHERE ST_DWithin(ports.geom, signs.geom, 10000)
      ORDER BY ST_Distance(ports.geom, signs.geom)
     LIMIT 3
   ) AS closest_port;

Como siempre, el uso variará dependiendo de su distribución de datos y consultas, por lo que EXPLAIN es su mejor amigo.

Finalmente, hay un problema menor, si usa IZQUIERDA en lugar de CROSS JOIN LATERAL en el que debe agregar ON TRUE después del alias de consultas laterales, por ejemplo,

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
LEFT JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports          
      ORDER BY signs.geom <-> ports.geom
      LIMIT 1
   ) AS closest_port
   ON TRUE;
John Powell
fuente
Cabe señalar que esto no funcionará bien con grandes cantidades de datos.
Jakub Kania
@JakubKania. Depende de si puedes usar ST_DWithin o no. Pero sí, punto tomado. Desafortunadamente, el operador Ordenar por <-> / <#> requiere que una de las geometrías sea constante, ¿no?
John Powell
@ JohnPowellakaBarça ¿alguna posibilidad de saber dónde vive esa publicación de blog hoy en día? - o, ¿una explicación similar de los operadores <-> y <#>? ¡¡Gracias!!
DPSEspacial
@DPSSpatial, eso es molesto. No, pero hay esto y esto que habla un poco sobre este enfoque. La segunda, que también usa uniones laterales, que es otra mejora interesante.
John Powell
@DPSSpatial. Es todo un poco resbaladizo este <->, <#> y material de unión lateral. He hecho esto con conjuntos de datos muy grandes y el rendimiento ha sido horrible, sin usar ST_DWithin, que se supone que todo esto debe evitar. En última instancia, knn es un problema complicado, por lo que el uso puede variar. Buena suerte :-)
John Powell
13

Esto se puede hacer con un LATERAL JOINPostgreSQL 9.3+:

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
     id, 
     ST_Distance(ports.geom, signs.geom) as dist
     FROM ports
     ORDER BY signs.geom <-> ports.geom
   LIMIT 1) AS closest_port
dbaston
fuente
10

El enfoque con unión cruzada no utiliza índices y requiere mucha memoria. Entonces básicamente tienes dos opciones. Pre 9.3 usaría una subconsulta correlacionada. 9.3+ puedes usar a LATERAL JOIN.

KNN GIST con un giro lateral Próximamente en una base de datos cercana

(consultas exactas a seguir pronto)

Jakub Kania
fuente
1
Uso fresco de una unión lateral. No había visto eso antes en este contexto.
John Powell
1
@ JohnBarça Es uno de los mejores contextos que he visto. También sospecho que sería útil cuando realmente necesita usar ST_DISTANCE()para encontrar el polígono más cercano y la unión cruzada está causando que el servidor se quede sin memoria. La consulta de polígono más cercana sigue sin resolverse AFAIK.
Jakub Kania
2

@John Barça

ORDER BY está mal!

ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Correcto

senal.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY"),port.id;

de lo contrario, no devolverá el más cercano, solo el que tiene el pequeño ID de puerto

estiramiento
fuente
1
El correcto se ve así (usé puntos y líneas):SELECT DISTINCT ON (points.id) points.id, lines.id, ST_Distance(lines.geom, points.geom) as dist FROM development.passed_entries As points, development."de_muc_rawSections_cleaned" As lines ORDER BY points.id, ST_Distance(lines.geom, points.geom),lines.id;
blackgis
1
OK, te entiendo ahora. En realidad, probablemente sea mejor usar el enfoque LATERAL JOIN, como en la respuesta de @ dbaston, que deja en claro qué cosa se está comparando con qué otra cosa en términos de cercanía. Ya no uso el enfoque anterior.
John Powell el