Baris ke Poligon

11

Saya gagal menemukan "nama" algoritme yang memungkinkan seseorang mengonversi garis menjadi poligon. Karena masalah ini melintasi SIG dan bidang geometri komputasi dan ilmu komputer. Saya tidak yakin apa lagi yang harus ditambahkan ke dalam campuran. Saya enggan memberikan daftar apa yang telah saya cari karena saya juga ingin tahu apa yang orang lain akan pertimbangkan sebagai pilihan pertama kriteria pencarian mereka.

Skenario ... Saya memiliki garis (dua poin diperlukan untuk membangun garis) ... setiap baris terhubung ke setidaknya satu baris lainnya. Ruang intervening antara garis yang terhubung akan membentuk poligon. Skenario paling sederhana adalah segitiga ... persegi panjang ... dan seseorang dapat beralih ke fitur multi-segmen.

Maaf untuk deskripsi yang tidak jelas, tetapi seperti yang saya katakan, saya tidak ingin memandu solusi yang mungkin turun jalan yang telah saya kunjungi, karena saya tertarik pada "pikiran pertama" sebanyak solusi akhir.

polygon algorithm geometry-conversion Germán Carrillo
sumber
Bisakah garis bertepatan? Bisakah garis melintas? (Yaitu bersih?) Jika demikian, saya harap menyebut proses ini Build tidak akan terlalu spesifik aplikasi.
Kirk Kuykendall
Garis Kirk Coincident dan "cacat" lainnya akan dihapus sebelum membuat poligon ... Saya mencoba menemukan "nama algoritma" yang saya yakin telah diterapkan dalam berbagai paket GIS (misalnya arcgis). Jadi singkatnya, pertimbangkan bahwa semua kondisi degenerasi telah ditangani dan Anda dibiarkan dengan garis bersih (2 titik garis) yang bertepatan pada node yang Anda harus dapat membangun poligon. Kuncinya adalah bahwa garis ada, tidak ada kondisi yang merosot dan ruang intervensi perlu dikonversi menjadi poligon. Terima kasih
Apakah poin di pesawat atau di bola?
Kirk Kuykendall
Kirk ... Di pesawat, metrik x, koordinat y, bukan koordinat bola. Misalnya, Anda memiliki segmen garis yang akan membentuk diagram voronoi, tetapi yang Anda miliki hanyalah segmen yang membentuknya tetapi bukan struktur data aktual yang menyebabkannya. Singkatnya, setiap segmen terhubung dan setiap segmen unik.

Jawaban:

4

Mungkin "area isi"? Lihat di sini dan di sini .

Edit

Kemungkinan lain adalah triangulasi terkendala . (Tautan ke applet Java yang memungkinkan Anda menggambar grafik dengan mouse dan mengilustrasikan algoritma bidang-menyapu untuk melakukan triangulasi.) Hasil dari triangulasi semacam itu, tidak peduli bagaimana itu dilakukan, dapat dengan mudah diproses untuk buat poligon yang diinginkan: gabungkan semua segitiga tetangga yang berbagi tepi yang baru dibuat.

Contoh

Grafik asli:

Grafik asli

Grafik triangulasi:

masukkan deskripsi gambar di sini

whuber
sumber
Bill Akan mengambil suara sejak saya belum menemukan itu ... tidak ingin membatasi komentar lain dari orang-orang di berbagai disiplin ilmu.
Meskipun, sebagian besar berurusan dengan isian raster, ini adalah jawaban terdekat. Saya masih belum memiliki nama algoritme kecuali jika itu dilampirkan pada raster atau vektor tetapi algoritma "sweep" mungkin cukup, tetapi saya tidak tahu mengapa saya mengapa koordinat akan diurutkan berdasarkan Y daripada X ( yang mudah diimplementasikan dalam kebanyakan bahasa).
@Dan Menyortir berdasarkan y atau x tidak penting, seperti yang Anda sarankan. Anda juga benar bahwa algoritma bidang-sapuan atau sapuan garis terlibat, tetapi sayangnya ini adalah teknik umum yang mencakup hampir semua prosedur geometri komputasi, jadi itu bukan istilah yang cocok untuk mencari secara khusus untuk algoritme Anda. Perhatikan bahwa masalah khusus ini bukan semata-mata teoretis, karena melibatkan penyisipan kompleks polyline ke dalam bidang (atau sphere), dan oleh karena itu algoritma yang baik harus menjaga informasi tentang penyematan: itu sebabnya ini benar-benar masalah pengisian area di hati.
Whuber
5

