«Cartes routières» courbes point à point

39

J'ai récemment consulté les pages Web des compagnies aériennes qui affichent leurs itinéraires au départ d'une ville donnée vers toutes les autres villes desservies. J'aimerais pouvoir créer des itinéraires courbes similaires entre les points. Quelqu'un a-t-il créé des scripts ou des fonctions qui généreront les arcs courbes comme ceux présentés dans cet exemple ?

Trajectoires de vol

Dans PostGIS, existe-t-il une implémentation de ST_MakeLine qui vous permettrait de spécifier la quantité de courbe à utiliser lors de la connexion de 2 points?

Bien que j'utilise actuellement PostGIS et QGIS, j'aimerais connaître d'autres options logicielles susceptibles de créer la même apparence.

RyanDalton
la source
Quelqu'un sait-il de belles implémentations? Exemples ou autre chose?
Mark Boulder

Réponses:

26

Créer de grands cercles pourrait vous donner l’effet désiré.

Peut-être que quelque chose comme discuté sur http://lists.osgeo.org/pipermail/postgis-users/2008-février/018620.html

Mise à jour:

J'ai suivi cette idée dans "Visualizing Global Connections" . C'est une solution purement PostGIS qui utilise la reprojection pour créer des arcs.

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

(La définition de CRS pour 953027 peut être trouvée ici: http://spatialreference.org/ref/esri/53027/ )

entrez la description de l'image ici

sous-bois
la source
4
J'aime l'idée, bien qu'avec les grands cercles, le problème que vous rencontrez est que, sur des distances plus courtes, vous finirez toujours par avoir une ligne généralement droite. J'aimerais pouvoir contrôler la quantité d'arc que je mets dans la ligne (c'est-à-dire- longueur d'arc = distance * 2).
RyanDalton
1
Voici un bon exemple du problème lié à l'
RyanDalton le
1
Après quelques recherches supplémentaires, j'ai trouvé ce post qui pourrait être utile pour aider cette méthode. mail-archive.com/[email protected]/…
RyanDalton
Pour une utilisation future par les lecteurs, j'ai pensé que je voudrais simplement créer un lien vers le récent billet de blog de @ underdark qui traite de ce sujet. underdark.wordpress.com/2011/08/20/…
RyanDalton le
C'est génial!! Utilisé dans mon projet pour tracer des lignes entre les enregistrements des utilisateurs et les emplacements des sites, repris de Forsquare
Lorenzo Barbagli
24

Le problème consiste à déterminer le degré de pliage des arcs pour améliorer leur résolution visuelle.

Voici une solution (parmi les nombreuses possibles). Considérons tous les arcs émanant d'une origine commune. Les arcs sont les plus encombrés ici. Pour séparer les meilleurs, organisons-les de manière à ce qu'ils se répartissent dans des angles égaux . C'est un problème si nous traçons des segments de ligne droite de l'origine aux destinations, car il y aura généralement des groupes de destinations dans différentes directions. Utilisons notre liberté pour plier les arcs afin d’espacer les angles de départ le plus uniformément possible.

Pour plus de simplicité, utilisons des arcs de cercle sur la carte. Une mesure naturelle de la "courbure" dans un arc du point y au point x est la différence entre son relèvement en y et le relèvement directement de y à x . Un tel arc est un secteur de cercle sur lequel y et x sont tous deux; la géométrie élémentaire montre que l'angle de pliage est égal à la moitié de l'angle inclus dans l'arc.

Pour décrire un algorithme, nous avons besoin d'un peu plus de notation. Soit y le point d'origine (tel que projeté sur la carte) et x_1 , x_2 , ..., x_n les points de destination. Définissez a_i comme étant le relèvement de y à x_i , i = 1, 2, ..., n .

Dans une étape préliminaire, supposons que les relèvements (tous compris entre 0 et 360 degrés) soient dans l’ordre croissant: cela nous oblige à calculer les relèvements puis à les trier; les deux sont des tâches simples.

Idéalement, nous voudrions que les relèvements des arcs soient égaux à 360 / n , 2 * 360 / n , etc., par rapport à un relèvement de départ. Les différences entre les roulements désirés et les roulements réels sont donc égales à i * 360 / n - a_i plus le roulement de départ, a0 . La plus grande différence est le maximum de ces n différences et la plus petite différence est leur minimum. Fixons a0 à mi-chemin entre le maximum et le minimum; C'est un bon candidat pour le roulement de départ car il minimise la quantité maximale de flexion qui va se produire . Par conséquent, définir

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

c'est la flexion à utiliser .

Il s’agit d’une géométrie élémentaire de tracer un arc de cercle de y à x qui sous-tend un angle de 2 b_i. Je vais donc ignorer les détails et passer directement à un exemple. Voici des illustrations des solutions pour 64, 16 et 4 points aléatoires placés dans une carte rectangulaire.

texte alternatif

texte alternatif

texte alternatif

Comme vous pouvez le voir, les solutions semblent obtenir plus agréable que le nombre de points de destination augmente. La solution pour n = 4 montre clairement comment les roulements sont équidistants, car dans ce cas, l’espacement est égal à 360/4 = 90 degrés et, évidemment, cet espacement est exactement réalisé.

Cette solution n'est pas parfaite: vous pouvez probablement identifier plusieurs arcs pouvant être modifiés manuellement pour améliorer le graphique. Mais cela ne fera pas un travail terrible et semble être un très bon début.

L’algorithme a également le mérite d’être simple: la partie la plus compliquée consiste à trier les destinations en fonction de leurs relèvements.


Codage

Je ne connais pas PostGIS, mais le code que j'ai utilisé pour dessiner les exemples peut servir de guide pour l'implémentation de cet algorithme dans PostGIS (ou tout autre SIG).

Considérez ce qui suit comme pseudocode (mais Mathematica l’exécutera :-). (Si ce site supportait TeX, comme le font les mathématiques, les statistiques et le TCS, je pourrais le rendre beaucoup plus lisible.) La notation comprend:

  • Les noms de variable et de fonction sont sensibles à la casse.
  • [Alpha] est un caractère grec minuscule. ([Pi] a la valeur que vous pensez qu'il devrait avoir.)
  • x [[i]] est l'élément i d'un tableau x (indexé à partir de 1).
  • f [a, b] applique la fonction f aux arguments a et b. Les fonctions dans les cas appropriés, comme 'Min' et 'Table', sont définies par le système; les fonctions avec une lettre minuscule initiale, comme "angles" et "offset", sont définies par l'utilisateur. Les commentaires expliquent des fonctions système obscures (comme 'Arg').
  • Le tableau [f [i], {i, 1, n}] crée le tableau {f [1], f [2], ..., f [n]}.
  • Le cercle [o, r, {a, b}] crée un arc de cercle dont le centre est situé à 0 de rayon r de l'angle a à l'angle b (les deux en radians dans le sens anti-horaire à partir de l'est).
  • Ordering [x] renvoie un tableau d'index des éléments triés de x. x [[Ordering [x]]] est la version triée de x. Lorsque y a la même longueur que x, y [[Ordering [x]]] trie y en parallèle avec x.

La partie exécutable du code est heureusement courte (moins de 20 lignes), car plus de la moitié est constituée de frais généraux déclaratifs ou de commentaires.

Dessiner une carte

zest une liste de destinations et en yest l'origine.

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}]
    }]
]

