Zeichnen einer Linie zwischen Punkten in einem bestimmten Abstand in PostGIS?

9

Ich habe Daten von Punkten entlang der Straßen, ich möchte diese Punkte in einfache farbige Linien verwandeln. Gibt es Hinweise, wie dieses Problem genannt werden kann, oder Algorithmen, die mir bei der Lösung dieses Problems helfen können? Punkte entlang der Straße möchte ich in Linien verwandeln.

Ich hatte gehofft, PostGISFunktionen zu verwenden, aber ich bin offen für Vorschläge, dies sind Daten aus einer .shpDatei.

Bearbeiten1: Das Bild wurde aktualisiert, um die ideale Lösung dieses Problems zu demonstrieren.

Das Zeichnen der Linie basiert ausschließlich auf dem Abstand zwischen diesen Punkten. Es gibt nichts anderes, nach dem ich sie gruppieren kann. Idealerweise sind dies Punkte mit maximaler spezifizierter Entfernung entlang der projizierten Linie? Und mit projizierter Linie meine ich, finde den ersten Punkt und dann den nächstgelegenen, projiziere dann eine Linie und überprüfe, ob es auf dieser Linie Punkte in maximaler Entfernung zu denen gibt, die bereits auf der Linie sind.

Mahakala
quelle
1
Welche Software planen Sie zu verwenden?
ArMoraer
Versuchen Sie, diese in Bürgersteige zu verwandeln?
DPSSpatial
Ich hatte gehofft, dazu PostGIS-Funktionen verwenden zu können, bin aber offen für Vorschläge. Dies sind Daten aus einer .shp-Datei.
Mahakala
1
Können Sie genau zeigen, welche Punkte Sie in Ihrer Zeichnung oder in einer anderen Zeichnung verbinden möchten? Sind es nur zwei Punkte gleichzeitig? Oder drei? Ist der Abstand zwischen den zu verbindenden Punkten immer gleich oder liegt er "nur" unter einem bestimmten Schwellenwert?
Peter Horsbøll Møller
1
Vielen Dank an @dbaston und MarHoff. Ich werde erst Ende April Zeit haben, Ihre Ideen zu testen. Ich wünschte, ich könnte das Kopfgeld aufteilen, aber ich muss dies an einen von Ihnen vergeben, und dbaston hat mir auch einige Fragen gestellt also werde ich seine Antwort akzeptieren. Vielen Dank an alle, die sich die Zeit genommen haben zu antworten! Tolle Community, um Teil von zu sein :-)
Mahakala

Antworten:

8

.

Sie können eine rekursive Abfrage verwenden , um den nächsten Nachbarn jedes Punkts beginnend mit jedem erkannten Ende der Linien zu untersuchen, die Sie erstellen möchten.

Voraussetzungen : Bereiten Sie eine Postgis-Ebene mit Ihren Punkten und eine weitere mit einem einzelnen mehrzeiligen Objekt vor, das Ihre Straßen enthält. Die beiden Schichten müssen sich auf demselben CRS befinden. Hier ist der Code für den von mir erstellten Testdatensatz. Bitte ändern Sie ihn nach Bedarf. (Getestet auf Postgres 9.2 und 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),

Geben Sie hier die Bildbeschreibung ein

Hier sind die Schritte :

  1. Generieren Sie für jeden Punkt die Liste aller Nachbarn und ihrer Entfernung, die diese drei Kriterien erfüllen.

    • Die Entfernung darf einen benutzerdefinierten Schwellenwert nicht überschreiten (dies vermeidet die Verknüpfung mit einem isolierten Punkt). Geben Sie hier die Bildbeschreibung ein
      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
      ),
    • Der direkte Weg darf keine Straße überqueren Geben Sie hier die Bildbeschreibung ein
      graph as (
      SELECt graph_full.*
      FROM graph_full RIGHT JOIN
      roads ON st_intersects(graph_full.geom,roads.geom) = false
      ),
    • Die Entfernung darf ein benutzerdefiniertes Verhältnis der Entfernung zum nächsten Nachbarn nicht überschreiten (dies sollte einer unregelmäßigen Digitalisierung besser Rechnung tragen als eine feste Entfernung). Dieser Teil war tatsächlich zu schwer zu implementieren und hielt sich an einen festen Suchradius

    Nennen wir diese Tabelle "das Diagramm".

  2. Wählen Sie das Ende des Linienpunkts aus, indem Sie es mit dem Diagramm verbinden und nur Punkte beibehalten, die genau einen Eintrag im Diagramm haben. Geben Sie hier die Bildbeschreibung ein

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

    Nennen wir diese Tabelle "eol" (Zeilenende)
    einfach? dass die Belohnung für das Erstellen eines großartigen Diagramms, aber des Festhaltens, im nächsten Schritt verrückt wird

  3. Richten Sie eine rekursive Abfrage ein, die ab jedem Eol von Nachbarn zu Nachbarn wechselt Geben Sie hier die Bildbeschreibung ein

    • Initialisieren Sie die rekursive Abfrage mithilfe der Tabelle eol und fügen Sie einen Zähler für die Tiefe, einen Aggregator für den Pfad und einen Geometriekonstruktor zum Erstellen der Linien hinzu
    • Fahren Sie mit der nächsten Iteration fort, indem Sie mithilfe des Diagramms zum nächsten Nachbarn wechseln und sicherstellen, dass Sie den Pfad niemals rückwärts verwenden
    • Nachdem die Iteration abgeschlossen ist, behalten Sie nur den längsten Pfad für jeden Startpunkt bei (wenn Ihr Datensatz einen potenziellen Schnittpunkt zwischen Erwartungslinien enthält, würde dieser Teil mehr Bedingungen benötigen).
    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

    Nennen wir diese Tabelle "recurse_eol".

  4. Behalten Sie für jeden Startpunkt nur die längste Linie bei und entfernen Sie jeden exakten doppelten Pfad. Beispiel: Die Pfade 1, 2, 3, 5 und 5, 3, 2, 1 sind dieselbe Linie, die durch ihre zwei unterschiedlichen "Zeilenende" entdeckt wird.

    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. Überprüft manuell verbleibende Fehler (isolierte Punkte, überlappende Linien, seltsam geformte Straße)


