Saya ingin menggambar peta poligon 2d berdasarkan data yang disediakan oleh sumber lain untuk memudahkan menganalisis tindakan pada peta. Data memiliki format berikut:
1 ['2', '4', '5', '7', '17', '10']
2 ['1', '3', '4']
3 ['2', '11', '4']
4 ['1', '2', '3', '11', '13', '18', '5']
5 ['1', '4', '18', '17']
6 ['7', '8']
...Nomor pertama adalah ID dari sebuah node, daftar berikut berisi ID dari tetangganya. Karena jumlah node tetangga berbeda, saya perlu menggambar peta poligon.
Jadi saya mencoba menggunakan poligon Voronoi untuk representasi peta. Masalahnya adalah: Bagaimana saya bisa menentukan poin untuk memuaskan semua hubungan lingkungan? Saya kira percobaan pertama saya kurang lebih merupakan kesalahan dalam siklus coba-coba saya. Saya menggunakan alat sfdp dari graphviz untuk mendapatkan posisi titik dari grafik:
Menggunakan posisi titik menghasilkan representasi peta berikut:
Masalah dari pendekatan ini adalah bahwa misalnya node 4 dan 1 adalah tetangga tetapi dalam diagram Voronoi mereka bukan karena posisi node. Jadi bagi saya pendekatan ini gagal.
Googling, saya menemukan banyak tutorial membuat peta dengan poligon atau ubin, tetapi saya belum tahu bagaimana saya bisa membuat peta untuk data yang diberikan. Saya kira ada pendekatan menggunakan (beberapa) segi enam / segitiga / kotak atau campuran untuk mencapai apa yang saya butuhkan tetapi saya tidak tahu apa yang akan saya cari.
Apakah ada kata kunci atau algoritma yang dapat membantu saya di sini?
Pembaruan / Hasil : Untuk kelengkapan: Ini adalah hasil saya setelah menggunakan saran dari jawaban yang diterima:
Jawaban:
Yang Anda inginkan adalah menghasilkan grafik ganda ; yaitu, grafik yang dihasilkan dengan mengubah wajah menjadi simpul , dan menghubungkannya berdasarkan wajah yang berdekatan di grafik asli. Contoh:
Masalahnya, seperti yang Anda lihat, adalah bahwa jika Anda ingin mempertahankan tata letak grafik yang sama, Anda akan mendapatkan beberapa tepi yang benar-benar melengkung di grafik ganda. Selain itu, Anda akan sering berakhir dengan multigraf - grafik di mana beberapa simpul memiliki beberapa tepi di antaranya. Ini dijamin planar, jadi itu sesuatu.
Untuk menggunakan contoh Anda, kami dapat menghasilkan grafik ganda dalam langkah-langkah berikut:
Langkah 1: Untuk setiap wajah dalam grafik asli, buat simpul
Perhatikan bahwa kita membuat "cincin" luar untuk mewakili "titik" terluar - ini adalah agar kita dapat memiliki grafik yang tampak lebih bagus di bagian akhir, tanpa tepi lengkung gila.
Langkah 2: Untuk setiap tepi dalam grafik asli, hubungkan kedua simpul wajah dengan tepi
Juga, Anda harus melakukan sesuatu agar tepinya tidak saling tumpang tindih. Kesenjangan antara 3 dan 12 sangat bermasalah. Tepi baru ini mungkin harus lentur untuk memungkinkan ini. Itu yang Anda dapatkan karena memiliki grafik cekung.
Langkah 3: Mainkan Risiko
sumber
Jika gambar pertama, di mana setiap titik adalah kotak kecil dengan warna tertentu, adalah apa yang Anda cari, Anda perlu membangun triangulasi Delaunay.
sumber