"Peta rute" titik-ke-titik yang melengkung

Saya baru-baru ini melihat halaman web maskapai penerbangan yang menampilkan rute mereka berangkat dari kota tertentu ke semua kota lain yang mereka layani. Saya ingin dapat membuat rute melengkung serupa di antara titik. Adakah yang membuat skrip atau fungsi yang akan menghasilkan lengkungan lengkung seperti yang ditampilkan dalam contoh ini ?

Di PostGIS, apakah ada implementasi ST_MakeLine yang memungkinkan Anda menentukan jumlah kurva yang digunakan saat menghubungkan 2 titik?

Sementara saya saat ini menggunakan PostGIS dan QGIS, saya akan senang mendengar tentang opsi perangkat lunak lain yang mungkin dapat membuat tampilan yang sama.

Membuat lingkaran yang hebat dapat memberi Anda efek yang diinginkan.

Mungkin sesuatu seperti dibahas di http://lists.osgeo.org/pipermail/postgis-users/2008-February/018620.html

Memperbarui:

Saya telah menindaklanjuti ide ini dalam "Visualisasi Koneksi Global" . Ini murni solusi berbasis PostGIS menggunakan proyeksi ulang untuk membuat busur.

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

(Definisi CRS untuk 953027 dapat ditemukan di sini: http://spatialreference.org/ref/esri/53027/ )

Masalahnya adalah untuk mencari tahu berapa banyak untuk menekuk busur untuk meningkatkan resolusi visual mereka.

Inilah satu solusi (di antara banyak kemungkinan). Mari kita pertimbangkan semua busur yang berasal dari asal yang sama. Busur menjadi paling ramai di sini. Untuk memisahkan mereka yang terbaik, mari kita atur sehingga mereka menyebar dalam sudut yang sama-sama berjarak . Ini masalah jika kita menggambar segmen garis lurus dari asal ke tujuan, karena biasanya akan ada kelompok tujuan di berbagai arah. Mari kita gunakan kebebasan kita untuk membengkokkan busur agar ruang sudut yang berangkat serata mungkin.

Untuk mempermudah, mari gunakan busur lingkaran di peta. Ukuran alami dari "tikungan" dalam busur dari titik y ke titik x adalah perbedaan antara bantalannya di y dan bantalan langsung dari y ke x . Busur seperti itu adalah sektor lingkaran di mana y dan x keduanya terletak; geometri dasar menunjukkan bahwa sudut lentur sama dengan satu-setengah dari sudut yang disertakan dalam busur.

Untuk menggambarkan suatu algoritma, kita perlu lebih banyak notasi. Biarkan y menjadi titik asal (seperti yang diproyeksikan pada peta) dan biarkan x_1 , x_2 , ..., x_n menjadi titik tujuan. Tentukan a_i sebagai kaitan dari y ke x_i , i = 1, 2, ..., n .

Sebagai langkah awal, anggap bantalan (semua antara 0 dan 360 derajat) berada dalam urutan naik: ini mengharuskan kita untuk menghitung bantalan dan kemudian mengurutkannya; keduanya adalah tugas langsung.

Idealnya, kami ingin bantalan busur sama dengan 360 / n , 2 * 360 / n , dll, relatif terhadap beberapa bantalan awal. Perbedaan antara bantalan yang diinginkan dan bantalan aktual oleh karena itu sama dengan i * 360 / n - a_i ditambah bantalan awal, a0 . Perbedaan terbesar adalah maksimum dari n perbedaan ini dan perbedaan terkecil adalah minimumnya. Mari kita mengatur a0 menjadi setengah antara max dan min; ini adalah kandidat yang baik untuk bantalan awal karena meminimalkan jumlah lentur maksimum yang akan terjadi . Akibatnya, jelaskan

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

ini adalah tekukan untuk digunakan .

Ini masalah geometri dasar untuk menggambar busur lingkaran dari y ke x yang menyudutkan sudut 2 b_i, jadi saya akan melewatkan detail dan langsung ke contoh. Berikut adalah ilustrasi solusi untuk 64, 16, dan 4 titik acak yang ditempatkan dalam peta persegi panjang

Seperti yang Anda lihat, solusinya tampaknya semakin baik karena jumlah poin tujuan meningkat. Solusi untuk n = 4 menunjukkan dengan jelas bagaimana bantalan diberi jarak yang sama, karena dalam hal ini jaraknya sama dengan 360/4 = 90 derajat dan jelas bahwa jarak tersebut dicapai secara tepat.

Solusi ini tidak sempurna: Anda mungkin dapat mengidentifikasi beberapa busur yang dapat di-tweak secara manual untuk meningkatkan grafik. Tetapi itu tidak akan melakukan pekerjaan yang buruk dan tampaknya merupakan awal yang sangat baik.

Algoritma ini juga memiliki kelebihan yaitu sederhana: bagian paling rumit terdiri dari pengurutan tujuan sesuai dengan bantalan mereka.

Coding

Saya tidak tahu PostGIS, tetapi mungkin kode yang saya gunakan untuk menggambar contoh dapat berfungsi sebagai panduan untuk mengimplementasikan algoritma ini di PostGIS (atau GIS lainnya).

Pertimbangkan yang berikut ini sebagai pseudocode (tetapi Mathematica akan menjalankannya :-). (Jika situs ini didukung TeX, sebagai matematika, statistik, dan orang-orang TCS lakukan, saya bisa membuat ini banyak lebih mudah dibaca.) Notasi termasuk:

• Nama variabel dan fungsi peka huruf besar-kecil.
• [Alpha] adalah karakter Yunani huruf kecil. ([Pi] memiliki nilai yang menurut Anda seharusnya.)
• x [[i]] adalah elemen i dari array x (diindeks mulai dari 1).
• f [a, b] menerapkan fungsi f untuk argumen a dan b. Fungsi dalam kasus yang tepat, seperti 'Min' dan 'Tabel', ditentukan oleh sistem; fungsi dengan huruf kecil awal, seperti 'sudut' dan 'offset', ditentukan pengguna. Komentar menjelaskan fungsi sistem yang tidak jelas (seperti 'Arg').
• Tabel [f [i], {i, 1, n}] menciptakan array {f [1], f [2], ..., f [n]}.
• Lingkaran [o, r, {a, b}] menciptakan busur lingkaran yang berpusat pada jari-jari r dari sudut a ke sudut b (keduanya dalam radian berlawanan arah jarum jam dari arah timur).
• Memesan [x] mengembalikan array indeks elemen yang diurutkan dari x. x [[Memesan [x]]] adalah versi x yang diurutkan. Ketika y memiliki panjang yang sama dengan x, y [[Memesan [x]]] mengurutkan y secara paralel dengan x.

Bagian yang dapat dieksekusi dari kode ini untungnya pendek - kurang dari 20 baris - karena lebih dari setengahnya adalah overhead atau komentar deklaratif.

Gambarkan peta

zadalah daftar tujuan dan yasal.

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

Buat busur lingkaran dari titik xke titik ymulai dari sudut \[Beta]relatif terhadap bantalan 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}]
]