Wie versprochen aktualisiert, kann ich immer noch nicht herausfinden, warum rekursive Abfragen manchmal nicht genau dasselbe Ergebnis liefern, wenn sie von der gegenüberliegenden EOL derselben Zeile ausgehen, sodass möglicherweise ab sofort ein Duplikat in der Ergebnisebene verbleibt.

Fühlen Sie sich frei zu fragen, ich verstehe total, dass dieser Code mehr Kommentare benötigt. Hier ist die vollständige Abfrage:

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
MarHoff
quelle
Hallo @MarHoff, danke für deine Antwort, ich habe etwas zu suchen. Ich hatte keine vollständige Lösung erwartet, nur einen Hinweis, wo ich nach Antworten suchen sollte. Ich möchte das besser verstehen und werde weiter graben und wahrscheinlich später weitere Fragen haben. Ich muss Ihren Algorithmus verstehen und das wird sowieso einige Zeit dauern :)
Mahakala
Habe ein funktionierendes Skript, Vorschau hier qgiscloud.com/MarHoff/test_qgiscloud_bis eine kleine Einschränkung für die Deduplizierung bleibt ... Keine Prämie mehr, keine Pression mehr, denke ich, also werde ich die Veröffentlichung veröffentlichen, wenn ich kann. Dieses Puzzle hat Spaß gemacht
MarHoff
danke @MarHoff, wenn ich könnte, hätte ich dieses Kopfgeld aufgeteilt. Ich kann nicht sehen, wie ich Ihnen Punkte geben kann, aber vielen Dank, dass Sie sich mit diesem und Ihrem Beweis befasst haben. Sieht echt aus :)
Mahakala
Getan. Vielen Dank für das Rätsel und entschuldigen Sie das Schimpfen. Wenn eine andere Antwort es für Sie getan hat, dann ist es völlig in Ordnung, manchmal ist einfach am besten ... Meine Antwort war vielleicht ein bisschen überlegt. Obwohl schönes Beispiel für die Verwendung von CTE + rekursive Abfrage + Windows-Funktion + Postgis für eine einzelne Abfrage;)
MarHoff
8

Wie @FelixIP hervorhebt, besteht der erste Schritt darin, die Punkte zu finden, aus denen jede Linie besteht. Sie können dies tun, indem Sie ST_ClusterWithin mit Ihrem maximalen Abstand aufrufen :

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

Anschließend müssen Sie eine Heuristik verwenden, um eine Linie durch alle Punkte in jedem Cluster zu erstellen. Wenn Sie beispielsweise annehmen können, dass die gewünschten Linien Y-monoton sind, können Sie die Punkte in jedem Cluster sortieren und in ST_MakeLine einspeisen . Das alles zusammen zu kombinieren würde so aussehen:

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
dbaston
quelle
Gut gemacht, aber der Y-monotone Ansatz (oder sogar das Umschalten zwischen X / Y-monoton) funktioniert nicht gut, wenn der Datensatz eine gekrümmte Straße enthält. Ist es der Fall? Der Bestellalgorithmus ist meiner Meinung nach der schwierigste Teil dieser Frage.
MarHoff
@MarHoff: Ja, gekrümmte Straßen werden ein Problem sein, aber ich versuche, die meisten Daten automatisch zu transformieren, und der Rest muss manuell erledigt werden. Oder ich werde mich weiter mit dem Thema befassen, um die Lösung herauszufinden, aber es kann länger dauern, bis jemand die verbleibenden Daten repariert. Ich muss die Ergebnisse auswerten, um entscheiden zu können. Vielen Dank für den Hinweis!
Mahakala
Statut getunt Ich dachte nur an einen Trick, den ich
ausprobieren
Gibt es eine robuste Möglichkeit, dies zu tun, bei der nicht alle möglichen Punktreihenfolgen ausprobiert und herausgefunden werden, welche die kürzeste Gesamtlänge ergibt?
Dbaston
Wenn diese Punktmengen immer den Straßen folgen, projizieren Sie die Position des Punkts auf das Straßensegment (ST_Line_Locate_Point) und ordnen die Punkte nach dem Ergebnis.
Travis