Bagaimana cara menggambarkan hubungan khusus antara tepi yang terhubung?

Pertimbangkan situasi sederhana ini di mana tiga sisi terhubung pada satu simpul:

hubungan tepi

Saya ingin menulis deskripsi yang ringkas dan jelas tentang hubungan antara A dan B sedemikian rupa sehingga membedakannya dari hubungan antara A dan C. Sesuatu seperti “ketika melintasi simpul ke arah searah jarum jam, A berbatasan? ke B, tetapi A tidak berdekatan? ke C. " Tapi itu tidak benar-benar kedekatan.

Mengatakan dengan cara yang berbeda: bayangkan Anda berdiri di atas simpul dan Anda menghadap ke A. Anda mulai memutar diri searah jarum jam. Tepi berikutnya yang akan Anda tuju adalah B, bukan C.

Apakah ada cara untuk menggambarkan hubungan ini antara A dan B dengan cara yang lebih ringkas, formal, atau benar daripada yang saya tulis di atas?

Itu harus directional (satu hubungan jenis ini ada di arah searah jarum jam dari A, dan yang lain ada di arah berlawanan arah jarum jam). Dan itu harus meningkatkan skala ke kasus-kasus di mana lebih dari tiga tepi terhubung pada node. Mungkin ada hubungannya dengan routing? (Saya sedang memikirkan hal ini dalam konteks jaringan jalan.)

Dua pendekatan yang sudah saya coba tetapi belum terlalu jauh dengan:

Referensi topologi 9IM seperti : Saya telah melihat DE-9IM , dan meskipun saya bukan ahli matematika, saya pikir saya masih bisa mengatakan dari diagram dan istilah bahwa itu tidak mencakup jenis hubungan ini. Saya juga belum menemukannya di deskripsi topologi pada bantuan ESRI atau bantuan Oracle . (Mungkin ada sesuatu di sana tapi aku belum menemukannya!)
Wajah : Saya telah bermain-main dengan fakta bahwa wajah di sisi "utara" A mungkin juga dibatasi oleh B, tetapi bukan C. Namun, seperti yang Anda lihat dalam diagram di sini, itu tidak selalu benar. Bayangkan diagram saya adalah kutipan dari jaringan jalan di mana A dan C adalah jalan arteri dan B adalah jalan buntu pendek.

Saya menduga mungkin tidak ada satu istilah untuk apa yang saya coba katakan; setidaknya saya ingin dapat menggambarkan hubungan seperti itu dengan cara yang lebih sederhana daripada yang saya lakukan di atas. Ini adalah pertanyaan platform-independen. Saat ini, saya hanya mencari kata-kata yang tepat. Nanti saya akan mencoba untuk mengimplementasikan konsep dalam python (pyqgis atau arcpy) pada sebuah shapefile, jadi setiap jawaban dengan titik akhir itu akan sangat menarik, tetapi tidak perlu.

vector topology terminology de-9im andytilia
sumber

Mengapa Anda tidak melampirkan ke setiap simpul daftar tepi yang terhubung dengan itu diperintahkan oleh arah?

julien

Sepertinya Anda mencari DCEL . Perhatikan bahwa ketika Anda menggandakan grafik planar , wajah menjadi node. Dalam ilustrasi ada potongan tiga wajah alpha , beta , dan gamma , dengan edge A memisahkan beta dari gamma , edge B memisahkan gamma dari alpha , dan edge C memisahkan alpha dari beta . Yang menghasilkan grafik siklik yang berisi semua informasi yang Anda cari - dan memang itu adalah kedekatan dalam grafik ganda.

whuber

@ Julien, terima kasih - itu ide implementasi yang layak; Saya akan mencobanya. Tapi pertama-tama ... Saya sedang mencari kata atau frasa untuk menggambarkan jenis hubungan ini.

andytilia

