"Mapas de ruta" punto a punto curvos

Recientemente he estado buscando en las páginas web de las aerolíneas que muestran sus rutas que parten de una determinada ciudad a todas las demás ciudades a las que dan servicio. Me gustaría poder crear rutas curvas similares entre puntos. ¿Alguien ha creado scripts o funciones que generarán los arcos curvos como los que se muestran en este ejemplo ?

En PostGIS, ¿existe una implementación de ST_MakeLine que le permita especificar la cantidad de curva que se utilizará al conectar 2 puntos?

Aunque actualmente estoy usando PostGIS y QGIS, agradecería escuchar sobre otras opciones de software que podrían crear la misma apariencia.

Crear grandes círculos podría darte el efecto deseado.

Tal vez algo como lo discutido en http://lists.osgeo.org/pipermail/postgis-users/2008-February/018620.html

Actualizar:

He seguido esta idea en "Visualizar conexiones globales" . Es una solución puramente basada en PostGIS que utiliza la reproyección para crear arcos.

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

(La definición de CRS para 953027 se puede encontrar aquí: http://spatialreference.org/ref/esri/53027/ )

El problema es calcular cuánto doblar los arcos para mejorar su resolución visual.

Aquí hay una solución (entre las muchas posibles). Consideremos todos los arcos que emanan de un origen común. Los arcos se llenan más aquí. Para separarlos de la mejor manera, organicemos de manera que se extiendan en ángulos igualmente espaciados . Es un problema si dibujamos segmentos de línea recta desde el origen hasta los destinos, porque generalmente habrá grupos de destinos en varias direcciones. Usemos nuestra libertad para doblar los arcos para espaciar los ángulos de salida lo más uniformemente posible.

Para simplificar, usemos arcos circulares en el mapa. Una medida natural de la "curva" en un arco desde el punto y al punto x es la diferencia entre su rumbo en y y el rumbo directamente de y a x . Tal arco es un sector de un círculo en el que se encuentran y y x ; La geometría elemental muestra que el ángulo de flexión es igual a la mitad del ángulo incluido en el arco.

Para describir un algoritmo necesitamos un poco más de notación. Sea y el punto de origen (como se proyecta en el mapa) y sea x_1 , x_2 , ..., x_n los puntos de destino. Defina a_i como el rumbo de y a x_i , i = 1, 2, ..., n .

Como paso preliminar, suponga que los rodamientos (todos entre 0 y 360 grados) están en orden ascendente: esto requiere que calculemos los rodamientos y luego los ordenemos; ambas son tareas sencillas.

Idealmente, nos gustaría que los rumbos de los arcos sean iguales a 360 / n , 2 * 360 / n , etc., en relación con algunos rumbos iniciales. Por lo tanto, las diferencias entre los rodamientos deseados y los rodamientos reales son iguales a i * 360 / n - a_i más el rodamiento inicial, a0 . La diferencia más grande es el máximo de estas n diferencias y la diferencia más pequeña es su mínimo. Configuremos a0 para que esté a medio camino entre el máximo y el mínimo; Este es un buen candidato para el rodamiento inicial porque minimiza la cantidad máxima de flexión que se producirá . En consecuencia, definir

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

esta es la flexión para usar .

Es una cuestión de geometría elemental dibujar un arco circular de y a x que tenga un ángulo de 2 b_i, así que omitiré los detalles e iré directamente a un ejemplo. Aquí hay ilustraciones de las soluciones para 64, 16 y 4 puntos aleatorios ubicados dentro de un mapa rectangular

Como se puede ver, las soluciones parecen tener más agradable como el número de puntos de destino aumenta. La solución para n = 4 muestra claramente cómo los rodamientos están igualmente espaciados, ya que en este caso la separación es igual a 360/4 = 90 grados y obviamente esa separación se logra exactamente.

Esta solución no es perfecta: probablemente pueda identificar varios arcos que podrían modificarse manualmente para mejorar el gráfico. Pero no hará un trabajo terrible y parece ser un muy buen comienzo.

El algoritmo también tiene el mérito de ser simple: la parte más complicada consiste en ordenar los destinos de acuerdo con sus orientaciones.

Codificación

No conozco PostGIS, pero quizás el código que usé para dibujar los ejemplos puede servir como guía para implementar este algoritmo en PostGIS (o cualquier otro SIG).

Considere lo siguiente como pseudocódigo (pero Mathematica lo ejecutará :-). (Si este sitio admitiera TeX, como lo hacen las matemáticas, estadísticas y TCS, podría hacer que esto sea mucho más legible). La notación incluye:

• Los nombres de variables y funciones distinguen entre mayúsculas y minúsculas.
• [Alfa] es un carácter griego en minúsculas. ([Pi] tiene el valor que crees que debería tener).
• x [[i]] es el elemento i de una matriz x (indexado a partir de 1).
• f [a, b] aplica la función f a los argumentos a y b. Las funciones en el caso apropiado, como 'Min' y 'Tabla', están definidas por el sistema; Las funciones con una letra minúscula inicial, como 'ángulos' y 'desplazamiento', están definidas por el usuario. Los comentarios explican cualquier función oscura del sistema (como 'Arg').
• La tabla [f [i], {i, 1, n}] crea la matriz {f [1], f [2], ..., f [n]}.
• El círculo [o, r, {a, b}] crea un arco del círculo centrado en o de radio r desde el ángulo a hasta el ángulo b (ambos en radianes en sentido antihorario desde el este).
• Ordenar [x] devuelve una matriz de índices de los elementos ordenados de x. x [[Ordenar [x]]] es la versión ordenada de x. Cuando y tiene la misma longitud que x, y [[Ordenar [x]]] ordena y en paralelo con x.

La parte ejecutable del código es afortunadamente corta, menos de 20 líneas, porque más de la mitad son gastos generales declarativos o comentarios.

Dibujar un mapa

zes una lista de destinos y yes el origen.

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

Cree un arco circular de punto xa punto ycomenzando en un ángulo \[Beta]relativo al rumbo 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}]
]

Calcule los rumbos desde un origen hasta una lista de puntos.

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

Calcule el rango medio de los residuos de un conjunto de rodamientos.

xes una lista de rodamientos en orden ordenado. Idealmente, 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
]

Prueba ST_CurveToLine

Algo como por ejemplo:

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

Puede visualizar esto copiando la consulta en el cuadro de texto y presionando Map1 en http://www.postgisonline.org/map.php

Creo que solo querría rodar su propia polilínea con algunas matemáticas vectoriales, http://en.wikipedia.org/wiki/B%C3%A9zier_curve , o si su gis tiene una interfaz ICurve .

Terminé probando esto para curvar un conjunto de cadenas de líneas de "dos puntos" usando la función ST_CurveToLine como lo sugirió @Nicklas Avén.

Pasé los siguientes 3 conjuntos de coordenadas a la función ST_OffsetCurve:

1. Inicio de la linea original
2. Punto medio de una línea desplazada paralela a la línea original
3. Fin de la linea original

Usé la función ST_OffsetCurve para calcular el desplazamiento: 1/10 de la longitud de la línea original en mi ejemplo.

Aquí está el SQL que utilicé para generar las líneas curvas a partir de las líneas rectas originales:

    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