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

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 ansible, mi piacerebbe che fosse anche veloce, ma sono più interessato a ottenere il numero di rettangoli più basso ansible. 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ù ansible 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: inserisci la descrizione dell'immagine qui

Con questo set di tre rettangoli, la soluzione corretta finirebbe con due rettangoli, come questo: inserisci la descrizione dell'immagine qui

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.

Nonostante il titolo della tua domanda, penso che tu stia veramente cercando la dissezione minima in rettangoli di un poligono rettilineo. (I link di Jason riguardano le coperture minime da rettangoli, che è un problema abbastanza diverso.)

David Eppstein discute questo problema nella sezione 3 del suo articolo di sondaggio del 2010, le soluzioni teorico-grafiche ai problemi di geometria computazionale , e fornisce una bella sintesi in questa risposta su mathoverflow.net :

L’idea è di trovare il numero massimo di diagonali parallele asse-disgiunte che hanno due vertici concavi come punti finali, divisi lungo quelli, e quindi formare un’altra divisione per ciascun vertice concavo rimanente. Per trovare il numero massimo di diagonali parallele asse-disgiunto, formare il grafico di intersezione delle diagonali; questo grafico è bipartito quindi il suo set massimo indipendente può essere trovato in tempo polinomiale mediante tecniche di corrispondenza del grafico.

Ecco il mio gloss su questa descrizione ammirevolmente concisa, usando la figura 2 dell’articolo di Eppstein. Supponiamo di avere un poligono rettilineo, possibilmente con buchi.

Quando il poligono viene sezionato in rettangoli, ognuno dei vertici concavi deve essere raggiunto da almeno un bordo della dissezione. Quindi otteniamo la dissezione minima se il maggior numero ansible di questi bordi fa il doppio lavoro, cioè collegano due dei vertici concavi.

Disegniamo quindi le diagonali asse-parallelo tra due vertici concavi contenuti interamente all’interno del poligono. (“Asse-parallelo” significa “orizzontale o verticale” qui, e una diagonale di un poligono è una linea che collega due vertici non adiacenti.) Vogliamo utilizzare quante più di queste linee ansible nella dissezione fintanto che non indossano si intersecano.

(Se non ci sono diagonali parallele all’asse, la dissezione è banale, basta fare un taglio da ciascun vertice concavo, oppure se non ci sono intersezioni tra le diagonali parallele all’asse allora le usiamo tutte, più un taglio da ciascun vertice concavo rimanente Altrimenti, continua a leggere.)

Il grafico di intersezione di un insieme di segmenti di linea ha un nodo per ogni segmento di linea e uno spigolo unisce due nodes se le linee si incrociano. Ecco il grafico di intersezione per le diagonali parallele all’asse:

È bipartito con le diagonali verticali in una parte e le diagonali orizzontali nell’altra parte. Ora, vogliamo scegliere quante più diagonali ansible finché non si intersecano. Ciò corrisponde alla ricerca del massimo set indipendente nel grafico di intersezione.

Trovare il massimo set indipendente in un grafico generale è un problema NP-difficile, ma nel caso speciale di un grafico bipartito, il teorema di König mostra che è equivalente al problema di trovare un matching massimo, che può essere risolto in tempo polinomiale, per esempio dall’algoritmo di Hopcroft-Karp . Un dato grafico può avere diverse corrispondenze massime, ma ognuna di esse lo farà, in quanto tutte hanno le stesse dimensioni. Nell’esempio, tutte le corrispondenze massime hanno tre coppie di vertici, ad esempio {(2, 4), (6, 3), (7, 8)}:

(Altre corrispondenze massime in questo grafico includono {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)} e { (1, 3), (2, 4), (7, 8)}.)

Per ottenere da una corrispondenza massima alla copertura del vertice minimo corrispondente, applica la dimostrazione del teorema di König . Nell’accoppiamento mostrato sopra, il set di sinistra è L = {1, 2, 6, 7}, l’insieme di destra è R = {3, 4, 5, 8}, e l’insieme di vertici non accoppiati in L è U = { 1}. C’è solo un percorso alternato che inizia in U , cioè 1-3-6, quindi l’insieme di vertici in percorsi alternati è Z = {1, 3, 6} e la copertura del vertice minimo è quindi K = ( L \ Z ) ∪ ( RZ ) = {2, 3, 7}, mostrato in rosso sotto, con l’impostazione indipendente massima in verde:

Traducendo ciò nel problema della dissezione, questo significa che possiamo usare cinque diagonali parallele all’asse nella dissezione:

Infine, fai un taglio da ciascun vertice concavo rimanente per completare la dissezione:

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

Un algoritmo di approssimazione del tempo lineare per la copertura rettangular 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 qui per una bibliografia di più articoli su questo argomento.