Le portail francophone de la géomatique

Bonjour,

Les points étant en lat/long, vous pouvez utilisez le type GEOGRAPHY, qui permet un calcul des distances en tenant compte de la forme de la terre (calcul en coordonnées sphériques). Vous pouvez aussi utiliser la fonction st_distance_spheroid() sur votre table, pour calculer des distances exactes.
Vous pouvez également stocker le résultat final sous forme de LINESTRING, ou le startPoint serait le point de départ et le endPoint le point de destination.

Pour convertir votre table en geography WGS 84:

alter table trajets alter column point_origine type geography(point, 4326) using st_Transform(point_origine, 4326)::geography;
alter table trajets alter column point_destination type geography(point, 4326) using st_Transform(point_destination, 4326)::geography;

Il y a plusieurs façons de faire en fonction de la volumétrie de la table:

• si la table contient peu de lignes, un calcul de toutes les trajectoires possibles pour chaque destination, en ne gardant que la plus courte permet de répondre à la question. Cette méthode n'utilise pas les index, sauf si vous savez que les distances minimales ne seront jamais supérieures à une certaine distance. Les Windows Functions sont utiles, dans ce cas.

Le principe est de faire un croisement entre la table et elle même, pour pouvoir calculer tous les couples (origine-destination) et de classer par distance la plus petite pour chaque identifiant de destination:

Si Utilisation de distance_spheroid (point WGS 84) plutot que la reprojection de la table:

oid: identifiant du point_origine, did: identifiant du point destination, id: identifiant unique de la table trajet (PK)

with tmp as (
  select t.oid, t1.did, t1.id, t.point_origine, t1.point_destination, 
    row_number() over (PARTITION BY t1.did order by st_distance_Spheroid(t.point_origine, t1.point_destination, 'SPHEROID["WGS 84",6378137,298.257223563]')) as rn
  from trajets t, trajets t1
  
) select t.id, t.did, t.oid,
    -- construction de la ligne de trajet entre une destination et l'origine la plus proche
    st_makeLine(point_origine, point_destination) as geom
from tmp t
where rn = 1;

• Si la table contient bcp de lignes, il faut mieux utiliser un index sur les plus proches voisins, en cherchant pour chaque ligne le point le plus proche de chaque destination.
Cet opérateur de plus proche voisin ne marche que dans la clause ORDER BY d'une requete: il donne le point le plus proche d'un point donné.
Ici, on veut tester toutes les combinaisons entre destinations et origines pour trouver le trajet le plus court, on utilise l'opérateur dans une sous requete exprimée dans le SELECT:

La requete est plus complexe à écrire. (edit: en fait non, moins complexe meme )

SELECT DISTINCT on (t.did) t.did, t.id as dest_id, 
  (
    select t1.oid
    from trajets t1
    order by t1.point_origine <-> t.point_destination
    limit 1) as ori_id
from trajets t;

Pour reconstruire des lignes de trajets uniques comme dans l'exemple 1, il faut refaire des jointures à partir de cette requetes vers la table trajets: deux jointures pour pouvoir retrouver la ligne du point d'origine et la ligne du point destination.

La sous requete a été modifiée avec un DISTINCT ON pour faire apparaitre l'identifiant unique d'une ligne de destination.

with tmp as (
  SELECT DISTINCT on (t.did) t.did, t.id as dest_id, 
    (
      SELECT t1.id
      FROM trajets t1
      ORDER BY t1.point_origine <-> t.point_destination
      LIMIT 1) AS ori_id
  FROM trajets t
) select t.dest_id, st_makeline(tr1.point_origine, tr2.point_destination) as geom
from tmp t join trajets tr1 on t.ori_id = tr1.id
  join trajets tr2 on t.dest_id = tr2.id;

Nicolas