Packing Polygons dalam polygon menggunakan ArcGIS Desktop?

25

Saya memiliki raster Boolean.

Di wilayah abu-abu raster saya ingin menyesuaikan poligon ukuran tertentu dalam batas yang berdekatan.

Pada dasarnya, saya memiliki poligon tidak beraturan, dan saya ingin "cocok" dengan poligon yang dikenal sejauh poligon tidak teratur sebanyak mungkin.

Arah poligon tidak masalah, dan bisa persegi. Saya ingin itu agar sesuai secara grafis, tetapi jika itu hanya melampirkan angka ke poligon (# yang cocok) yang akan berfungsi juga.

Saya menggunakan ArcGIS Desktop 10.

Ini
sumber
8
Ini masalah yang sangat sulit. Sebagai contoh, dibutuhkan banyak pekerjaan hanya untuk memasukkan lingkaran sebanyak mungkin ke dalam kotak. Ketika poligon asli rumit - seperti dalam ilustrasi - Anda memerlukan beberapa prosedur optimasi yang kuat. Metode terbaik yang saya temukan untuk masalah ini adalah simulasi anil, tetapi itu tidak akan tersedia di ArcGIS dan akan membutuhkan skrip yang sangat licik untuk skrip itu (ArcGIS terlalu lambat). Bisakah Anda sedikit mengendurkan persyaratan Anda, seperti memasang poligon yang lebih kecil dalam jumlah yang cukup , daripada sebanyak mungkin?
Whuber
1
@whuber Terima kasih telah mengedit posting saya. Ya, beberapa kali cukup akan berhasil. Atau, bagaimana dengan orientasi sudut tertentu. ex. pada gambar di atas, saya telah memasukkan poligon sebanyak yang saya bisa pada orientasi itu, seandainya saya memutarnya 90 derajat Anda bisa muat satu lagi ...
Thad
1
Ya, tapi itu juga penuh dengan jebakan. Ada yang dasar. Misalnya, teks ESRI yang ditulis dan diterbitkan, "Getting to Know ArcView GIS" (untuk versi 3) termasuk latihan di mana persegi panjang yang mewakili lapangan sepak bola ditempatkan secara interaktif di dalam poligon. Masalahnya adalah, jawaban latihan salah karena penulis gagal memproyeksikan data dan kesalahan dalam menggunakan koordinat geografis cukup besar untuk mempengaruhi hasilnya. Jawabannya terlihat bagus di GIS, tetapi jika ada yang berusaha membangun bidang itu, mereka akan menemukan tidak ada cukup ruang untuk itu :-).
whuber
6
@whuber Saya kira mereka berpikir angka "ball park" sudah cukup.
Kirk Kuykendall
2
Dalam kasus umum poligon tidak beraturan dalam poligon tidak beraturan, ini adalah masalah yang tidak dapat dikomputasi secara komputasional: Menemukan solusi optimal bukanlah tujuan yang masuk akal dalam semua kasus, dan kemungkinan NP-lengkap dari perspektif teknis: Kasus-kasus mana yang tidak dapat ditentukan sebelumnya. Jika Anda membatasi masalah secara signifikan, beberapa algoritma pemasangan acak berulang cenderung memberi Anda angka yang cukup tinggi . Perasaan saya jika ini adalah tugas adalah bahwa mereka tidak mencari jawaban yang benar , mereka mencari pendekatan kreatif.
MappingTomorrow

Jawaban:

22

Ada banyak cara untuk mendekati masalah ini. Format data raster menunjukkan pendekatan berbasis raster; dalam mengkaji pendekatan-pendekatan tersebut, rumusan masalah sebagai program linear bilangan bulat biner tampak menjanjikan, karena sangat sesuai dengan semangat banyak analisis pemilihan lokasi GIS dan dapat dengan mudah disesuaikan dengannya.

