Ho un problema di piastrellatura interessante, ho una grande immagine quadrata (dimensione 128k, quindi 131072 quadrati) con dimensoni 256x512 ... Voglio riempire questa immagine con certi tipi di grana (una tessera 1x1, una striscia 1x2, una striscia 2x1 e 2x2 quadrati) e non hanno sovrapposizione, nessun foro e nessuna estensione oltre il limite dell'immagine. Data una certa probabilità per ciascuno di questi tipi di granulosità, viene generato un elenco del numero richiesto da inserire.
Ovviamente un metodo iterativo / forza bruta non funziona bene qui se posizioniamo i pezzi solo in modo casuale, invece è richiesto un certo algoritmo. 1) tutti i grani quadrati 2x2 vengono posizionati casualmente fino all'esaurimento. 2) i grani 1x2 e 2x1 sono posizionati in modo casuale alternativamente fino all'esaurimento 3) le rimanenti tessere 1x1 sono posizionate per riempire tutti i buchi.
Si scopre che questo algoritmo funziona piuttosto bene per alcuni casi e non ha problemi a riempire l'intera immagine, tuttavia come puoi immaginare, aumentando la probabilità (e quindi il numero) di grani 1x2 e 2x1 alla fine il posizionamento si ferma (dal ci sono troppi buchi creati dalle strisce e non tutti possono essere posizionati).
Il mio approccio a questa soluzione è stato il seguente: 1) Creare una mini-immagine di dimensioni 8x8 o 16x16. 2) Riempi questa immagine in modo casuale e seguendo l'algoritmo sopra specificato in modo che la probabilità desiderata dell'intera immagine sia realizzata nella mini-immagine. 3) Crea N di queste mini-immagini e poi inseriscile casualmente nell'immagine grande.
Sfortunatamente ci sono alcuni inconvenienti a questa semplificazione. 1) data la piccola dimensione delle mini-immagini, inchiodare una probabilità esatta per l'intera immagine non è possibile. Esempio se voglio p (2x1) = P (1x2) = 0.4, la mini immagine può dare solo 0.41 come probabilità di chiusura. 2) Le mini-immagini creano uno pseudo confine in cui non si verificano sovrapposizioni che non sono realmente descrittive del modello per cui viene utilizzato. 3) C'è solo un numero fisso di mini-immagini quindi non sono sicuro di quanto questo sia realmente casuale.
In realtà sto solo pensando a possibili soluzioni per questo. La mia preoccupazione principale è davvero quella di inchiodare le probabilità più da vicino, ora si potrebbe suggerire di aumentare la dimensione delle mini-immagini. Bene, ho scoperto che in alcuni casi (p (1x2) = p (2x1) = 0.5) la mini-immagine 16x16 non è nemmeno risolvibile iterativamente .. Quindi è abbastanza ovvio quanto sia difficile risolverlo a caso per qualcosa di più grande di 8x8 dimensioni. Quindi mi piacerebbe sentire alcune idee. Grazie