@whuber, terima kasih atas tipnya. Saya belum pernah bertemu DCEL sebelumnya. Sepertinya B adalah "berikutnya" setengah-sisi dari northfacing, setengah-sisi barat dari A. Hm: maka jika saya ingin pergi berlawanan arah, maka saya mempertimbangkan setengah-sisi yang menghadap ke selatan dari A. Dan "ke barat" tersirat oleh simpul umum. Saya ingin tahu apakah itu akan berfungsi ketika B bukan batas wajah (mis. Jalan buntu). Saya akan melihat lebih jauh.

andytilia

@ Julien, saya membaca komentar Anda lagi. Saya bisa melihat sekarang Anda memberi saya ungkapan yang disarankan juga. :-) Mungkin saya bisa menggunakan "diperintahkan oleh arah" untuk menggambarkan hubungan. Harus bermain-main dengannya sedikit.

andytilia

Jawaban:

Saya tahu bahwa saya agak terlambat ke pesta di sini, tapi ini hal yang cukup menarik, dan saya berharap jawaban saya bisa berguna.

Apa yang Anda tanyakan adalah hubungan kualitatif; sering diabaikan saudara hubungan kuantitatif. Penalaran kualitatif muncul cukup sering dalam ilmu geospasial. Contoh kueri meliputi: Paket mana yang berdekatan dengan yang ini? Fitur apa yang ada di dalam tumpang tindih wilayah A dan wilayah B? Wilayah mana yang cekung? Jalan mana di sebelah kiri? Hubungannya adalah: bersebelahan dengan, di dalam, cekung, dan kiri. Pertanyaan kualitatif sering diabaikan atau dinilai rendah jika dibandingkan dengan pertanyaan kuantitatif seperti mana yang lebih besar, lebih pendek, atau lebih besar jumlahnya.

Suatu relasi kualitatif yang mengambil dua input disebut relasi biner. Ada dua notasi umum untuk ini: - isLeftOf (A, B) Ini adalah notasi awalan. - A isLeftOf B Ini adalah notasi infiks.

Dalam contoh di atas ada juga hubungan unary: isConcave. Relasi ini menghubungkan suatu wilayah dengan daerah itu sendiri dan akan mengembalikan nilai boolean.

Semua predikat spasial Egenhofer dalam model 9-persimpangan (dirujuk dalam 9EIM) adalah hubungan biner antara dua wilayah. Anda mungkin juga tertarik dengan Randell, Cui dan Cohn's RCC (http://en.wikipedia.org/wiki/Region_connection_calculus). Hubungan kualitatif (topologis) yang diberikan dalam bidang studi ini menghubungkan daerah dengan daerah, dan karya selanjutnya menghubungkan garis ke daerah dan garis ke garis. Namun, ini tidak cukup apa yang Anda cari.

OK, maaf atas penyimpangan itu, tapi semoga itu membantu dengan aspek terminologi pertanyaan Anda.

@whuber benar di jalurnya dengan menyarankan daftar tepi terhubung ganda (DCEL). Ini adalah kerabat dekat peta kombinatorial, sering digunakan di bawah penutup dalam sistem CAD, dan ujung bersayap. Konsep winged edge (http://en.wikipedia.org/wiki/Winged_edge) adalah bagaimana standar teks terkenal mendefinisikan lubang dalam poligon (http://en.wikipedia.org/wiki/Well-known_text) #Geometric_objects). Perhatikan pada poligon bahwa urutan titik luar berlawanan arah jarum jam, dan searah jarum jam untuk titik dalam. Seorang peri kecil yang berjalan di sepanjang batas dalam urutan ini akan selalu melihat bagian dalam wilayah di sebelah kirinya.

Dengan peta kombinatorial dan DCEL titik kuncinya adalah bahwa objek-objek ini didefinisikan pada permukaan yang dapat diorientasikan. Kami tidak perlu masuk ke formalitas matematika - idenya cukup sederhana: jika Anda dapat menentukan arah di permukaan, seperti yang Anda bisa dengan sistem referensi spasial dalam GIS, maka Anda memiliki permukaan yang dapat diorientasikan. Jadi, jika Anda dapat menentukan arah, maka Anda dapat menentukan urutan arah di setiap titik di permukaan. Dengan pemesanan terarah Anda dapat menentukan isLeftOf (A, B), isRotATIONALAdjacentTo (A, B) dan sebagainya.

Menentukan pemesanan di sekitar titik dalam grafik yang tertanam di permukaan membutuhkan dua penugasan: 1) menugaskan label ke ujung titik tepi dan 2) menetapkan konvensi untuk pesanan di sekitar titik. Jika elemen order dalam array (mis. [A, B, C] pada gambar Anda) searah jarum jam, maka kita dapat mengetahui sisi mana yang berada di sebelah kiri B.

