"Mapas de rota" ponto a ponto curvados

Recentemente, estive pesquisando páginas da web de companhias aéreas que exibem suas rotas que partem de uma determinada cidade para todas as outras cidades que atendem. Eu gostaria de poder criar rotas curvas semelhantes entre pontos. Alguém criou scripts ou funções que irão gerar arcos curvos como os exibidos neste exemplo ?

No PostGIS, existe uma implementação do ST_MakeLine que permita especificar a quantidade de curva a ser usada ao conectar 2 pontos?

Enquanto atualmente estou usando o PostGIS e o QGIS, gostaria de saber sobre outras opções de software que podem criar a mesma aparência.

Criar grandes círculos pode dar o efeito desejado.

Talvez algo como discutido em http://lists.osgeo.org/pipermail/postgis-users/2008-February/018620.html

Atualizar:

Eu segui essa ideia em "Visualizando conexões globais" . É uma solução puramente baseada em PostGIS usando reprojeção para criar arcos.

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

(A definição de CRS para 953027 pode ser encontrada aqui: http://spatialreference.org/ref/esri/53027/ )

O problema é descobrir quanto dobrar os arcos para melhorar sua resolução visual.

Aqui está uma solução (entre as muitas possíveis). Vamos considerar todos os arcos que emanam de uma origem comum. Os arcos ficam mais lotados aqui. Para separá-los da melhor forma, vamos organizá-los para que se espalhem em ângulos igualmente espaçados . É um problema se desenharmos segmentos de linha reta da origem aos destinos, porque normalmente haverá grupos de destinos em várias direções. Vamos usar nossa liberdade para dobrar os arcos, a fim de espaçar os ângulos de partida o mais uniformemente possível.

Para simplificar, vamos usar arcos circulares no mapa. Uma medida natural da "dobra" em um arco do ponto y ao ponto x é a diferença entre o seu rolamento em y e o rolamento diretamente de y a x . Tal arco é um setor de um círculo no qual y e x se encontram; geometria elementar mostra que o ângulo de flexão é igual à metade do ângulo incluído no arco.

Para descrever um algoritmo, precisamos de um pouco mais de notação. Seja y o ponto de origem (conforme projetado no mapa) e seja x_1 , x_2 , ..., x_n os pontos de destino. Defina a_i como o rolamento de y a x_i , i = 1, 2, ..., n .

Como passo preliminar, suponha que os rolamentos (todos entre 0 e 360 ​​graus) estejam em ordem crescente: isso exige que calculemos os rolamentos e depois os classifiquemos; ambos são tarefas diretas.

Idealmente, gostaríamos que os rolamentos dos arcos fossem iguais a 360 / n , 2 * 360 / n etc., em relação a algum rolamento inicial. As diferenças entre os rolamentos desejados e os rolamentos reais são, portanto, iguais a i * 360 / n - a_i mais o rolamento de partida, a0 . A maior diferença é o máximo dessas n diferenças e a menor diferença é o mínimo. Vamos definir a0 para estar a meio caminho entre o máximo e o mínimo; este é um bom candidato para o rolamento inicial, pois minimiza a quantidade máxima de flexão que ocorrerá . Conseqüentemente, defina

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

essa é a curvatura a ser usada .

É uma questão de geometria elementar desenhar um arco circular de y a x que subtenda um ângulo de 2 b_i, por isso vou pular os detalhes e seguir diretamente para um exemplo. Aqui estão ilustrações das soluções para 64, 16 e 4 pontos aleatórios colocados em um mapa retangular

Como você pode ver, as soluções parecem ficar mais agradável como o número de destino pontos aumenta. A solução para n = 4 mostra claramente como os rolamentos estão igualmente espaçados, pois nesse caso o espaçamento é igual a 360/4 = 90 graus e, obviamente, esse espaçamento é exatamente alcançado.

Esta solução não é perfeita: você provavelmente pode identificar vários arcos que poderiam ser ajustados manualmente para melhorar o gráfico. Mas não fará um trabalho terrível e parece ser um bom começo.

O algoritmo também tem o mérito de ser simples: a parte mais complicada consiste em classificar os destinos de acordo com seus rumos.

Codificação

Não conheço o PostGIS, mas talvez o código que eu usei para desenhar os exemplos possa servir como um guia para implementar esse algoritmo no PostGIS (ou em qualquer outro GIS).

Considere o seguinte como pseudocódigo (mas o Mathematica o executará :-). (Se este site oferecer suporte ao TeX, como os de matemática, estatísticas e TCS, eu poderia tornar isso muito mais legível.) A notação inclui:

• Os nomes de variáveis ​​e funções diferenciam maiúsculas de minúsculas.
• [Alpha] é um caractere grego em letras minúsculas. ([Pi] tem o valor que você acha que deveria ter).
• x [[i]] é o elemento i de uma matriz x (indexada a partir de 1).
• f [a, b] aplica a função f aos argumentos a e b. Funções no caso apropriado, como 'Min' e 'Table', são definidas pelo sistema; funções com uma letra minúscula inicial, como 'ângulos' e 'deslocamento', são definidas pelo usuário. Os comentários explicam quaisquer funções obscuras do sistema (como 'Arg').
• A tabela [f [i], {i, 1, n}] cria a matriz {f [1], f [2], ..., f [n]}.
• O círculo [o, r, {a, b}] cria um arco do círculo centrado no o do raio r do ângulo a ao ângulo b (ambos em radianos no sentido anti-horário do leste a leste).
• A ordenação [x] retorna uma matriz de índices dos elementos classificados de x. x [[Ordenação [x]]] é a versão classificada de x. Quando y tem o mesmo comprimento que x, y [[Ordenando [x]]] classifica y em paralelo com x.

A parte executável do código é misericordiosamente curta - menos de 20 linhas - porque mais da metade é de sobrecarga declarativa ou de comentários.

Desenhe um mapa

zé uma lista de destinos e yé a origem.

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

Crie um arco circular de ponto xa ponto ycomeçando no ângulo \[Beta]relativo ao rolamento 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 os rolamentos de uma origem para uma lista de pontos.

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

Calcule a faixa média dos resíduos de um conjunto de rolamentos.

xé uma lista de rolamentos em ordem classificada. 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
]

Experimente ST_CurveToLine

Algo como, por exemplo:

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

Você pode visualizar isso copiando a consulta na caixa de texto e pressionando Map1 em http://www.postgisonline.org/map.php

Eu acho que você gostaria de rolar sua própria polilinha com algumas matemáticas vetoriais, http://en.wikipedia.org/wiki/B%C3%A9zier_curve , ou se seus gis tiverem uma interface ICurve .

Acabei tentando fazer uma curva de um conjunto de cadeias de linhas de "dois pontos" usando a função ST_CurveToLine, como sugerido por @Nicklas Avén.

Passei os três conjuntos de coordenadas a seguir para a função ST_OffsetCurve:

1. Início da linha original
2. Ponto médio de um deslocamento de linha paralelo à linha original
3. Fim da linha original

Eu usei a função ST_OffsetCurve para calcular o deslocamento - 1/10 do comprimento da linha original no meu exemplo.

Aqui está o SQL que eu usei para gerar as linhas curvas a partir das linhas retas originais:

    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