Tracer une ligne entre des points à une distance spécifique dans PostGIS?

J'ai une donnée de points le long des rues, je voudrais transformer ces points en simples lignes colorées. Y a-t-il des pointeurs sur le nom de ce problème ou des algorithmes qui peuvent m'aider à résoudre ce problème?

J'espérais utiliser des PostGISfonctions pour ce faire, mais je suis ouvert aux suggestions, il s'agit de données d'un .shpfichier.

Edit1: Mise à jour de l'image pour démontrer la solution idéale de ce problème.

Tracer la ligne serait uniquement basé sur la distance entre ces points, il n'y a rien d'autre que je puisse utiliser pour les regrouper. Idéalement, ce serait des points à une distance maximale spécifiée le long de la ligne projetée? Et par ligne projetée, je veux dire trouver le premier point puis le plus proche, puis projeter une ligne et vérifier s'il y a des points sur cette ligne à une distance maximale de ceux qui sont déjà sur la ligne.

La

Vous pouvez utiliser une requête récursive pour explorer le voisin le plus proche de chaque point à partir de chaque fin de ligne détectée que vous souhaitez créer.

Prérequis : préparez un calque postgis avec vos points et un autre avec un seul objet Multi-linestring contenant vos routes. Les deux couches doivent être sur le même CRS. Voici le code de l'ensemble de données de test que j'ai créé, veuillez le modifier si nécessaire. (Testé sur postgres 9.2 et postgis 2.1)

WITH RECURSIVE
points as (SELECT id, st_transform((st_dump(wkb_geometry)).geom,2154) as geom, my_comment as com FROM mypoints),
roads as (SELECT st_transform(ST_union(wkb_geometry),2154) as geom from highway),

Voici les étapes :

1. Générer pour chaque point la liste de tous les voisins et leur distance qui répondent à ces trois critères.

   • La distance ne doit pas dépasser un seuil défini par l'utilisateur (cela évitera la liaison avec un point isolé)

     graph_full as (
     SELECT a.id, b.id as link_id, a.com, st_makeline(a.geom,b.geom) as geom, st_distance(a.geom,b.geom) as distance
     FROM points a
     LEFT JOIN points b ON a.id<>b.id
     WHERE st_distance(a.geom,b.geom) <= 15
     ),

   • Le chemin direct ne doit pas traverser une route

     graph as (
     SELECt graph_full.*
     FROM graph_full RIGHT JOIN
     roads ON st_intersects(graph_full.geom,roads.geom) = false
     ),

   • La distance ne doit pas dépasser un rapport défini par l'utilisateur de la distance du plus proche voisin (cela devrait mieux s'adapter à la numérisation irrégulière que la distance fixe) Cette partie était en fait trop difficile à mettre en œuvre, collée à un rayon de recherche fixe

   Appelons ce tableau "le graphique"

2. Sélectionnez le point de fin de ligne en vous joignant au graphique et en ne gardant que le point qui a exactement une entrée dans le graphique.

   eol as (
   SELECT points.* FROM
   points  JOIN
   (SELECT id, count(*) FROM graph 
   GROUP BY id
   HAVING count(*)= 1) sel
   ON points.id = sel.id),

   Appelons ce tableau "eol" (fin de ligne)
   facile? que la récompense pour avoir fait un grand graphique mais les choses qui tiennent le coup deviendront folles à la prochaine étape

3. Configurer une requête récursive qui passera des voisins aux voisins à partir de chaque eol

   • Initialiser la requête récursive à l'aide de la table eol et en ajoutant un compteur pour la profondeur, un agrégateur pour le chemin et un constructeur de géométrie pour construire les lignes
   • Passez à l'itération suivante en passant au voisin le plus proche à l'aide du graphique et en vérifiant que vous ne reculez jamais en utilisant le chemin
   • Une fois l'itération terminée, ne conservez que le chemin le plus long pour chaque point de départ (si votre jeu de données comprend une intersection potentielle entre les lignes attendues, cette partie aurait besoin de plus de conditions)

   recurse_eol (id, link_id, depth, path, start_id, geom) AS (--initialisation
   SELECT id, link_id, depth, path, start_id, geom FROM (
       SELECT eol.id, graph.link_id,1 as depth,
       ARRAY[eol.id, graph.link_id] as path,
       eol.id as start_id,
       graph.geom as geom,
       (row_number() OVER (PARTITION BY eol.id ORDER BY distance asc))=1 as test
       FROM eol JOIn graph ON eol.id = graph.id 
       ) foo
   WHERE test = true
   
   UNION ALL ---here start the recursive part
   
   SELECT id, link_id, depth, path, start_id, geom  FROM (
       SELECT graph.id, graph.link_id, r.depth+1 as depth,
       path || graph.link_id as path,
       r.start_id,
       ST_union(r.geom,graph.geom) as geom,
       (row_number() OVER (PARTITION BY r.id ORDER BY distance asc))=1 as test
       FROM recurse_eol r JOIN graph ON r.link_id = graph.id AND NOT graph.link_id = ANY(path)) foo
   WHERE test = true AND depth < 1000), --this last line is a safe guard to stop recurring after 1000 run adapt it as needed

   Appelons cette table "recurse_eol"

