Jalur terpendek menggunakan poin OSM interpolasi

8

Saya memiliki satu set titik GPS yang telah saya akses ke jaringan OSM. Pada tangkapan layar di bawah ini, titik-titik GPS berwarna merah, titik-titik yang terputus berwarna hijau. masukkan deskripsi gambar di sini

Saya ingin menghitung jalur terpendek yang mencakup semua titik jalan hijau ini. Solusi saya adalah menghitung jalur terpendek antara setiap pasangan poin dan akhirnya menyatukan hasilnya.

Masalah saya adalah bahwa dijkstra_sp tidak akan menerima poin arbitrer pada jaringan OSM. Poin saya yang terpotong tidak harus dalam tabel cara karena mereka dihitung menggunakan logika berikut.

  1. Temukan cara terdekat ke titik GPS yang diberikan.
  2. Dengan menggunakan interpolasi, temukan titik terdekat dalam perjalanan ke titik GPS.

Titik patah tidak ada dalam tabel cara karena mereka diperoleh dengan interpolasi.

Jadi pertanyaan saya adalah: Bagaimana cara menghitung jalur terpendek antara dua titik di jaringan OSM yang belum tentu dalam tabel cara?

interpolation pgrouting Fezter
sumber
Kedengarannya bagi saya Anda sedang mencoba memecahkan Masalah Traveling Salesman . Dalam hal ini, cara paling efisien untuk pergi akan menggunakan algoritma TSP ...
ntg

Jawaban:

3

Kami memecahkan masalah yang sama dengan tepi dan simpul sementara. Kami menjentikkan coords GPS kami ke tepi e dari v1 ke v2 dan mendapat offset antara 0 dan 1:

segOffset := line_locate_point(geom(e), Point(coords);

Dengan ini kami membuat Point baru () dan dari sini v_tmp vertex baru:

line_interpolate_point(geom(e), segOffset);

Kami kemudian membagi tepi e1 kami menjadi dua sisi baru e_tmp1 dari v1 ke v_tmp dan e_tmp2 dari v_tmp ke v2. (Anda bisa membaginya menjadi 4 temp endges ...)

Dengan target kami, kami melakukan hal yang sama. Daripada kami mulai membuka dengan simpul baru kami v_tmp_source, v_tmp_dest dan hanya itu.

Axel Zingsem
sumber
2

Saya cocok dengan node terdekat, menggunakan pgrouting untuk menemukan rute antara node ini. Saya mengejar total jarak, jadi saya kemudian menambahkan dua jarak titik-simpul.

Saya memiliki batas atas pada seberapa dekat sebuah node harus dapat diterima.

Matematika akan lebih rumit / lebih lambat, tetapi Anda bisa melakukan hal yang sama untuk edge jika Anda menggunakan algoritma pgrouting yang bekerja dalam hal edge daripada node.

menang
sumber
(Maaf, entah bagaimana saya tidak bisa berkomentar untuk "menang", jadi saya harus melakukannya dengan jawaban lain)> Matematika akan lebih rumit / lebih lambat, tetapi Anda bisa melakukan hal yang sama untuk edge jika Anda menggunakan algoritma pgrouting yang bekerja dalam hal tepi daripada node. Algoritma Shooting Star lebih unggul daripada node.
dkastl
Baik simpul terdekat maupun prosedur berbasis tepi tidak akan berfungsi, lihat contoh di bawah ini. dl.dropbox.com/u/11502389/Screenshot2.png Garis biru adalah cara masing-masing titik hijau aktif.
1

masalah Anda mengingatkan saya pada beberapa kasus serupa, yang harus kami selesaikan beberapa tahun yang lalu: seseorang menggambar jalur (linestring) di atas peta raster dan kami harus mencocokkan jalur ini dengan jaringan jalan yang mendasari.

Ini tampaknya mirip dengan titik GPS merah Anda. Dan sama seperti Anda, kami berasumsi bahwa kami dapat mencari jalur terpendek antara titik-titik ini.

Karena ini sudah lama sekali, saya tidak ingat detail lagi. Tapi kami menerbitkan fungsi di "matching.sql", yang sudah menjadi bagian dari pgRouting. Tidak ada dokumentasi. Maaf untuk itu. Tetapi mungkin membaca sumber SQL memberi Anda beberapa ide bagaimana cara kerjanya: https://github.com/pgRouting/pgrouting/blob/master/core/sql/matching.sql

dkastl
sumber
Menggunakan node terdekat tidak berfungsi, pertimbangkan contoh di bawah ini.
Fungsi pencocokan ini saya sebutkan melakukan kombinasi pencocokan untuk node dan segmen jalan. Itu tergantung seberapa dekat titik GPS Anda ke sebuah node. Jika Anda sangat dekat dengan persimpangan, titik GPS Anda mungkin lebih dekat ke tepi, yang sebenarnya tidak boleh ditugaskan.
dkastl