Dalam formulasi ini, kami menyebutkan semua posisi dan orientasi yang mungkin dari poligon isian, yang saya sebut sebagai "ubin". Terkait dengan setiap ubin adalah ukuran "kebaikannya." Tujuannya adalah untuk menemukan koleksi ubin yang tidak tumpang tindih yang total kebaikannya sebesar mungkin. Di sini, kita dapat mengambil kebaikan setiap ubin menjadi area yang dicakupnya. (Dalam lingkungan keputusan yang lebih kaya data dan canggih, kami dapat menghitung kebaikan sebagai kombinasi sifat sel yang termasuk dalam setiap ubin, properti yang mungkin terkait dengan visibilitas, kedekatan dengan hal-hal lain, dan sebagainya.)

Kendala pada masalah ini hanya karena tidak ada dua ubin dalam solusi yang tumpang tindih.

Hal ini dapat dibingkai sedikit lebih abstrak, dengan cara kondusif untuk perhitungan efisien, dengan enumerasi sel-sel dalam poligon yang akan diisi ( "daerah") 1, 2, ..., M . Setiap penempatan ubin dapat dikodekan dengan vektor indikator nol dan yang, membiarkan yang sesuai dengan sel-sel yang dicakup oleh ubin dan nol di tempat lain. Dalam pengkodean ini, semua informasi yang diperlukan tentang koleksi ubin dapat ditemukan dengan menjumlahkan vektor indikator mereka (komponen dengan komponen, seperti biasa): jumlahnya akan nol di mana setidaknya satu ubin menutupi sel dan jumlahnya akan lebih besar dari satu tempat dua atau lebih ubin tumpang tindih. (Jumlahnya secara efektif menghitung jumlah yang tumpang tindih.)

Satu abstraksi yang lebih sedikit: himpunan kemungkinan penempatan ubin sendiri bisa disebutkan, mengatakan 1, 2, ..., N . Pemilihan setiap set penempatan ubin itu sendiri sesuai dengan vektor indikator di mana yang menentukan ubin yang akan ditempatkan.

Berikut ilustrasi kecil untuk memperbaiki ide . Itu disertai dengan kode Mathematica yang digunakan untuk melakukan perhitungan, sehingga kesulitan pemrograman (atau ketiadaan) dapat menjadi jelas.

Pertama, kami menggambarkan daerah yang akan diberi ubin:

region =  {{0, 0, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}};

Gambar 1: wilayah

Jika kita beri nomor selnya dari kiri ke kanan, mulai dari atas, vektor indikator untuk wilayah ini memiliki 16 entri:

Flatten[region]

