Menemukan garis tengah terowongan?

19

Saya memiliki beberapa file peta yang terdiri dari 'polylines' (setiap baris hanyalah daftar simpul) yang mewakili terowongan, dan saya ingin mencoba dan menemukan terowongan 'garis tengah' (ditampilkan, kira-kira, merah di bawah).

teks alternatif

Saya sudah pernah sukses di masa lalu menggunakan triangulasi Delaunay tapi saya ingin menghindari metode itu karena tidak (secara umum) memungkinkan modifikasi data peta saya yang mudah / sering.

Ada ide tentang bagaimana saya bisa melakukan ini?

Saya bekerja di C ++ yang cukup mentah.

geometry algorithm polyline-creation skeleton sje397
sumber
gis.stackexchange.com/q/177/162 juga berkaitan dengan apa yang Anda cari: algoritma skeletisation .
julien
3
Saya pikir tautan silang dengan SO relevan karena ada jawaban di sana juga stackoverflow.com/questions/3983613/find-tunnel-center-line
Dr. belisarius
@julien: Anda sudah menautkan itu dalam jawaban Anda. Saya membacanya, tetapi tidak menjawab pertanyaan spesifik saya (yang, untuk diulangi, adalah: 'Saya sudah tahu bagaimana menemukan MAT - tetapi saya bertanya-tanya apakah ada yang tahu algoritma non-Delaunay [yaitu bukan lib - masalahnya bukan pengkodean saya;)] yang efisien untuk perubahan yang dilokalkan '). Ada jawaban pada SO yang juga tidak menjawab tetapi butuh banyak usaha dan memberi saya banyak untuk dipikirkan jadi saya telah memberikan cek kepada orang itu sampai sesuatu yang lebih baik datang. Tidak ada jawaban di bawah ini yang sebaik itu (yang mungkin salah saya).
sje397

Jawaban:

6

Anda telah membuat pendekatan yang bagus ke Transformasi Sumbu Medial. Triangulasi Delaunay memang menawarkan pendekatan yang baik untuk itu. (Tantangan utama adalah bahwa bagian-bagian dari TIK adalah potongan parabola, bukan hanya segmen garis.)

Saya telah menemukan referensi kode kerja (biasanya dalam C / C ++ saya ingat) dalam literatur akademik. Lakukan pencarian di Google Cendekia dan cari makalah yang lebih lama (yang lebih baru tampaknya berfokus pada perhitungan 3D).

whuber
sumber
Saya punya beberapa kode yang berfungsi, menggunakan Delaunay. Saya benar-benar bertanya apakah ada cara lain.
sje397
1
@ sje397 Pertama-tama, Delaunay hanya kira-kira menyelesaikan masalah, jadi untuk alasan itu saja dapat bernilai meneliti kode yang lebih baik. Kedua, memang ada cara lain. Saya dapat menguraikan dua secara singkat: (1) mencari MAT melalui buffer internal dan (2) melakukan analisis medan pada kisi jarak Euclidean dari polyline. Saya juga tidak menyebutkan karena keduanya jauh lebih tidak efisien dan menghasilkan hasil yang lebih buruk. Dapat dibayangkan bahwa metode kedua dapat menerima solusi dinamis yang cukup cepat.
whuber
4

Mungkin layak untuk melihat ke "kerangka poligon".

Ada beberapa sampel sumber C ++ di http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

underdark
sumber
Terima kasih underdark. Saya akan melihat lebih jauh ke dalam CGAL. Tetapi persyaratan bahwa perhitungan ulang tidak mahal ketika data peta saya berubah adalah kesulitannya.
sje397
CGAL cukup cepat - perhitungan on the fly harus dimungkinkan. Jika tidak, Anda dapat melihat apa yang disebut 'struktur data kinetik': cgal.org/Manual/3.3/doc_html/cgal_manual/…
julien
"Kerangka" adalah istilah lain untuk MAT. Mencari "medial axis transform" telah menghasilkan lebih banyak dan lebih baik daripada pencarian pada "skeleton" dalam pengalaman saya.
whuber
"skeleton" tampaknya lebih umum - MAT hanya satu algoritma spesifik untuk skeleton, kan? Apapun, itu bukan topiknya ...!
julien
Lisensi untuk CGAL terlihat membatasi (iev mahal - ini adalah perangkat lunak komersial).
sje397