oggetto Positioning Algorithm

Question

sto chiedendo se esiste una soluzione "ottimale" per questo problema:

ho un n x m (pixel) Spazio dimensioni con p fosse già precedentemente rectangled - oggetti di varie dimensioni su di esso. Ora voglio posizionare q (stessi) nuovi oggetti in questo spazio senza sovrapposizioni.

L'algoritmo mi si avvicinò con:

1. Crea array A [] [] con la dimensione [(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

2. Iterate tutti gli elementi da p e per ogni:

   mark all fields in A[][] as occupied, where the element "lies"

3. Posiziona tutti gli elementi da q nei punti corrispondenti in cui i campi in A [] [] non sono contrassegnati

(Boy, Spero di poter fare quel comprensibile ...)

Esiste un modo migliore per fare questo? Qualsiasi aiuto sarebbe molto apprezzato!

Answer 1

Da una breve ricerca su Internet, sembra che l'imballaggio ottimale del rettangolo sia un problema NP-hard. Direi che le persone intelligenti nel mondo accademico hanno trovato alcuni algoritmi di approssimazione per questo, quindi è un'opzione per googling.

Ma vorrei provare a fare il lavoro semplice metodo di prima:

1. Divide gli oggetti in formati in base alla loro larghezza
2. Prova a mettere loro line-by-line dal più grande al più piccolo.

La mia ipotesi è che in molti casi questa soluzione ingenua funzionerà.

Answer 2

So che questa non è una risposta specifica alla tua domanda, ma potrebbe essere utile per ricercare e/o scavare nel codice sorgente graphviz. graphviz offre una serie di modelli di layout, incluso neato, che tenta di minimizzare una funzione energetica globale.

Wikipedia ha qualche pseudo-codice per force-base algorithms.

Answer 3

Se ho capito la domanda, sembra che tu stia cercando un algoritmo di "bin" ottimale per l'imballaggio (noto anche come Problema di Knapsack). Questo è un problema NP-Complete, anche se la tua descrizione sembra che tu possa probabilmente forzare la tua strada a una soluzione ottimale.