Dalam contoh Anda, setiap elemen berdekatan dengan yang lain. Fakta itu juga terlihat dalam array karena array sebenarnya mewakili permutasi, yaitu urutan yang penting, tetapi elemen mana yang pertama tidak. Jadi [A, B, C] setara dengan [C, A, B]. Dengan kata lain, array membungkus membuat elemen terakhir yang berdekatan dengan yang pertama.

katahdin
sumber

Terima kasih! Saya suka istilah "RotATIONAL Adjacent". Itu hanya perlu diperpanjang, seperti yang Anda katakan, dengan konvensi untuk memesan sekitar titik. Dalam kasus saya, saya perlu mendefinisikan kasus konvensi per kasus. Jadi saya akan bekerja pada pengkodean sesuatu seperti isRotATIONALAdjacentTo (A, B, Direction) menggunakan permutasi seperti yang Anda sarankan. Atau dalam hal kasus di atas "A searah-jarum jam berbatasan dengan B, dan A tidak searah-jarum jam berbatasan dengan C".

andytilia

Ngomong-ngomong, saya belum melihat ke Kalkulus Koneksi Wilayah. Meskipun tidak cukup apa yang memecahkan masalah ini (seperti yang Anda sebutkan), tetap saja menarik. Bisakah Anda mengarahkan saya ke "karya selanjutnya" yang ada dalam pikiran Anda oleh Randell, Cui dan Cohn? (hm: karakter RC&C menciptakan kerangka kerja yang disebut RCC)

andytilia

Ketika Anda melihat topologi dan grafik konektivitas yang Anda dapatkan dari vendor seperti Teleatlas, Navteq, ESRI, dll, Anda akan mulai melihat suatu pola (tentu saja setiap orang memiliki cara "khusus" mereka sendiri dalam melakukan sesuatu).

Secara pribadi , walaupun 1) Topologi Geospasial dan 2) Routing Graphs hanyalah Graphs dan dapat digeneralisasi untuk direpresentasikan dalam struktur data yang sama, saya mencoba untuk menghindarinya sebanyak mungkin.

Saya mencoba membuat perbedaan di kepala saya.

Ketika saya mengatakan "Topologi Geospasial" (1) Maksud saya struktur grafik untuk mewakili hubungan geometris dari fitur (misalnya apa yang tersisa dari tepi A, apa wajah yang dibentuk oleh tepi [A, B, C], apa yang terkandung oleh wajah B, dll).
Ketika saya mengatakan "Routing Graph" (2), maksud saya struktur grafik untuk menyelesaikan masalah routing (misalnya jalur terpendek untuk mendapatkan dari A-> B dengan pembatasan / ketentuan [X])

Mereka hanya grafik, dan mereka milik luasnya ilmu pengetahuan , tetapi ada keuntungan yang jelas tidak menggeneralisasi sebagai hal yang sama. Mereka melayani tujuan yang berbeda, dan jauh lebih mudah untuk mengoptimalkan dan menerapkan operasi ketika mereka dikhususkan untuk tujuan tertentu.

ESRI melakukan ini. Mereka memiliki struktur grafik untuk Topologi Geospasial (TopologiGraph) dan struktur Grafik yang berbeda untuk Masalah Routing (dataset jaringan). Heck, mereka bahkan memiliki Struktur Grafik yang lebih lama - Jaringan Geometrik - yang berfungsi dengan baik untuk masalah aliran di jaringan utilitas.

