Gebogene Punkt-zu-Punkt-Routenkarten

39

Ich habe mir kürzlich Webseiten von Fluggesellschaften angesehen, auf denen deren Routen von einer bestimmten Stadt zu allen anderen Städten, die sie bedienen, angezeigt werden. Ich möchte in der Lage sein, ähnlich gekrümmte Routen zwischen Punkten zu erstellen. Hat jemand Skripte oder Funktionen erstellt, die die in diesem Beispiel gezeigten gekrümmten Bögen erzeugen ?

Flugpfade

Gibt es in PostGIS eine Implementierung von ST_MakeLine, mit der Sie die Menge der Kurve angeben können, die beim Verbinden von 2 Punkten verwendet werden soll?

Während ich derzeit PostGIS und QGIS verwende, würde ich mich über weitere Softwareoptionen freuen, die möglicherweise das gleiche Erscheinungsbild erzielen.

RyanDalton
quelle
Kennt jemand irgendwelche netten Implementierungen davon? Beispiele oder was auch immer?
Mark Boulder

Antworten:

26

Wenn Sie große Kreise erstellen, können Sie den gewünschten Effekt erzielen.

Vielleicht wird so etwas auf http://lists.osgeo.org/pipermail/postgis-users/2008-February/018620.html diskutiert

Aktualisieren:

Ich habe diese Idee in "Visualisierung globaler Verbindungen" weiterverfolgt . Es handelt sich um eine rein PostGIS-basierte Lösung, bei der zur Erstellung von Bögen eine Neuprojektion verwendet wird.

SELECT ST_Transform(
  ST_Segmentize(
    ST_MakeLine(
      ST_Transform(a.the_geom, 953027),
      ST_Transform(b.the_geom, 953027)
    ), 
  100000), 
4326)

