PgRouting - Bagaimana cara memotong tautan saat mencapai biaya maksimal?

13

Saya memiliki shapefile polyline yang mewakili jaringan jalan dan shapefile kedua yang mengandung poin. Saya ingin menggunakan PostGIS (mungkin PgRouting) untuk mengidentifikasi sub-jaringan atau area layanan yang terpancar dari titik-titik ini.

Pada dasarnya, saya berharap untuk mengajukan pertanyaan, "Mulai dari titik X, seberapa jauh saya bisa berjalan ke arah mana pun, dengan total anggaran perjalanan 1 km, mengikuti jaringan jalan?" Hasilnya adalah seperangkat polyline terpotong yang mewakili kisaran total kemungkinan perjalanan, mengingat anggaran perjalanan 1 km.

Sebagai referensi, analisis GRASS ini tampaknya persis seperti yang ingin saya lakukan (kecuali saya ingin melakukan ini di PostGIS): http://www.gdf-hannover.de/lit_html/grass60_v1.2_en/node57.html#sec: optalloc

Contoh berikut ini tampaknya hampir apa yang ingin saya lakukan, kecuali tampaknya menjawab pertanyaan "node mana yang bisa saya tempuh untuk diberi anggaran perjalanan jarak X?" http://underdark.wordpress.com/2011/02/12/drive-time-isochrones/

Yang kedua tidak cukup jawaban yang saya cari, karena saya ingin polylines terpotong pada jarak tempuh saya - saya tidak peduli apakah saya bisa sampai ke titik.

postgis network pgrouting Peter
sumber
Salah satu opsi yang terjadi pada saya adalah entah bagaimana membagi polyline saya menjadi banyak poin. Itu membuat saya lebih dekat ke jawaban yang benar, tetapi tampaknya cukup berantakan, dan masih belum cukup membuat saya sampai di sana.
Peter

Jawaban:

2

Satu pemikiran yang saya miliki adalah untuk 1) menjalankan rutin driving_distance dan 2) menggunakan rutin "points_as_polygon" dari pgRouting (yang memanggil fungsi alphashape) untuk menghasilkan poligon terkecil pada jarak biaya tertentu berdasarkan pada titik rutinitas driving_distance kembali. Kemudian Anda bisa memilih semua jalan dalam poligon yang akan memberi Anda gambaran umum tentang perjalanan.

Jika Anda belum mengikuti diskusi di daftar pengguna pgRouting , mereka telah membahas lebih banyak opsi belakangan ini (utas Mei & Juni 2011).

RyanKDalton
sumber
1
Diskusi daftar pengguna yang menarik. Sayang sekali fungsi driving_distance buggy.
underdark
1

Karena ini benar-benar masalah grafik, yang Anda butuhkan adalah konektivitas / topologi + informasi biaya. Untuk pg_routing, itu adalah tabel yang Anda kirim ke algoritma jalur terpendek. Artikel ini memiliki informasi tentang cara membangunnya (saya berasumsi Anda sudah memilikinya). Maaf saya tidak bisa memberikan fungsi persisnya di pg_routing yang melakukan ini, tetapi menulis satu bisa dilakukan. Namun, saya dapat memberitahu Anda bahwa jika Anda terus memanggil shortest_path berulang-ulang Anda melakukan algoritma di bawah ini berulang-ulang dan membuang hasilnya - tidak efisien sama sekali.

Solusi Anda kemudian menjadi berjalan di setiap sisi sambil menambahkannya ke "daftar berjalan" dan menghitung biaya sampai anggaran Anda (yaitu jarak) ditarik mundur. Jika anggaran dapat diterima (mis. Anggaran belum ditarik berlebihan), Anda juga menambahkan geometri ke "kantong geometri daftar yang dapat diterima". Anda hanya perlu memproses setiap sisi tepat satu kali. Untuk tepi terakhir (di mana anggaran Anda terlalu banyak ditarik), Anda perlu mendapatkan panjangnya dan menginterpolasi jarak persis yang ingin Anda tempuh , kemudian menambahkan hasilnya ke "daftar yang dapat diterima". Hasil Anda adalah gabungan dari tas geometri itu.

Ragi Yaser Burhum
sumber
1
Ada kehalusan pada langkah terakhir: beberapa tepi bisa dicapai dari salah satu dari ujungnya. Hal ini dapat menyebabkan bagian dari kedua ujungnya dimasukkan atau bahkan seluruh tepi, meskipun melintasi seluruh tepi dari salah satu dari titik akhir akan melebihi batas anggaran. Misalnya, pertimbangkan untuk bepergian dari titik a di sepanjang grafik tidak berarah dengan ujung panjang unit {(a, b), (a, c), (b, c)} dan anggaran sebesar 1,6. Anda dapat mencapai b atau c dengan biaya 1, dengan 0,6 tersisa untuk dibelanjakan. Ini membuat setiap titik di sepanjang tepi (b, c) dapat diakses.
whuber
Anda benar :) +1
Ragi Yaser Burhum
1

"Mulai dari titik X, seberapa jauh saya bisa berjalan ke arah tertentu, diberi total anggaran perjalanan 1 km, mengikuti jaringan jalan?"

Karena Anda hanya perlu mempertimbangkan wilayah kecil (radius maksimal 1 km), Anda mungkin dapat memisahkan pembagian tautan menjadi beberapa bagian kecil (tergantung pada akurasi yang ingin Anda capai) dan membuat simpul yang diperlukan. Jaringan "resolusi tinggi" yang dihasilkan masih dapat dikelola.

underdark
sumber