Dapat diperdebatkan, di dunia PostgreSQL / PostGIS, kami juga menemukan ini. Ada struktur data untuk routing dan satu lagi untuk topologi geospasial .

Dalam pertanyaan Anda, Anda berbicara tentang grafik dan menavigasi mereka searah jarum jam dan berlawanan arah jarum jam, serta wajah-wajah, yang membuat saya yakin bahwa Anda menginginkan struktur khusus untuk (1).

Untuk "Topologi Geospasial", saya pikir cara yang baik untuk mewakili Topologi semacam ini adalah cara yang dilakukan Kantor Hidrografi Inggris dalam S57 Topologi mereka, Deskripsi Topologi Lengkap .

Topologi Lengkap UKHO

Sangat mirip dengan apa yang dilakukan semua implementasi utama.

Sekarang, jika apa yang Anda cari adalah perutean, maka grafik menjadi berbeda berdasarkan apakah Anda memerlukan satu arah atau konektivitas dua arah. Pada akhirnya, intinya adalah:

Memiliki DARI simpul yang terhubung ke simpul yang membuat Tepi
The Tepi memiliki atribut untuk sisi kiri dan kanan (misalnya rentang alamat).
The Persimpangan (yaitu node di mana ujung-ujungnya terhubung) dapat memiliki satu set pembatasan. Jadi pada dasarnya Anda akan memiliki entri persimpangan utama untuk mewakili persimpangan itu sendiri, dan entri individual dengan entri FROM dan TO untuk mewakili batasan aliran.

Semoga sukses, dan beri tahu kami bagaimana proyek Anda ternyata.

Ragi Yaser Burhum
sumber

Terima kasih banyak karena telah membuat perbedaan yang jelas antara dua jenis grafik. Apakah Anda pikir itu perbedaan yang adil untuk mengatakan bahwa Routing Graphs umumnya mengandung beberapa informasi pada edge dan / atau node, sedangkan Geospatial Topology tidak pernah membutuhkan atribusi pada edge dan node (hanya didasarkan pada hubungan spasial antara objek)? Saya kira masalah saya sangat cocok dalam domain Topologi Geospasial: hubungan antara Tepi A dan B ada terlepas dari atribusi apa pun di tepinya. Tapi saya masih kehilangan cara ringkas untuk menyebutkan hubungan ini ...

andytilia

Saya pikir itu terlalu kuat dari sebuah pernyataan untuk mengatakan bahwa "Topologi Geospasial tidak pernah membutuhkan atribusi pada tepi dan simpul", itu benar-benar berdasarkan kasus per kasus. Saya telah melihat Grafik Topologi yang berisi atribusi yang dibagi di antara fitur yang memiliki simpul itu. Contohnya adalah nilai Z atau Temperatur. Saya akan mengatakan katakan saja sebut saja simpul dan buat perbedaan simpul yang terhubung bila perlu, tetapi tentu saja, saya tidak memiliki cukup konteks dari keseluruhan masalah yang Anda coba selesaikan.

Ragi Yaser Burhum

Ah, benar, terima kasih: representasi grafik planar dari dua jalan yang melintasi jembatan. Mungkin ada satu simpul dengan empat sisi, tetapi tidak semua sisi terhubung satu sama lain. Jadi node perlu berisi informasi tentang level persimpangan, untuk membedakan situasi itu dari persimpangan di-grade.

andytilia

Tepatnya :). Itu sebabnya saya menyebutkan persimpangan. Saya sedang memikirkan kasus itu. Salah satu cara untuk melakukannya adalah dengan merepresentasikan persimpangan sebagai "master node" dengan entri FROM-TO. Situasi jalan layang / jalan layang terjadi setiap saat. Bahkan yang terburuk adalah kasus-kasus seperti Bay Bridge atau di Chicago di mana Anda memiliki tepi yang cocok dalam ruang 2D (mereka secara efektif saling berhadapan) dengan satu set tepi yang mengalir satu arah, sementara yang lain mengalir dengan cara lain.

Ragi Yaser Burhum