PostGIS puntos más cercanos con ST_Distance, kNN

Question

Necesito obtener en cada elemento de una tabla el punto más cercano de otra tabla. La primera tabla contiene las señales de tráfico y la segunda las entradas de la ciudad. El caso 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 atascado 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 el id de la entrada más cercana 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 estoy obteniendo la distancia de cada señal de tráfico a cada entrada. Pero, ¿cómo puedo obtener sólo la distancia mínima?

Saludos,

Answer 1

Ya casi está. Hay un pequeño truco que consiste en utilizar la función de Postgres operador distinto que devolverá la primera coincidencia de cada combinación -- como está ordenando por ST_Distancia, efectivamente devolverá el punto más cercano de cada senal 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 sabes que la distancia mínima en cada caso no es mayor que alguna cantidad x, (y tienes un índice espacial en tus tablas), puedes acelerar esto poniendo un WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", distance) Por ejemplo, si se sabe que todas las distancias mínimas no superan los 10 km:

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ás ninguna fila para esa combinación de senal y puerto.

Nota: El orden por orden debe coincidir con el orden de distinct on, lo cual tiene sentido, ya que distinct está tomando el primer grupo distinto basado en 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 de punto central y caja delimitadora, respectivamente) que hacen un uso más eficiente del índice espacial y no requieren el hack ST_DWithin para evitar n^2 comparaciones. Hay una buena artículo del blog explicando su funcionamiento. Lo general 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 . Dado que esta cuestión ha recibido mucha atención y que los vecinos más cercanos (kNN) suelen ser un problema difícil (en términos de tiempo de ejecución algorítmica) en los SIG, parece que merece la pena ampliar un poco el alcance original de esta cuestión.

La forma estándar de encontrar los x vecinos más cercanos de un objeto es utilizar un LATERAL JOIN (conceptualmente similar a un bucle for each). Tomando prestado descaradamente de 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

Así, si quiere encontrar los 10 puertos más cercanos, ordenados por distancia, sólo 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 lógica de tipo ARRAY. Aunque este enfoque funciona bien, puede acelerarse enormemente si se sabe que sólo hay que buscar hasta una distancia determinada. En este caso, puede utilizar ST_DWithin (signos.geom, puertos.geom, 1000) en la subconsulta, que debido a la forma en que funciona la indexación con el operador <-> -- una de las geometrías debe ser una constante, en lugar de una referencia de columna -- puede ser mucho más rápido. Así, por ejemplo, para obtener los 3 puertos más cercanos, en un radio de 10km, se 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á en función de la distribución de los datos y las consultas, por lo que EXPLICAR es tu mejor amigo.

Por último, hay un pequeño inconveniente, si se utiliza IZQUIERDA en lugar de UNIÓN LATERAL CRUZADA en que hay que añadir ON TRUE después del alias de las 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;

Answer 2

Esto puede hacerse con un LATERAL JOIN en PostgreSQL 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

Answer 3

El enfoque con cross-join no utiliza índices y requiere mucha memoria. Así que básicamente tienes dos opciones. Antes de la versión 9.3 se utilizaba una subconsulta correlacionada. 9.3+ puedes usar una LATERAL JOIN .

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

(las consultas exactas se harán en breve)

Answer 4

@John Barça

ORDER BY está mal.

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

A la derecha

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

de lo contrario no devolverá el más cercano, sólo el que tenga el id de puerto pequeño

Answer 5

Si sólo está interesado en una consulta que devuelva los puntos más cercanos a su punto de referencia, entonces esto también serviría:

select senal.id,port.id, st_closestPoint(port."GEOMETRY",senal."GEOMETRY" 
    FROM traffic_signs As senal, entrance_halls As port