Créez un arc de cercle de point xà point en ycommençant par un angle par \[Beta]rapport au relèvement x -> y.

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}]
]

Calculer les relèvements d'une origine à une liste de points.

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

Calcule le milieu de gamme des résidus d'un ensemble de roulements.

xest une liste de roulements dans l'ordre de tri. Idéalement, 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
la source
Je devrais mentionner que cette solution suppose que les destinations entourent plus ou moins l'origine. Lorsque ce n'est pas le cas, l'idée (des roulements équidistants) n'est pas bonne. Mais il peut être facilement réparé en introduisant de fausses destinations dans les espaces angulaires et en supprimant ensuite ces destinations (et leurs arcs). Ce processus peut être automatisé par le calcul de la distance moyenne entre les paliers et à l' aide que l'identification des écarts importants, etc .
whuber
De beaux graphiques. Je me demande si les compagnies aériennes utilisent un outil automatisé pour établir les cartes de route figurant au dos de leur magazine de bord.
Kirk Kuykendall
1
@Kirk Ils paient probablement quelqu'un pour faire la cartographie manuellement :-). Cette question m'a inspiré pour voir si une approche simple pouvait créer des graphiques raisonnablement bons. La réponse semble prometteuse. Ces graphiques, d'ailleurs, ont été produits par Mathematica 8 en utilisant ses primitives Circle et Point et un peu d'arithmétique vectorielle pour trouver les centres de cercle.
whuber
J'aime le résultat que vous avez montré et moi c'est la voie à suivre. Je serai honnête cependant, je me considère technique, mais je me suis un peu égaré dans la formule que vous avez donnée, et comment transformer cela en code PostGIS devient donc presque impossible. Quelqu'un at-il des idées sur la façon de traduire le concept de whuber en code exploitable? Je vais essayer de passer en revue et de tenter le coup, mais une aide serait grandement appréciée.
RyanDalton
@ whuber- Merci pour le pseudocode mis à jour. Nous devrons voir si nous pouvons réellement l'implémenter dans PostGIS.
RyanDalton
5

