Hasilkan poligon dari satu set garis berpotongan

10

Ini adalah pertanyaan sederhana dan sangat umum yang telah ditanyakan untuk tujuan yang berbeda (lihat tautan ini dan ini juga , misalnya), di sini, bagaimanapun, kami mencari bukan paket perangkat lunak tetapi algoritma yang dapat kami coba implementasikan katakan dalam Python .

Jadi, seperti yang ditunjukkan di bawah ini serangkaian garis dipetakan (mereka sudah dipangkas, BTW).
Algoritma / ide untuk menghasilkan poligon (seperti yang ditunjukkan merah) ?

masukkan deskripsi gambar di sini

algorithm polygonize geometry-conversion Pengembang
sumber
Apakah batas luar kotak diketahui, atau apakah itu juga, harus dibaca dari jalur input?
Devdatta Tengshe

Jawaban:

5

Baiklah, kami memberikan jawaban di sini yang bukan merupakan jawaban lengkap untuk pertanyaan kami, yaitu pertanyaan itu akan tetap " terbuka untuk dijawab ". Namun itu adalah solusi untuk masalah dalam pertanyaan. Inilah trik yang kami gunakan:

Pertama mari kita lihat hasilnya :
masukkan deskripsi gambar di sini

Jadi garis yang diberikan dalam leftpoligon yang dibangun ditunjukkan dalam middle. Mereka adalah poligon nyata seperti yang ditunjukkan pada right;)

Untuk algoritma yang diberikan di bawah ini kami menggunakan Shapelypaket dalam Python .

  • lines ==> MultiLineString {:: M}
  • tambahkan kecil buffer, katakan eps{:: MB}
  • region ==> Polygon {:: P} (wilayah di sini adalah bujur sangkar)
  • P.difference(MB) {poligon yang dihasilkan}

Perhatikan bahwa operasi ini sunyi dengan cepat. Namun, titik yang hilang adalah bahwa algoritma tersebut bukan metode asli untuk membangun poligon dari garis . Namun demikian itu bekerja dengan sempurna untuk masalah yang kami miliki di tangan kami.

Pengembang
sumber
4

JTS Topology Suite memiliki kelas Polygonizer, yang cukup banyak melakukan hal ini.

Anda dapat melihat kode sumbernya, tersedia di sini , dan mengonversinya menjadi Python.

Devdatta Tengshe
sumber
Seperti uraian kode yang mengatakan itu tidak akan berfungsi seperti yang diharapkan oleh penulis pertanyaan: "edge harus mengangguk dengan benar; yaitu, mereka hanya harus bertemu pada titik akhir mereka. Polygonizer akan berjalan pada input yang salah diklik tetapi tidak akan membentuk poligon dari non -noded edge "
Pablo
1
Ada operasi di dalam JTS untuk memisahkan Garis dengan benar pada simpul. Mungkin OP juga bisa melihatnya.
Devdatta Tengshe
3

Anda mungkin melihat paket Python Shapely, khususnya poligon ()

Dave
sumber
Catatan singkat yang mempoligonisasi di Shapely ( from shapely.ops import polygonize) menggunakan GEOS.Poligonisasi dari GEOS . Jadi ini adalah tautan di mana ada tautan ke tautan ...: |
Pengembang
Percobaan kami dengan polygonizetidak berhasil sama sekali. Namun terima kasih telah mengingatkan kami Shapelyyang dengannya kami dapat menemukan solusi (tipuan, sebenarnya) sebagaimana diposting sebagai jawaban.
Pengembang
2

Berikut ini solusi lain yang bisa kami temukan.

Menggunakan DCELkita dapat membuat blok dari menyentuh garis.

Untuk Python ada paket {di sini} . Ini adalah implementasi kecil dengan beberapa bug. Namun demikian dengan beberapa upaya dapat digunakan untuk masalah ini. Perhatikan juga tahapan-tahapan berikut:

Tahap pra-pemrosesan dengan mana semua persimpangan antara garis ditemukan. Maka dengan demikian semua garis dipecah menjadi segmen pada titik-titik interaksi. Daftar titik persimpangan dan daftar tepi terkait adalah yang diperlukan untuk DCEL.

Pengembang
sumber
Karena metode ini merupakan solusi asli dan memberikan kinerja yang jauh lebih baik dibandingkan dengan metode lain di mana differenceoperasi sedang digunakan.
Pengembang