Rysowanie linii między punktami w określonej odległości w PostGIS?

Mam dane punktów wzdłuż ulic, chciałbym zamienić te kropki w proste kolorowe linie. Wszelkie wskazówki, jak można nazwać ten problem lub algorytmy, które mogą mi pomóc w rozwiązaniu tego problemu?

Miałem nadzieję, że użyję do tego PostGISfunkcji, ale jestem otwarty na sugestie, to dane z .shppliku.

Edycja1: Zaktualizowano obraz, aby zademonstrować idealne rozwiązanie tego problemu.

Narysowanie linii byłoby oparte wyłącznie na odległości między tymi punktami, nic więcej nie mogę użyć do ich grupowania. Idealnie byłyby to punkty w maksymalnej określonej odległości wzdłuż rzutowanej linii? I przez rzutowaną linię mam na myśli znaleźć pierwszy punkt, a następnie następny najbliższy, a następnie rzutować linię i sprawdzić, czy są jakieś punkty na tej linii w maksymalnej odległości od któregokolwiek z tych już na linii.

W pobliżu

Możesz użyć zapytania rekurencyjnego, aby zbadać najbliższego sąsiada każdego punktu, zaczynając od każdego wykrytego końca linii, które chcesz zbudować.

Wymagania wstępne : przygotuj warstwę Postgis ze swoimi punktami, a drugą za pomocą jednego obiektu z wieloma liniami zawierającymi Twoje drogi. Dwie warstwy muszą znajdować się na tym samym CRS. Oto kod zestawu danych testowych, który utworzyłem, zmodyfikuj go w razie potrzeby. (Testowane na postgres 9.2 i 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),

Oto kroki :

1. Wygeneruj dla każdego punktu listę wszystkich sąsiadów i ich odległości spełniających te trzy kryteria.

   • Odległość nie może przekraczać progu zdefiniowanego przez użytkownika (pozwoli to uniknąć połączenia z izolowanym punktem)

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

   • Bezpośrednia ścieżka nie może przechodzić przez jezdnię

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

   • Odległość nie może przekraczać zdefiniowanego przez użytkownika stosunku odległości od najbliższego sąsiada (powinno to lepiej uwzględniać digitalizację nieregularną niż stała odległość) Ta część była zbyt trudna do wdrożenia, przyklejona do ustalonego promienia wyszukiwania

   Nazwijmy tę tabelę „wykresem”

2. Wybierz punkt końca linii, łącząc się z wykresem i zachowując tylko punkt, który ma dokładnie jedną pozycję na wykresie.

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

   Nazwijmy tę tabelę „eol” (koniec linii)
   łatwym? że nagroda za wykonanie świetnego wykresu, ale trzymanie się rzeczy oszaleje w następnym kroku

3. Skonfiguruj zapytanie rekurencyjne, które będzie przełączać się między sąsiadami, zaczynając od każdego eol

   • Zainicjuj zapytanie rekurencyjne za pomocą tabeli eol i dodając licznik głębokości, agregator ścieżki i konstruktor geometrii, aby zbudować linie
   • Przejdź do następnej iteracji, przełączając się do najbliższego sąsiada za pomocą wykresu i sprawdzając, czy nigdy nie cofasz się ścieżką
   • Po zakończeniu iteracji zachowaj tylko najdłuższą ścieżkę dla każdego punktu początkowego (jeśli zestaw danych zawiera potencjalne przecięcie między liniami oczekiwanymi, ta część wymagałaby więcej warunków)

   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

   Nazwijmy tę tabelę „recurse_eol”

4. Zachowaj tylko najdłuższą linię dla każdego punktu początkowego i usuń każdą dokładnie zduplikowaną ścieżkę Przykład: ścieżki 1,2,3,5 I 5,3,2,1 to ta sama linia odkryta przez dwie różne „końcówkę linii”

   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. Ręcznie sprawdza pozostałe błędy (pojedyncze punkty, nakładające się linie, dziwnie ukształtowana ulica)

Zaktualizowany zgodnie z obietnicą, wciąż nie mogę zrozumieć, dlaczego czasami zapytanie rekurencyjne nie daje dokładnie tego samego wyniku, gdy zaczynasz od przeciwnego eol tego samego wiersza, więc niektóre duplikaty mogą na razie pozostać w warstwie wyników.

Nie wahaj się zapytać. Całkowicie rozumiem, że ten kod wymaga więcej komentarzy. Oto pełne zapytanie:

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

Jak wskazuje @FelixIP, pierwszym krokiem jest znalezienie punktów, które utworzą każdą linię. Możesz to zrobić, wywołując ST_ClusterWithin z maksymalną odległością separacji:

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

Następnie musisz użyć heurystyki, aby zbudować linię przechodzącą przez wszystkie punkty w każdym klastrze. Na przykład, jeśli możesz założyć, że żądane linie są monotoniczne Y, możesz posortować punkty w każdym klastrze i wprowadzić je do ST_MakeLine . Łącząc to wszystko razem wyglądałoby to tak:

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