Dalam teori grafik , operasi ini disebut komputasi wajah . Ini terkait dengan perhitungan dual dari grafik yang diberikan.

Misalnya, di perpustakaan java GeOxygène , grafik (disebut CarteTopo ) memiliki metode getFaces untuk mengambil wajahnya .

Ini disebut poligonisasi di JTS

Julien
sumber
Tautan yang bagus. Namun, mereka semua mengira masalah @ Dan telah diselesaikan: dapat memanggil grafik "planar" berarti Anda telah mengidentifikasi wajah poligonal. Dia ingin tahu bagaimana seseorang mengkonversi koleksi sewenang-wenang busur (di pesawat) menjadi grafik planar jujur-untuk-kebaikan di tempat pertama. Ini membutuhkan pembangunan representasi dari "topologi" -nya, seperti DCEL.
whuber
Terima kasih banyak, Anda adalah sumber pengetahuan! Saya bertanya-tanya bagaimana seseorang bisa begitu cemerlang.
julien
4

Perangkat lunak host RepRap mengubah daftar segmen garis (dalam beberapa urutan acak yang tidak diketahui) menjadi daftar poligon, yang terdengar mirip dengan apa yang Anda coba lakukan.

Secara khusus, algoritma "pencocokan akhir" RepRap menangani banyak kasus patologis.

Sayangnya, perangkat lunak RepRap mengasumsikan bahwa setiap sudut memiliki jumlah tepi yang merata - 2 garis menuju sudut pada objek normal; 4 baris berjalan bersama ketika sudut dari satu objek menyentuh sudut dari objek lain, dll. Saya tidak tahu betapa sulitnya untuk mengadaptasi algoritma ini untuk menangani diagram voronoi, yang biasanya memiliki 3 tepi menuju ke setiap sudut.

David Cary
sumber
+1 Temuan menarik! Berhati-hatilah: meskipun perangkat lunak ini kelihatannya mampu menyelesaikan banyak masalah yang berhubungan dengan menghubungkan saluran ke poligon, perangkat lunak ini mungkin melakukan terlalu banyak hal: sepertinya perangkat lunak itu mencoba menyederhanakan fitur-fiturnya juga, yang mungkin merupakan efek samping yang tidak diinginkan. (Misalnya, itu dapat menghancurkan integritas topologi.)
whuber
3

Sudahkah Anda menjelajahi basis kode GRASS untuk solusi masalah Anda? -> http://old.nabble.com/Polyline-to-Polygon-operation-td20257839.html

oeon
sumber
1
Terima kasih ... tapi saya tidak mencari solusi "paket" khusus tetapi algoritma yang mendasari dan / atau namanya yang akan datang berbagai bidang GIS, Comp Geom dan / atau Comp Sci ... pertahankan ide yang datang
Saya sedang berpikir untuk secara khusus melihat kode sumber di balik 2 proses yang disebutkan dalam tautan saya dapat membantu Anda.
Oeon
Saya kira saya harus menginstal perangkat lunak untuk melihat kode karena saya tidak melihat daftar pada halaman-halaman itu kecuali saya kehilangan sesuatu.
1
Anda dapat menelusuri sumber GRASS online: trac.osgeo.org/grass/browser
underdark
@ underdark Terima kasih atas penunjuknya. Sejauh yang saya tahu dari main.cdalam v.typesumber, semua yang terjadi adalah bahwa fitur yang re-label sebagai batas: tidak ada proses yang sebenarnya terjadi. Dalam retrospeksi ini tidak terlalu mengejutkan: jika (saya tidak tahu pasti) fitur dipertahankan dengan informasi topologi 2D penuh, maka semua perhitungan untuk mengidentifikasi daerah poligonal secara otomatis terjadi selama pembuatan atau impor fitur dan dipertahankan sepanjang semua operasi geoproses.
whuber
3

Halo

Saya tidak berpikir apa yang Anda cari adalah algoritma tertentu. Tugasnya bisa sangat sulit atau sangat sederhana tergantung pada dataset Anda.

Anda harus membagi masalah dalam setidaknya 2 bagian. 1) lebih merupakan masalah jaringan, bagaimana menemukan cincin tertutup dari linestrings. 2) mengekspresikan linestring tertutup sebagai poligon

