2009-11-25 5 views
6

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

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!

+0

Giusto per essere chiari, NON è possibile riposizionare oggetti esistenti, correggere? –

+0

Quali forme sono i "q nuovi oggetti di uguale grandezza"? Sono tutti rettangoli? Ti è permesso ruotarli? –

risposta

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à.

0

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.

1

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.