(Die CRS-Definition für 953027 finden Sie hier: http://spatialreference.org/ref/esri/53027/ )

Bildbeschreibung hier eingeben

Underdunkel
quelle
4
Ich mag die Idee, obwohl bei großen Kreisen das Problem ist, dass Sie bei kürzeren Entfernungen immer noch eine im Allgemeinen gerade Linie haben. Ich möchte in der Lage sein, den Betrag des Bogens zu steuern, den ich in die Linie einfüge (dh Bogenlänge = Abstand * 2).
RyanDalton
1
Hier ist ein gutes Beispiel für das Problem mit der einfachen Verwendung von großen Kreisen: gc.kls2.com/cgi-bin/…
RyanDalton
1
Nach einigen zusätzlichen Recherchen habe ich diesen Beitrag gefunden, der bei der Unterstützung dieser Methode hilfreich sein kann. mail-archive.com/[email protected]/…
RyanDalton
Für zukünftige Leser dachte ich, ich würde einfach auf @ underdarks jüngsten Blog-Post verweisen, der dieses Thema behandelt. underdark.wordpress.com/2011/08/20/…
RyanDalton
Das ist großartig!! Wird in meinem Projekt zum Zeichnen von Linien zwischen Benutzer-Checkins und Veranstaltungsorten verwendet und von Forsquare
Lorenzo Barbagli
24

Das Problem besteht darin, herauszufinden, wie stark die Bögen gebogen werden müssen, um ihre visuelle Auflösung zu verbessern.

Hier ist eine Lösung (unter den vielen möglichen). Betrachten wir alle Bögen, die von einem gemeinsamen Ursprung ausgehen. Die Bögen werden hier am meisten überfüllt. Um sie am besten zu trennen, ordnen wir sie so an, dass sie sich in gleichmäßigen Winkeln ausbreiten . Es ist ein Problem, wenn wir gerade Liniensegmente vom Ursprung zu den Zielen zeichnen, da es normalerweise Zielgruppen in verschiedenen Richtungen gibt. Lassen Sie uns unsere Freiheit nutzen, um die Bögen zu biegen, um die Abweichungswinkel so gleichmäßig wie möglich zu verteilen.

Zur Vereinfachung verwenden wir Kreisbögen auf der Karte. Ein natürliches Maß für die "Biegung" in einem Bogen von Punkt y zu Punkt x ist die Differenz zwischen seiner Peilung bei y und der Peilung direkt von y zu x . Ein solcher Bogen ist ein Kreisabschnitt, auf dem y und x liegen; Die Elementargeometrie zeigt, dass der Biegewinkel die Hälfte des im Bogen enthaltenen Winkels beträgt.

Um einen Algorithmus zu beschreiben, brauchen wir etwas mehr Notation. Sei y der Ursprungspunkt (wie auf der Karte projiziert) und sei x_1 , x_2 , ..., x_n der Zielpunkt. Definieren Sie a_i als Peilung von y nach x_i , i = 1, 2, ..., n .

Als ersten Schritt nehmen wir an, dass die Lager (alle zwischen 0 und 360 Grad) in aufsteigender Reihenfolge sind: Dies erfordert, dass wir die Lager berechnen und sie dann sortieren; beides sind unkomplizierte aufgaben.

Idealerweise möchten wir, dass die Peilung der Bögen 360 / n , 2 * 360 / n usw. entspricht, bezogen auf ein Startlager. Die Differenzen zwischen den gewünschten Lagern und den tatsächlichen Lagern betragen daher i * 360 / n - a_i zuzüglich des Startlagers a0 . Die größte Differenz ist das Maximum dieser n Differenzen und die kleinste Differenz ist ihr Minimum. Stellen wir a0 so ein , dass es auf halbem Weg zwischen dem Maximum und dem Minimum liegt. Dies ist ein guter Kandidat für das Startlager, da es das maximale Ausmaß der auftretenden Biegung minimiert . Folglich definieren

b_i = i * 360 / n - a0 - a_i:

Dies ist das Biegen zu verwenden .

Es ist eine Frage der Elementargeometrie, einen Kreisbogen von y nach x zu zeichnen, der einen Winkel von 2 b_i einschließt. Daher überspringe ich die Details und gehe direkt zu einem Beispiel. Hier finden Sie Abbildungen der Lösungen für 64, 16 und 4 zufällige Punkte in einer rechteckigen Karte

Alt-Text

Alt-Text

Alt-Text

Wie Sie sehen können, scheinen die Lösungen zu erhalten schöner als die Anzahl der Zielpunkte erhöht. Die Lösung für n = 4 zeigt deutlich, wie die Lager gleichmäßig verteilt sind, denn in diesem Fall beträgt der Abstand 360/4 = 90 Grad und offensichtlich wird dieser Abstand genau erreicht.

Diese Lösung ist nicht perfekt: Sie können wahrscheinlich mehrere Bögen identifizieren, die manuell optimiert werden könnten, um die Grafik zu verbessern. Aber es wird keine schreckliche Arbeit leisten und scheint ein wirklich guter Anfang zu sein.

Der Algorithmus hat auch den Vorteil, dass er einfach ist: Der komplizierteste Teil besteht darin, die Ziele nach ihrer Peilung zu sortieren.


Codierung

Ich kenne PostGIS nicht, aber vielleicht kann der Code, mit dem ich die Beispiele gezeichnet habe, als Leitfaden für die Implementierung dieses Algorithmus in PostGIS (oder einem anderen GIS) dienen.

Betrachten Sie Folgendes als Pseudocode (aber Mathematica führt es aus :-). (Wenn diese Site TeX unterstützt, wie es Mathe, Statistik und TCS tun, könnte ich dies viel besser lesbar machen.) Die Notation beinhaltet:

  • Variablen- und Funktionsnamen unterscheiden zwischen Groß- und Kleinschreibung.
  • [Alpha] ist ein griechischer Kleinbuchstabe. ([Pi] hat den Wert, den Sie denken, dass es haben sollte.)
  • x [[i]] ist das Element i eines Arrays x (indexiert ab 1).
  • f [a, b] wendet die Funktion f auf die Argumente a und b an. Funktionen im richtigen Fall, wie 'Min' und 'Table', sind systemdefiniert. Funktionen mit einem anfänglichen Kleinbuchstaben wie "Winkel" und "Versatz" sind benutzerdefiniert. Kommentare erklären unbekannte Systemfunktionen (wie 'Arg').
  • Tabelle [f [i], {i, 1, n}] erstellt das Array {f [1], f [2], ..., f [n]}.
  • Kreis [o, r, {a, b}] erzeugt einen Kreisbogen, der um o mit dem Radius r von Winkel a bis Winkel b zentriert ist (beide im Bogenmaß gegen den Uhrzeigersinn von genau nach Osten).
  • Ordering [x] gibt ein Array von Indizes der sortierten Elemente von x zurück. x [[Ordering [x]]] ist die sortierte Version von x. Wenn y dieselbe Länge wie x hat, sortiert y [[Ordering [x]]] y parallel zu x.

Der ausführbare Teil des Codes ist erfreulicherweise kurz - weniger als 20 Zeilen -, da über die Hälfte davon entweder deklarativer Overhead oder Kommentare sind.

Zeichnen Sie eine Karte

zist eine Liste von Zielen und yist der Ursprung.

circleMap[z_List, y_] := 
Module[{\[Alpha] = angles[y,z], \[Beta], \[Delta], n},
    (* Sort the destinations by bearing *)
    \[Beta] = Ordering[\[Alpha]];
    x = z[[\[Beta] ]]; (* Destinations, sorted by bearing from y *)
    \[Alpha] = \[Alpha][[\[Beta]]]; (* Bearings, in sorted order *)
    \[Delta] = offset[\[Alpha]];
    n = Length[\[Alpha]];
    Graphics[{(* Draw the lines *)
        Gray, Table[circle[y, x[[i]],2 \[Pi] i / n + \[Delta] - \[Alpha][[i]]], 
             {i, 1, Length[\[Alpha]]}],
        (* Draw the destination points *)
        Red, PointSize[0.02], Table[Point[u], {u, x}]
    }]
]

Erstellen Sie einen Kreisbogen von Punkt xzu Punkt, ybeginnend in einem Winkel \[Beta]relativ zur x -> y-Peilung.

circle[x_, y_, \[Beta]_] /; -\[Pi] < \[Beta] < \[Pi] := 
Module[{v,  \[Rho], r, o, \[Theta], sign},
    If[\[Beta]==0, Return[Line[{x,y}]]];

    (* Obtain the vector from x to y in polar coordinates. *)
    v = y - x; (* Vector from x to y *)
    \[Rho] = Norm[v]; (* Length of v *)
    \[Theta] = Arg[Complex @@ v]; (* Bearing from x to y *)

    (* Compute the radius and center of the circle.*)
    r = \[Rho] / (2 Sin[\[Beta]]); (* Circle radius, up to sign *)
    If[r < 0, sign = \[Pi], sign = 0];
    o = (x+y)/2 + (r/\[Rho]) Cos[\[Beta]]{v[[2]], -v[[1]]}; (* Circle center *)

    (* Create a sector of the circle. *)
    Circle[o, Abs[r], {\[Pi]/2 - \[Beta] + \[Theta] + sign, \[Pi] /2 + \[Beta] + \[Theta] + sign}]
]

Berechnen Sie die Peilungen von einem Ursprung zu einer Liste von Punkten.

angles[origin_, x_] := Arg[Complex@@(#-origin)] & /@ x;

Berechnen Sie den Mittenbereich der Reste eines Lagersatzes.

xist eine Liste der Lager in sortierter Reihenfolge. Idealerweise x [[i]] ~ 2 [Pi] i / n.

offset[x_List] :=
Module[
    {n = Length[x], y},
    (* Compute the residuals. *)
    y = Table[x[[i]] - 2 \[Pi] i / n, {i, 1, n}];
    (* Return their midrange. *)
    (Max[y] + Min[y])/2
]
whuber
quelle
Ich sollte erwähnen, dass diese Lösung annimmt, dass die Ziele mehr oder weniger den Ursprung umgeben. Wenn dies nicht der Fall ist, ist die gesamte Idee (von Lagern mit gleichem Abstand) nicht gut. Es kann jedoch leicht behoben werden, indem einige falsche Ziele in die Winkellücken eingefügt und diese Ziele (und ihre Bögen) später entfernt werden. Dieser Prozess kann automatisiert werden, indem der durchschnittliche Abstand zwischen den Lagern berechnet und zur Identifizierung der großen Lücken usw. Verwendet wird .
whuber
Schöne Grafik. Ich frage mich, ob Fluggesellschaften bei der Erstellung der Streckenkarten, die auf der Rückseite ihres Bordmagazins erscheinen, ein automatisiertes Tool verwenden.
Kirk Kuykendall
1
@Kirk Sie bezahlen wahrscheinlich jemanden, der die Kartografie manuell macht :-). Diese Frage hat mich inspiriert, zu prüfen, ob mit einem einfachen Ansatz einigermaßen gute Grafiken erstellt werden können. Die Antwort sieht vielversprechend aus. Diese Grafiken, nebenbei gesagt, wurden von erzeugt Mathematica 8 mit seinen Kreis und Punkt - Primitiven und ein wenig Vektor - Arithmetik die Kreismittelpunkte zu finden.
whuber
Ich liebe das Ergebnis, das du gezeigt hast und ich bin auf diesem Weg. Ich bin ehrlich, ich halte mich für technisch, aber ich habe mich ein wenig in der Formel verlaufen, die Sie angegeben haben, und wie man das in PostGIS-Code umwandelt, ist daher fast unmöglich. Hat da draußen jemand eine Idee, wie man das Konzept von whuber in praktikablen Code umsetzt? Ich werde versuchen, es zu überprüfen und zu versuchen, aber Hilfe wäre sehr dankbar.
RyanDalton
@whuber- Danke für den aktualisierten Pseudocode. Wir werden sehen müssen, ob wir es tatsächlich in PostGIS implementieren können.
RyanDalton
5

Versuchen Sie es mit ST_CurveToLine

So etwas wie zum Beispiel:

SELECT ST_CurveToLine('CIRCULARSTRING(1 1,5 3,10 1)'::geometry) as the_geom;

Sie können dies visualisieren, indem Sie die Abfrage in das Textfeld kopieren und auf Map1 unter http://www.postgisonline.org/map.php klicken

Nicklas Avén
quelle
Am Ende habe ich dies ausprobiert, um einen Satz von "Zweipunkt" -Linestrings zu krümmen.
Brent Edwards
3

Am Ende habe ich dies ausprobiert, um mithilfe der ST_CurveToLine-Funktion eine Reihe von "Zweipunkt" -Linestrings zu kurven, wie von @Nicklas Avén vorgeschlagen.

Ich habe die folgenden 3 Koordinatensätze an die Funktion ST_OffsetCurve übergeben:

  1. Beginn der ursprünglichen Zeile
  2. Mittelpunkt eines Linienversatzes parallel zur ursprünglichen Linie
  3. Ende der ursprünglichen Zeile

Ich habe die Funktion ST_OffsetCurve verwendet, um den Versatz - 1/10 der Länge der ursprünglichen Linie in meinem Beispiel zu berechnen.

Hier ist die SQL, mit der ich die gekrümmten Linien aus den ursprünglichen geraden Linien generiert habe:

    ST_CurveToLine('CIRCULARSTRING(' || st_x(st_startpoint(the_geom)) || ' ' || st_y(st_startpoint(the_geom)) || ', ' || st_x(st_centroid(ST_OffsetCurve(the_geom, st_length(the_geom)/10, 'quad_segs=4 join=bevel'))) || ' ' || st_y(st_centroid(ST_OffsetCurve(the_geom, st_length(the_geom)/10, 'quad_segs=4 join=bevel'))) || ', ' || st_x(st_endpoint(the_geom)) || ' ' ||  st_y(st_endpoint(the_geom)) || ')') AS the_curved_geom
Brent Edwards
quelle
Wirklich nützlich, aber aus irgendeinem Grund respektiert das Ergebnis mein srid nicht. Irgendeine Idee warum?
DMS02
Könnten Sie etwas mehr Details bereitstellen - srid der Eingabegeometrie, Ausgabe srid fehlt, ist anders, Fehler generiert (welche Anwendung (en) - QGIS, PostgreSQL).
Brent Edwards
Die Tabelle, in die ich die resultierenden gekrümmten Linien einfügen möchte, hat eine enforce_srid_geom-Einschränkung. Wenn ich die Abfrage ausführe, erhalte ich die Fehlermeldung, dass diese Abfrage diese Einschränkung verletzt. Mit einer Tabelle ohne diese Einschränkung funktioniert es, aber wenn sie zu QGIS hinzugefügt wird, wird sie mit srid 0 aufgelistet. Meine Abfrage: INSERT INTO test (the_curved_geom) SELECT [hier Ihr SQL] FROM lines
DMS02 28.10.16
Führen Sie die Funktionen postgis.net/docs/ST_GeometryType.html und postgis.net/docs/ST_SRID.html für die Geometriespalte (the_curved_geom) aus und überprüfen Sie, ob Konflikte mit Ihrer Testtabelle und enforce_srid_geom vorliegen. In diesem Fall können Sie die Geometrie / das Raster nach Bedarf transformieren oder Ihre Testtabelle / Einschränkung ändern.
Brent Edwards