Points PostGIS les plus proches avec ST_Distance, kNN

J'ai besoin d'obtenir sur chaque élément d'une table le point le plus proche d'une autre table. La première table contient les panneaux de signalisation et la seconde les halls d'entrée de la ville. Le fait est que je ne peux pas utiliser la fonction ST_ClosestPoint et que je dois utiliser la fonction ST_Distance et obtenir l'enregistrement min (ST_distance) mais je suis assez bloqué dans la construction de la requête.

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
);

J'ai besoin d'obtenir l'id de l'entrnce_hall le plus proche de chaque traffic_sign.

Ma requête jusqu'à présent:

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")

Avec cela, j'obtiens la distance entre chaque panneau de signalisation et chaque hall d'entrée. Mais comment puis-je obtenir uniquement la distance minimale?

Cordialement,

Vous y êtes presque. Il y a une petite astuce qui consiste à utiliser l' opérateur distinct de Postgres , qui retournera la première correspondance de chaque combinaison - lorsque vous commandez par ST_Distance, en fait, il retournera le point le plus proche de chaque sénal à chaque port.

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 vous savez que la distance minimale dans chaque cas n'est pas supérieure à un certain montant x (et que vous avez un index spatial sur vos tables), vous pouvez accélérer cela en mettant un WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", distance), par exemple, si toutes les distances minimales sont connues pour être pas plus de 10 km, puis:

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");

Évidemment, cela doit être utilisé avec prudence, car si la distance minimale est plus grande, vous n'obtiendrez simplement aucune ligne pour cette combinaison de sénal et de port.

Remarque: l'ordre par ordre doit correspondre au distinct sur ordre, ce qui est logique, car distinct prend le premier groupe distinct basé sur un certain ordre.

Il est supposé que vous avez un index spatial sur les deux tables.

MODIFIER 1 . Il existe une autre option, qui consiste à utiliser les opérateurs <-> et <#> de Postgres (calculs du point central et du cadre de délimitation, respectivement) qui utilisent plus efficacement l'index spatial et ne nécessitent pas le hack ST_DWithin pour éviter n ^ 2 comparaisons. Il y a un bon article de blog expliquant comment ils fonctionnent. La chose générale à noter est que ces deux opérateurs fonctionnent dans la clause 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;

MODIFIER 2 . Comme cette question a reçu beaucoup d'attention et que les k-voisins les plus proches (kNN) sont généralement un problème difficile (en termes d'exécution algorithmique) dans les SIG, il semble utile d'étendre quelque peu la portée initiale de cette question.

La méthode standard pour trouver les x voisins les plus proches d'un objet est d'utiliser un LATERAL JOIN (conceptuellement similaire à un pour chaque boucle). Empruntant sans vergogne à la réponse de dbaston , vous feriez quelque chose comme:

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

Donc, si vous voulez trouver les 10 ports les plus proches, classés par distance, il vous suffit de modifier la clause LIMIT dans la sous-requête latérale. Ceci est beaucoup plus difficile à faire sans LATERAL JOINS et implique l'utilisation d'une logique de type ARRAY. Bien que cette approche fonctionne bien, elle peut être considérablement accélérée si vous savez que vous n'avez qu'à chercher à une distance donnée. Dans ce cas, vous pouvez utiliser ST_DWithin (signs.geom, ports.geom, 1000) dans la sous-requête, qui, en raison de la façon dont l'indexation fonctionne avec l'opérateur <-> - l'une des géométries doit être une constante plutôt qu'un référence de colonne - peut être beaucoup plus rapide. Ainsi, par exemple, pour obtenir les 3 ports les plus proches, à moins de 10 km, vous pouvez écrire quelque chose comme ceci.

 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;

Comme toujours, l'utilisation variera en fonction de votre distribution de données et de vos requêtes, EXPLAIN est donc votre meilleur ami.

Enfin, il y a un petit problème, si vous utilisez LEFT au lieu de CROSS JOIN LATERAL dans la mesure où vous devez ajouter ON TRUE après l'alias des requêtes latérales, par exemple,

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;

Cela peut être fait avec un LATERAL JOINdans 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

L'approche avec jointure croisée n'utilise pas d'index et nécessite beaucoup de mémoire. Vous avez donc essentiellement deux choix. Avant la version 9.3, vous utilisiez une sous-requête corrélée. 9.3+ vous pouvez utiliser a LATERAL JOIN.

KNN GIST avec une torsion latérale Bientôt dans une base de données près de chez vous

(requêtes exactes à suivre bientôt)

@John Barça

COMMANDER PAR est faux!

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

Droite

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

sinon il ne retournera pas le plus proche, seulement celui qui a le petit id de port