Essayez ST_CurveToLine

Quelque chose comme par exemple:

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

Vous pouvez visualiser cela en copiant la requête dans la zone de texte et en appuyant sur Map1 à l' adresse http://www.postgisonline.org/map.php.

Nicklas Avén
la source
J'ai fini par essayer de courber un ensemble de cordages "à deux points".
Brent Edwards
3

J'ai fini par essayer de courber un ensemble de lignes "deux points" à l'aide de la fonction ST_CurveToLine comme suggéré par @Nicklas Avén.

J'ai passé les 3 jeux de coordonnées suivants à la fonction ST_OffsetCurve:

  1. Début de la ligne d'origine
  2. Milieu d'une ligne décalé parallèlement à la ligne d'origine
  3. Fin de la ligne d'origine

J'ai utilisé la fonction ST_OffsetCurve pour calculer le décalage - 1 / 10ème de la longueur de la ligne d'origine dans mon exemple.

Voici le code SQL que j'ai utilisé pour générer les lignes courbes à partir des lignes droites d'origine:

    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
la source
Vraiment utile, mais pour une raison quelconque, le résultat ne respecte pas mon secret. Une idée pourquoi?
DMS02
Pourriez-vous fournir plus de détails - grille de la géométrie en entrée, grille en sortie manquante, différente, erreurs générées (quelle (s) application (s) - QGIS, PostgreSQL).
Brent Edwards
La table dans laquelle je veux insérer les lignes courbes résultantes a une contrainte enforce_srid_geom. Lorsque j'exécute la requête, j'obtiens une erreur indiquant que cette requête enfreint cette contrainte. Avec une table sans cette contrainte, cela fonctionne, mais lorsque vous l'ajoutez à QGIS, il est répertorié avec le srid 0. Ma requête: INSERT INTO test (the_curved_geom) SELECT [ici votre SQL] FROM lignes
DMS02
Essayez d’exécuter les fonctions postgis.net/docs/ST_GeometryType.html et postgis.net/docs/ST_SRID.html sur la colonne de géométrie (the_curved_geom) et vérifiez s’il ya des conflits avec votre table de test et enforce_srid_geom. Si tel est le cas, vous pouvez transformer la géométrie / grille au besoin ou modifier votre table / contrainte de test.
Brent Edwards