Posizionare rettangoli sovrapposti non casuali su un pannello

Question

Ho un gruppo di dimensioni X di Y. Voglio inserire fino a N rettangoli, di dimensioni in modo casuale, su questo pannello, ma non voglio che nessuno di loro a sovrapporsi. Ho bisogno di sapere la X, Y per le posizioni di questi rettangoli.

Algoritmo, chiunque?

Modifica : Tutti i rettangoli N sono noti, in via preliminare e possono essere selezionati in qualsiasi ordine. Questo cambia la procedura?

Answer 1

È possibile modellare questo da una serie di rettangoli "libere", a cominciare da sola con le coordinate di 0,0, dimensioni (x, y). Ogni volta che avete bisogno di aggiungere più un rettangolo, scegliere una delle restanti rettangoli "liberi", generare nuovo rettangolo (con alto a sinistra coordinare e dimensioni tali che sarà completamente contenuto), e dividere quel rettangolo così come qualsiasi altra sovrapposizione " libero" rettangolo, in modo tale che i bambini esprimono spazio libero rimanente. Questo si tradurrà in 0 a 4 nuovi rettangoli (0 se nuovo rettangolo era esattamente la dimensione del vecchio rettangolo libero; 4 se è nel mezzo e così via). Nel corso del tempo si otterrà aree sempre più sempre più piccole liberi, in modo da rettangoli si crea sarà più piccola pure.

Ok, non è una spiegazione molto elaborato, è più facile da mostrare sulla lavagna. Ma il modello è quello che ho usato per la ricerca di luogo di partenza per i componenti GUI incollate nuova Cut'n; è facile tenere traccia dei pezzi disponibili di schermo e scegliere (per esempio) di sinistra o più in alto di queste aree.

Answer 2

Ecco un articolo decente su algoritmi di imballaggio 2d: http://www.devx.com/ dotnet / articolo / 36005

In genere vorrà un qualche tipo di algoritmo usando euristiche per ottenere risultati decenti. Una soluzione semplice (ma non ottimale) sarebbe il primo algoritmo di misura.

Answer 3

Ho usato questo algoritmo Rettangolo Imballaggio in una delle mie applicazioni, disponibili come file sorgenti C #.

L'algoritmo viene inizializzato con le dimensioni del pannello, quindi eseguire iterazioni attraverso tutti i rettangoli e ottenere la loro posizione. L'ordine dei rettangoli può influenzare il risultato, a seconda del packer.

Answer 4

Vi consiglio di usare StaxMans suggerimento.

Ecco la mia 2c:

Aggiungere un sacco di rettangoli in modo casuale (si sovrappongono l'un l'altro). eliminare rettangoli sovrapposti:

for rectangle in list of rectangles:
    if rectangle not deleted:
        delete all rectangles touching rectangle.

per trovare tutti i rettangoli che toccano una particolare rettangolo, è possibile utilizzare un albero quad o disuguaglianze sulla base di x1, y1 x2, valori Y2.

Modifica:. In realtà, la maggior parte dei motori di gioco come ad esempio Pygame ecc includono rilevamento delle collisioni di rettangoli, che è un problema comune

Answer 5

o mantenere una lista di rettangoli già aggiunto e creare un algoritmo che calcola fuori dove posizionare il nuovo rettangolo sulla base di tale lista. È possibile creare una classe Rectangle base per contenere le informazioni sui tuoi rettangoli.

Non dovrebbe essere così difficile creare un algoritmo personalizzato.