[algorithm] Algoritmo per trovare il minor numero di rettangoli per coprire un insieme di rettangoli senza sovrapposizioni



0 Answers

Ecco alcuni articoli accademici che discutono le soluzioni a questo problema;

Un algoritmo di approssimazione del tempo lineare per la copertura rettangolare minima (questo è per coprire i poligoni quindi è un caso più generale di quello che hai presentato qui).

Covers rettangolari ottimali per poligoni convessi rettilinei (questo è uno più lungo le linee del tuo problema specifico)

Puoi anche provare here per una bibliografia di più articoli su questo argomento.

Question

Ho una serie di rettangoli e vorrei "ridurre" il set in modo da avere il minor numero di rettangoli per descrivere la stessa area del set originale. Se possibile, mi piacerebbe che fosse anche veloce, ma sono più interessato a ottenere il numero di rettangoli più basso possibile. Ho un approccio ora che funziona la maggior parte del tempo.

Attualmente, comincio dal rettangolo in alto a sinistra e vedo se riesco ad espanderlo verso destra e verso il basso pur mantenendo un rettangolo. Lo faccio finché non è più possibile espandere, rimuovere e dividere tutti i rettangoli intersecanti e aggiungere il rettangolo espanso nuovamente nell'elenco. Quindi avvio di nuovo il processo con il prossimo rettangolo in alto a sinistra, e così via. Ma in alcuni casi, non funziona. Per esempio:

Con questo set di tre rettangoli, la soluzione corretta finirebbe con due rettangoli, come questo:

Tuttavia, in questo caso, il mio algoritmo inizia elaborando il rettangolo blu. Questo si espande verso il basso e divide il rettangolo giallo (correttamente). Ma quando il resto del rettangolo giallo viene elaborato, invece di espandersi verso il basso, si espande per primo a destra e riprende la parte precedentemente scissa. Quindi l'ultimo rettangolo viene elaborato e non può espandersi verso destra o verso il basso, quindi viene lasciato il set originale di rettangoli. Potevo modificare l'algoritmo per espanderlo prima e poi a destra. Ciò risolverebbe questo caso, ma causerebbe lo stesso problema in uno scenario simile che è stato capovolto.

Modifica: per chiarire, il set originale di rettangoli non si sovrappone e non è necessario connettersi. E se un sottoinsieme di rettangoli è connesso, il poligono che li copre completamente può avere dei buchi.




Related