4. Conserver uniquement la ligne la plus longue pour chaque point de départ et supprimer tous les chemins exacts en double Exemple: les chemins 1, 2, 3, 5 et 5, 3, 2, 1 sont la même ligne découverte par ses deux "fins de ligne" différentes

   result as (SELECT start_id, path, depth, geom FROM
   (SELECT *,
   row_number() OVER (PARTITION BY array(SELECT * FROM unnest(path) ORDER BY 1))=1 as test_duplicate,
   (max(depth) OVER (PARTITION BY start_id))=depth as test_depth
   FROM recurse_eol) foo
   WHERE  test_depth = true AND test_duplicate = true)
   
   SELECT * FROM result

5. Vérifie manuellement les erreurs restantes (points isolés, lignes qui se chevauchent, rue de forme étrange)

Mis à jour comme promis, je n'arrive toujours pas à comprendre pourquoi parfois une requête récursive ne donne pas exactement le même résultat en commençant à partir de l'éol opposé d'une même ligne, donc certains doublons peuvent rester dans la couche résultat à partir de maintenant.

N'hésitez pas à demander, je comprends totalement que ce code ait besoin de plus de commentaires. Voici la requête complète:

WITH RECURSIVE
points as (SELECT id, st_transform((st_dump(wkb_geometry)).geom,2154) as geom, my_comment as com FROM mypoints),
roads as (SELECT st_transform(ST_union(wkb_geometry),2154) as geom from highway),

graph_full as (
    SELECT a.id, b.id as link_id, a.com, st_makeline(a.geom,b.geom) as geom, st_distance(a.geom,b.geom) as distance
    FROM points a
    LEFT JOIN points b ON a.id<>b.id
    WHERE st_distance(a.geom,b.geom) <= 15
    ),

graph as (
    SELECt graph_full.*
    FROM graph_full RIGHT JOIN
    roads ON st_intersects(graph_full.geom,roads.geom) = false
    ),

eol as (
    SELECT points.* FROM
    points  JOIN
        (SELECT id, count(*) FROM graph 
        GROUP BY id
        HAVING count(*)= 1) sel
    ON points.id = sel.id),


recurse_eol (id, link_id, depth, path, start_id, geom) AS (
    SELECT id, link_id, depth, path, start_id, geom FROM (
        SELECT eol.id, graph.link_id,1 as depth,
        ARRAY[eol.id, graph.link_id] as path,
        eol.id as start_id,
        graph.geom as geom,
        (row_number() OVER (PARTITION BY eol.id ORDER BY distance asc))=1 as test
        FROM eol JOIn graph ON eol.id = graph.id 
        ) foo
    WHERE test = true

UNION ALL
    SELECT id, link_id, depth, path, start_id, geom  FROM (
        SELECT graph.id, graph.link_id, r.depth+1 as depth,
        path || graph.link_id as path,
        r.start_id,
        ST_union(r.geom,graph.geom) as geom,
        (row_number() OVER (PARTITION BY r.id ORDER BY distance asc))=1 as test
        FROM recurse_eol r JOIN graph ON r.link_id = graph.id AND NOT graph.link_id = ANY(path)) foo
    WHERE test = true AND depth < 1000),

result as (SELECT start_id, path, depth, geom FROM
    (SELECT *,
    row_number() OVER (PARTITION BY array(SELECT * FROM unnest(path) ORDER BY 1))=1 as test_duplicate,
    (max(depth) OVER (PARTITION BY start_id))=depth as test_depth
    FROM recurse_eol) foo
WHERE  test_depth = true AND test_duplicate = true)

SELECT * FROM result

Comme le souligne @FelixIP, la première étape consiste à trouver les points qui composeront chaque ligne. Vous pouvez le faire en appelant ST_ClusterWithin avec votre distance de séparation maximale:

SELECT
  row_number() OVER () AS cid, 
  (ST_Dump(geom)).geom 
FROM (
  SELECT unnest(st_clusterwithin(geom, 0.05)) AS geom 
  FROM inputs) sq

Ensuite, vous devrez utiliser une heuristique pour construire une ligne à travers tous les points de chaque cluster. Par exemple, si vous pouvez supposer que les lignes souhaitées sont monotones Y, vous pouvez trier les points dans chaque cluster et les alimenter dans ST_MakeLine . Combiner tout cela ressemblerait à ceci:

SELECT 
  ST_MakeLine(geom ORDER BY ST_Y(geom)) AS geom
FROM (
  SELECT row_number() OVER () AS cid, 
  (ST_Dump(geom)).geom FROM (
    SELECT unnest(st_clusterwithin(geom, 0.05)) AS geom 
    FROM inputs) sq) ssq 
GROUP BY cid