Hitung bantalan dari asal ke daftar poin.

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

Hitung midrange residu dari satu set bantalan.

xadalah daftar bantalan dalam urutan diurutkan. Idealnya, 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
]

Coba ST_CurveToLine

Sesuatu seperti misalnya:

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

Anda dapat memvisualisasikan ini dengan menjawab kueri ke dalam kotak teks dan menekan Map1 di http://www.postgisonline.org/map.php

Saya pikir Anda hanya ingin menggulung polyline Anda sendiri dengan beberapa vektor matematika, http://en.wikipedia.org/wiki/B%C3%A9zier_curve , atau jika gis Anda memiliki antarmuka ICurve .

Saya akhirnya mencoba ini untuk melengkung satu set linestrings "dua titik" menggunakan fungsi ST_CurveToLine seperti yang disarankan oleh @Nicklas Avén.

Saya melewati 3 set koordinat berikut ke fungsi ST_OffsetCurve:

1. Mulai dari garis aslinya
2. Titik tengah dari garis diimbangi sejajar dengan garis aslinya
3. Akhir dari garis aslinya

Saya menggunakan fungsi ST_OffsetCurve untuk menghitung offset - 1/10 dari panjang baris asli dalam contoh saya.

Berikut ini adalah SQL yang saya gunakan untuk menghasilkan garis lengkung dari garis lurus asli:

    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