{0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

Mari kita gunakan ubin berikut, bersama dengan semua rotasi dengan kelipatan 90 derajat:

tileSet = {{{1, 1}, {1, 0}}};

Gambar 2: ubin

Kode untuk menghasilkan rotasi (dan refleksi):

apply[s_List, alpha] := Reverse /@ s;
apply[s_List, beta] := Transpose[s];
apply[s_List, g_List] := Fold[apply, s, g];
group = FoldList[Append, {}, Riffle[ConstantArray[alpha, 4], beta]];
tiles = Union[Flatten[Outer[apply[#1, #2] &, tileSet, group, 1], 1]];

(Komputasi yang agak buram ini dijelaskan dalam balasan di /math//a/159159 , yang menunjukkannya hanya menghasilkan semua kemungkinan rotasi dan pantulan ubin dan kemudian menghapus hasil duplikat apa pun.)

Misalkan kita menempatkan ubin seperti yang ditunjukkan di sini:

Gambar 3: penempatan ubin

Sel 3, 6, dan 7 tercakup dalam penempatan ini. Itu ditunjuk oleh vektor indikator

{0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

Jika kita menggeser ubin ini satu kolom ke kanan, vektor indikator itu akan menjadi

{0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}

Kombinasi mencoba menempatkan ubin di kedua posisi ini secara bersamaan ditentukan oleh jumlah indikator ini,

{0, 0, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}

Angka 2 di posisi ketujuh menunjukkan tumpang tindih ini dalam satu sel (baris kedua ke bawah, kolom ketiga dari kiri). Karena kami tidak ingin tumpang tindih, kami akan mensyaratkan bahwa jumlah vektor dalam setiap solusi yang valid harus tidak memiliki entri melebihi 1.

Ternyata untuk masalah ini, 29 kombinasi orientasi dan posisi dimungkinkan untuk ubin. (Ini ditemukan dengan sedikit pengkodean yang melibatkan pencarian lengkap.) Kami dapat menggambarkan semua 29 kemungkinan dengan menggambar indikator mereka sebagai vektor kolom . (Menggunakan kolom alih-alih baris adalah konvensional.) Berikut adalah gambar array yang dihasilkan, yang akan memiliki 16 baris (satu untuk setiap sel yang mungkin dalam persegi panjang) dan 29 kolom:

makeAllTiles[tile_, {n_Integer, m_Integer}] := 
  With[{ m0 = Length[tile], n0 = Length[First[tile]]},
   Flatten[
    Table[ArrayPad[tile, {{i, m - m0 - i}, {j, n - n0 - j}}],  {i, 0, m - m0}, {j, 0, n - n0}], 1]];
allTiles = Flatten[ParallelMap[makeAllTiles[#, ImageDimensions[regionImage]] & , tiles], 1];
allTiles = Parallelize[
   Select[allTiles, (regionVector . Flatten[#]) >= (Plus @@ (Flatten[#])) &]];
options = Transpose[Flatten /@ allTiles];

Gambar 4: array opsi

(Dua vektor indikator sebelumnya muncul sebagai dua kolom pertama di sebelah kiri.) Pembaca yang bermata tajam mungkin telah memperhatikan beberapa peluang untuk pemrosesan paralel: perhitungan ini dapat memakan waktu beberapa detik.

Semua hal di atas dapat disajikan kembali secara ringkas menggunakan notasi matriks:

  • F adalah array opsi ini, dengan M rows dan N kolom.

  • X adalah indikator dari serangkaian penempatan genteng, panjang N .

  • b adalah vektor- N yang.

  • R adalah indikator untuk wilayah tersebut; ini adalah M- vektor.

Total "kebaikan" yang terkait dengan solusi X yang mungkin , sama dengan RFX , karena FX adalah indikator sel yang dicakup oleh X dan produk dengan R menjumlahkan nilai-nilai ini. (Kita dapat mempertimbangkan R jika kita menginginkan solusi untuk mendukung atau menghindari area tertentu di wilayah ini.) Ini harus dimaksimalkan. Karena kita bisa menuliskannya sebagai ( RF ). X , ini adalah fungsi linier X : ini penting. (Dalam kode di bawah ini, variabel cberisi RF .)

Kendalanya adalah itu

  1. Semua elemen X harus non-negatif;

  2. Semua elemen X harus kurang dari 1 (yang merupakan entri yang sesuai dalam b );

  3. Semua elemen X harus integral.

Batasan (1) dan (2) menjadikan ini program linier , sedangkan persyaratan ketiga mengubahnya menjadi program linier bilangan bulat .

Ada banyak paket untuk menyelesaikan program linier integer yang diekspresikan dengan tepat dalam formulir ini. Mereka mampu menangani nilai-nilai M dan N menjadi puluhan atau bahkan ratusan ribu. Itu mungkin cukup baik untuk beberapa aplikasi di dunia nyata.


Sebagai ilustrasi pertama kami, saya menghitung solusi untuk contoh sebelumnya menggunakan perintah Mathematica 8 LinearProgramming. (Ini akan meminimalkan fungsi objektif linier. Minimalisasi dengan mudah diubah menjadi maksimalisasi dengan meniadakan fungsi objektif.) Ini mengembalikan solusi (sebagai daftar ubin dan posisi mereka) dalam 0,011 detik:

b = ConstantArray[-1, Length[options]];
c = -Flatten[region].options;
lu = ConstantArray[{0, 1}, Length[First[options]]];
x = LinearProgramming[c, -options, b, lu, Integers, Tolerance -> 0.05];
If[! ListQ[x] || Max[options.x] > 1, x = {}];
solution = allTiles[[Select[x Range[Length[x]], # > 0 &]]];

Gambar 5: solusi

Sel abu-abu sama sekali tidak berada di wilayah tersebut; sel-sel putih tidak tercakup oleh solusi ini.

Anda dapat mengerjakan (dengan tangan) banyak tilings lain yang sama baiknya dengan yang satu ini - tetapi Anda tidak dapat menemukan yang lebih baik. Itulah batasan potensial dari pendekatan ini: itu memberi Anda satu solusi terbaik, bahkan ketika ada lebih dari satu. (Ada beberapa solusi: jika kita menyusun ulang kolom X , masalahnya tetap tidak berubah, tetapi hasilnya perangkat lunak sering memilih solusi yang berbeda. Namun, perilaku ini tidak dapat diprediksi.)

Sebagai ilustrasi kedua , agar lebih realistis, mari kita pertimbangkan wilayah dalam pertanyaan. Dengan mengimpor gambar dan meng-resampling, saya mewakilinya dengan grid 69 kali 81:

Gambar 6: Wilayah

Wilayah ini terdiri dari 2156 sel dari kisi ini.

Untuk membuat hal-hal menarik, dan untuk menggambarkan generalisasi dari pengaturan pemrograman linier, mari kita coba untuk mencakup sebanyak mungkin wilayah ini dengan dua jenis persegi panjang:

Gambar 7: ubin

Satu adalah 17 dengan 9 (153 sel) dan yang lainnya adalah 15 oleh 11 (165 sel). Kita mungkin lebih suka menggunakan yang kedua, karena lebih besar, tetapi yang pertama lebih kurus dan bisa muat di tempat yang lebih sempit. Ayo lihat!

Program sekarang melibatkan N = 5589 kemungkinan penempatan ubin. Itu cukup besar! Setelah 6,3 detik perhitungan, Mathematica datang dengan solusi sepuluh ubin ini:

Gambar 8: solusi

Karena beberapa slack ( .eg, kita dapat menggeser ubin kiri bawah hingga empat kolom ke kiri), jelas ada beberapa solusi lain yang sedikit berbeda dari yang ini.

whuber
sumber
1
Versi sebelumnya dari solusi ini (tetapi tidak sebagus) muncul di situs Mathematica di Mathematica.stackexchange.com/a/6888 . Mungkin perlu dicatat juga, bahwa variasi kecil dari formulasi dapat digunakan untuk menyelesaikan masalah yang meliputi seluruh wilayah dengan sesedikit mungkin ubin (memungkinkan beberapa tumpang tindih, tentu saja): ini akan menyelesaikan "penambalan lubang" masalah.
Whuber
1
Demi kepentingan ruang, jawaban ini tidak menjelaskan beberapa perbaikan yang berpotensi membantu. Misalnya, setelah menemukan semua posisi ubin yang mungkin (sebagai vektor indikator), Anda dapat menambahkan semuanya untuk menemukan sel mana yang sebenarnya dapat dicakup oleh beberapa ubin. Himpunan sel-sel tersebut dibagi menjadi dua komponen yang terhubung terpisah dalam contoh kedua. Ini berarti masalah dapat diselesaikan secara independen dalam dua komponen, secara substansial mengurangi ukurannya (dan karenanya menghitung waktu). Penyederhanaan awal semacam itu cenderung penting untuk mengatasi masalah dunia nyata.
whuber
Usaha dan jawaban yang bagus. Jawaban Chris juga membantu. Terima kasih semuanya atas bantuannya! Bekerja, dan membuat saya bergerak ke arah yang benar lagi.
Thad
Wow! Saya tertarik pada masalah yang sama dan posting ini memberi saya perspektif baru. Terima kasih. Bagaimana jika R lebih besar (mis. 140x140≈20000), apakah ada cara untuk mengurangi biaya perhitungan? Apakah Anda tahu ada makalah yang terkait dengan masalah ini? Kata kunci pencarian saya tidak menuntun saya dengan cara yang benar (sampai sekarang).
nimcap
@nimcap Ini adalah kelas masalah yang penting, begitu banyak penelitian berlangsung. Kata kunci untuk pencarian akan dimulai dengan "program linear integer campuran" dan keluar dari sana berdasarkan apa yang Anda temukan.
whuber
5

Tautan ke Algoritma Genetika untuk Pengemasan Poligon , disediakan dalam jawaban saya untuk pertanyaan serupa di Mencari algoritma untuk menempatkan jumlah maksimum poin dalam area terbatas pada jarak minimum? , semoga bermanfaat. Sepertinya metode ini dapat digeneralisasi untuk bekerja dengan bentuk wadah yang sewenang-wenang (dan bukan hanya persegi panjang).

Kirk Kuykendall
sumber
Makalah itu memiliki beberapa ide bagus (+1), tetapi semua algoritmanya fokus, secara mendasar, pada pengemasan poligon dalam wilayah persegi panjang . Ini karena ini merepresentasikan pengepakan dengan struktur data diskrit (urutan poligon beserta orientasinya) yang mewakili sekumpulan prosedur di mana poligon digeser , sejajar dengan sisi bujur sangkar, menuju sudut yang ditentukan. Tampaknya pengkodean diskrit sederhana seperti itu akan kurang efektif untuk daerah yang lebih rumit. Mungkin penyederhanaan awal dari daerah di grid akan membantu.
whuber
2

Untuk subset sangat dibatasi yang Anda sebutkan (ubin persegi / segitiga di lubang), dengan asumsi optimasi eksplisit di atas, kodesemu ini harus sampai pada jawaban perkiraan dengan hanya membawa Anda melalui kemungkinan dengan resolusi tinggi, kasar memaksa masalah. Ini tidak akan berfungsi dengan benar untuk situasi di mana rotasi ubin individu dapat melihat keuntungan, seperti ubin persegi panjang atau wadah yang sangat tidak teratur. Ini adalah 1 juta iterasi, Anda dapat mencoba lebih banyak jika perlu.

Asumsikan sebuah persegi dengan sisi panjang L

Buat pola kotak-kotak kotak, yang setidaknya dari dimensi luasnya wadah, ditambah setidaknya 1L di setiap arah.

N = 0

DX = 0

DY = 0

DR = 0

Atur ulang posisi kotak-kotak ke centroid asli

Untuk (R = 1: 100)

Untuk (Y = 1: 100)

Untuk (X = 1: 100)

M = Hitung jumlah kotak sepenuhnya dalam wadah

Jika (M> N)

DR = R

DY = Y

DX = X

N = M

Pindahkan kotak-kotak timur dengan L / 100

Atur ulang arah timur kotak-kotak

Pindahkan kotak-kotak utara dengan L / 100

Setel ulang arah utara kotak-kotak

Putar kotak-kotak dengan 3,6 derajat CW di sekitar pusatnya

DY = DY * L

DX = DX * L

Atur ulang kotak-kotak ke posisi semula dan rotasi

Cetak DR & "," & DX & ", dan" & DY & "adalah terjemahan final / rotasi matriks"

Putar kotak-kotak oleh DR

Terjemahkan kotak-kotak oleh DX, DY

Pilih kotak yang sepenuhnya dalam wadah

Kotak ekspor

Memetakan Besok
sumber
Jika Anda mencoba prosedur ini pada daerah 2 dengan 5 dengan sel yang hilang di tengah-tengah satu sisi panjang, Anda akan menemukan Anda hanya dapat menempatkan satu 2 dengan 2 persegi ke dalamnya. Namun, dua kotak seperti itu mudah pas. Masalahnya adalah mereka bukan bagian dari pola "kotak-kotak" biasa. Kesulitan ini adalah salah satu hal yang membuat masalah ini cukup sulit.
whuber
1
Ya. Jika Anda memiliki bentuk wadah yang tidak teratur sehingga dapat mendukung beberapa pola reguler yang tidak sama pada beberapa sel masing-masing, ini berakhir sangat jauh dari optimal. Menambahkan hal-hal seperti itu ke ruang kemungkinan meningkatkan waktu pemrosesan dengan sangat cepat, dan memerlukan tingkat perencanaan tertentu untuk kasus tertentu yang Anda targetkan.
Pemetaan Besok