«Cartes routières» courbes point à point

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 ?

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.

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

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.

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
]

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.

Je pense que vous voudriez simplement rouler votre propre polyligne avec des mathématiques vectorielles, http://en.wikipedia.org/wiki/B%C3%A9zier_curve , ou si votre gis a une interface ICurve .

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