Bagian kedua, yaitu "mengubah garis menjadi poligon" lebih tergantung pada format daripada representasi poligon / linestring. Maksud saya pergi dari:

LINESTRING (1 1, 2 2)
LINESTRING (2 2, 2 1)
LINESTRING (2 1, 1 1)

ke:
POLYGON ((1 1,2 2,2 1,1 1))

mengkonversi baris ke poligon, tetapi bukan itu yang Anda bicarakan, saya kira. Bagian yang lebih sulit adalah yang pertama. Jika Anda memiliki spageti garis, cara memesannya sebagai linestrings tertutup.

Saya kira jawaban untuk pertanyaan itu banyak bergantung pada dataset. Seperti yang ditanyakan Kirk, jika garis-garis itu bisa melewati masalah, jauh lebih besar. Jika Anda tahu bahwa semua "koleksi garis" adalah bagian dari linestring tertutup, semakin mudah. Kemudian Anda dapat mengambil garis apa pun dan berjalan di sekitar jalan sampai Anda kembali lagi dan kemudian melanjutkan ke langkah dua di atas.

Maksud saya adalah bahwa kondisi dataset menetapkan semua aturan tentang cara melakukannya. Jika Anda ingin menemukan semua kemungkinan poligon dalam spaghetti dari linestrings, saya berasumsi akan ada banyak algoritma yang berbeda yang terlibat untuk menempatkan titik titik di semua persimpangan, mencari semua jalur yang mungkin dan sebagainya.

Dalam PostGIS fungsi ini disebut ST_Polygonize Fungsi itu menciptakan semua kemungkinan poligon dari linestrings yang Anda berikan.

Itu dilakukan oleh GEOS sehingga Anda dapat menemukan algoritma di belakang di kedua kode GEOS dan JTS.

Hanya beberapa pemikiran

/ Nicklas

Nicklas Avén
sumber
1

Anda dapat mencoba mencari algoritma "Forward Star". Saya telah diberitahu bahwa ini adalah generik, tetapi satu-satunya diskusi tentang hal itu yang pernah saya baca selalu mengacu pada arcgis. Mungkin lihat referensi yang dikutip dalam catatan kuliah ini untuk bintang depan.

Kirk Kuykendall
sumber
1
Saya akan berkomentar di sini, meskipun komentar ini membahas beberapa solusi yang diusulkan juga: masalahnya tidak dapat diwakili dalam jaringan (atau grafik). Ini membutuhkan informasi tentang bagaimana garis-garis terhubung dalam permukaan dua dimensi . Dengan demikian representasi bintang maju / mundur tidak banyak berguna; DCEL atau sesuatu seperti itu diperlukan.
whuber
@whuber - Saya berasumsi bahwa komentar Dan bahwa semua "cacat" telah dihapus menyiratkan bahwa garis itu bersih. Dengan demikian, harus dimungkinkan untuk mereduksi ini menjadi masalah traversal grafik untuk menemukan semua siklus dalam grafik. Pada awalnya saya pikir bintang Forward akan membantu dalam algoritma yang berjalan di sekitar grafik mengambil belokan kanan paling tajam yang mungkin di setiap node. Namun, kelihatannya lebih banyak terlihat ada cara yang lebih baik. stackoverflow.com/questions/261573/… Tapi tetap saja, ini mengasumsikan masalah dapat dinyatakan kembali sebagai grafik.
Kirk Kuykendall
1
Menemukan siklus dalam grafik tidak sama dengan menemukan wajah dalam grafik planar. Pertimbangkan grafik abstrak dengan simpul {a, b, c, d} dan tepi {a, b}, {a, c}, {b, c}, {b, d}, {c, d}. Dasar untuk siklus terdiri dari a-> b-> d-> c-> a dan a-> b-> c-> a. Dalam planar embedding a -> (0,1), b -> (2,2), c -> (2,0), d -> (3,1) (di mana semua tepi adalah segmen garis), siklus a-> b-> d-> c-> a bukan wajah, tetapi jika kita pindah d ke (1,1), itu adalah wajah. Ini menunjukkan mengapa konsep "wajah" memerlukan grafik untuk disematkan dalam bidang dan mengapa wajah tidak dapat dihitung secara murni dari struktur abstrak grafik.
whuber