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




language-agnostic geometry rectangles (3)

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.

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.


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 verrà raggiunto da un bordo della dissezione. Quindi otteniamo la dissezione minima se il maggior numero possibile di questi bordi fa il doppio lavoro, cioè collegano due dei vertici concavi.

Disegniamo quindi tutte le diagonali parallele all'asse tra due vertici concavi (una diagonale di un poligono è una linea che collega due vertici non adiacenti). Vogliamo utilizzare quante più linee possibili nella dissezione.

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

È bipartite con le diagonali verticali in una parte e le diagonali orizzontali nell'altra parte. Ora, vogliamo scegliere quante più diagonali possibile 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-completo, 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 . Ecco la corrispondenza massima:

E qui ci sono la copertura del vertice minimo corrispondente (rosso) e il set massimo indipendente (verde):

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

Infine, fai un taglio da ogni angolo concavo rimanente per completare la dissezione:


Vuoi sapere tutto quello che c'è da sapere sul grande O? Anche io.

Quindi, per parlare di O grande, userò parole che hanno solo un battito in loro. Un suono per parola. Le piccole parole sono veloci. Conoscete queste parole, e anch'io. Useremo le parole con un suono. Sono piccoli. Sono sicuro che conoscerai tutte le parole che useremo!

Ora, io e te parliamo del lavoro. Il più delle volte, non mi piace il lavoro. Ti piace il lavoro? Potrebbe essere il tuo caso, ma sono sicuro di no.

Non mi piace andare al lavoro. Non mi piace passare il tempo al lavoro. Se avessi la mia strada, mi piacerebbe solo giocare e fare cose divertenti. Ti senti lo stesso di me?

Ora, a volte, devo andare a lavorare. E 'triste ma vero. Quindi, quando sono al lavoro, ho una regola: cerco di fare meno lavoro. Il più vicino a nessun lavoro come posso. Poi vado a giocare!

Quindi ecco la grande novità: il grande O può aiutarmi a non lavorare! Posso suonare più volte, se conosco il grande O. Meno lavoro, più gioco! Questo è ciò che O grande mi aiuta a fare.

Ora ho del lavoro. Ho questa lista: uno, due, tre, quattro, cinque, sei. Devo aggiungere tutte le cose in questa lista.

Wow, odio il lavoro. Ma vabbè, devo farlo. Quindi eccomi.

Uno più due è tre ... più tre sei ... e quattro è ... Non lo so. Mi sono perso. È troppo difficile per me da fare nella mia testa. Non mi interessa molto questo tipo di lavoro.

Quindi non facciamo il lavoro. Lascia che tu e io pensiamo quanto sia difficile. Quanto lavoro dovrei fare per aggiungere sei numeri?

Bene vediamo.Devo aggiungere uno e due, e poi aggiungerlo a tre, e poi aggiungerlo a quattro ... Tutto sommato, conto sei aggiunte. Devo fare sei aggiunte per risolvere questo.

Ecco che arriva grande O, per dirci quanto sia dura questa matematica.

Big O dice: dobbiamo fare sei aggiunte per risolvere questo. Si aggiunge, per ogni cosa da uno a sei. Sei piccole parti di lavoro ... ogni pezzo di lavoro è una aggiunta.

Bene, non farò il lavoro per aggiungerli ora. Ma so quanto sarebbe difficile. Sarebbe sei aggiunge.

Oh no, ora ho più lavoro. Sheesh. Chi produce questo genere di cose ?!

Ora mi chiedono di aggiungere da uno a dieci! Perchè dovrei farlo? Non volevo aggiungerne uno a sei. Per aggiungere da uno a dieci ... beh ... sarebbe ancora più difficile!

Quanto più difficile sarebbe? Quanto altro lavoro dovrei fare? Ho bisogno di più o meno passaggi?

Beh, suppongo che dovrei fare dieci aggiunte ... una per ogni cosa da uno a dieci. Dieci ne ha più di sei. Dovrei lavorare molto di più per aggiungere da uno a dieci, da uno a sei!

Non voglio aggiungere adesso. Voglio solo pensare a quanto sia difficile aggiungere molto. E, spero, per giocare il prima possibile.

Per aggiungere da uno a sei, questo è un po 'di lavoro. Ma vedi, aggiungere da uno a dieci, è più lavoro?

Big O è tuo amico e mio. Big O ci aiuta a pensare a quanto lavoro dobbiamo fare, quindi possiamo pianificare. E, se siamo amici del grande O, può aiutarci a scegliere un lavoro che non sia così difficile!

Ora dobbiamo fare un nuovo lavoro. Oh, no. Non mi piace affatto questa cosa del lavoro.

Il nuovo lavoro è: aggiungi tutte le cose dall'una all'altra.

Aspettare!Cos'è n? Mi è mancato? Come posso aggiungere da uno a se non mi dici che cosa è?

Beh, non so cosa sia. Non mi è stato detto Eri tu? No? Oh bene. Quindi non possiamo fare il lavoro. Accidenti.

Ma anche se non lo faremo ora, possiamo indovinare quanto sarebbe difficile, se sapessimo n. Dovremmo aggiungere n cose, giusto? Ovviamente!

Ora arriva O grande, e ci dirà quanto sia duro questo lavoro. Dice: per aggiungere tutte le cose da uno a N, uno per uno, è O (n). Per aggiungere tutte queste cose, [so che devo aggiungere n volte.] [1] Questo è grande O! Ci dice quanto sia difficile fare un certo tipo di lavoro.

Per me, penso al grande O come un grande, lento, uomo capo. Pensa al lavoro, ma non lo fa. Potrebbe dire: "Quel lavoro è veloce". Oppure, potrebbe dire: "Quel lavoro è così lento e difficile!" Ma lui non fa il lavoro. Guarda solo il lavoro, e poi ci dice quanto tempo potrebbe volerci.

Mi importa un sacco di grandi O. Perché? Non mi piace lavorare! A nessuno piace lavorare. Questo è il motivo per cui tutti noi amiamo il grande O! Ci dice quanto velocemente possiamo lavorare. Ci aiuta a pensare a quanto sia duro il lavoro.

Uh oh, più lavoro. Ora, non facciamo il lavoro. Ma facciamo un piano per farlo, passo dopo passo.

Ci hanno dato un mazzo di dieci carte. Sono tutti mescolati: sette, quattro, due, sei ... non proprio per niente. E ora ... il nostro compito è di ordinarli.

Ergh. Sembra un sacco di lavoro!

Come possiamo ordinare questo mazzo? Ho un piano.

Guarderò ogni coppia di carte, coppia per coppia, attraverso il mazzo, dal primo all'ultimo. Se la prima carta in una coppia è grande e la carta successiva in quella coppia è piccola, le cambio. Altrimenti, vado alla prossima coppia, e così via e così via ... e presto, il mazzo è finito.

Quando il mazzo è finito, chiedo: ho scambiato le carte in quel passaggio? Se è così, devo fare tutto ancora una volta, dall'alto.

Ad un certo punto, a un certo punto, non ci saranno swap, e il nostro tipo di mazzo verrebbe fatto. Così tanto lavoro!

Bene, quanto lavoro sarebbe, per ordinare le carte con quelle regole?

Ho dieci carte. E, il più delle volte - cioè, se non ho molta fortuna - devo passare attraverso l'intero mazzo fino a dieci volte, con fino a dieci scambi di carte ogni volta attraverso il mazzo.

Big O, aiutami!

Big O entra e dice: per un mazzo di n carte, ordinarlo in questo modo sarà fatto in tempo O (N al quadrato).

Perché dice n quadrato?

Beh, sai n al quadrato è n volte n. Ora, ho capito: n carte controllate, fino a quello che potrebbe essere n volte attraverso il mazzo. Quello è due cicli, ciascuno con n passi. Questo è molto alquanto da fare. Un sacco di lavoro, di sicuro!

Ora, quando O grande dice che impiegherà il lavoro di O (n al quadrato), non significa n quadrati aggiunti, sul naso. Potrebbe essere un po 'meno, per alcuni casi. Ma nel peggiore dei casi, saranno quasi n al quadrato passi di lavoro per ordinare il mazzo.

Ora qui è dove il grande O è nostro amico.

Big O sottolinea questo: quando n diventa grande, quando ordiniamo le carte, il lavoro diventa MOLTO MOLTO PIÙ DURO rispetto al vecchio lavoro just-add-these-things. Come facciamo a saperlo?

Bene, se n diventa davvero grande, non ci importa cosa potremmo aggiungere a n o n al quadrato.

Per il grande n, n al quadrato è più grande di n.

Big O ci dice che ordinare le cose è più difficile che aggiungere cose. O (n al quadrato) è più di O (n) per il grande n. Ciò significa che se n diventa veramente grande, per ordinare un mazzo misto di n cose DEVE impiegare più tempo, piuttosto che aggiungere n cose miste.

Big O non risolve il lavoro per noi. Big O ci dice quanto sia duro il lavoro.

Ho un mazzo di carte. Li ho sistemati. Hai aiutato Grazie.

C'è un modo più veloce per ordinare le carte? Può grande O aiutaci?

Sì, c'è un modo più veloce! Ci vuole un po 'di tempo per imparare, ma funziona ... e funziona abbastanza velocemente. Puoi provarlo anche tu, ma prenditi il ​​tuo tempo ad ogni passo e non perdere il tuo posto.

In questo nuovo modo di ordinare un mazzo, non controlliamo coppie di carte nel modo in cui abbiamo fatto un po 'di tempo fa. Ecco le tue nuove regole per ordinare questo mazzo:

Uno: scelgo una carta nella parte del mazzo su cui lavoriamo ora. Puoi sceglierne uno per me, se ti va. (La prima volta che facciamo questo, "la parte del mazzo su cui lavoriamo ora" è l'intero mazzo, ovviamente.)

Due: spago il mazzo su quella carta che hai scelto. Cos'è questo splay? come faccio a splay? Bene, vado giù dalla carta iniziale, uno per uno, e cerco una carta più alta della carta splay.

Tre: vado dalla carta finale verso l'alto, e cerco una carta più bassa della carta splay.

Una volta che ho trovato queste due carte, le cambio e continuo a cercare altre carte da scambiare. Cioè, torno al secondo passaggio e splay sulla scheda che hai scelto ancora.

Ad un certo punto, questo ciclo (da due a tre) terminerà. Termina quando entrambe le metà di questa ricerca si incontrano nella scheda splay. Quindi, abbiamo appena allargato il mazzo con la carta che hai scelto al punto uno. Ora, tutte le carte vicino all'inizio sono più basse della carta splay; e le carte vicino alla fine sono più alte della carta splay. Fantastico trucco!

Quattro (e questa è la parte divertente): ora ho due mazzi piccoli, uno più basso della carta splay e uno più alto. Ora vado al primo passo, su ogni piccolo mazzo! Vale a dire, parto dal primo passaggio sul primo mazzo piccolo, e quando il lavoro è terminato, parto dal primo passaggio sul prossimo piccolo mazzo.

Rompendo il mazzo in parti e ordiniamo ogni parte, più piccola e più piccola, e a un certo momento non ho più lavoro da fare. Ora questo può sembrare lento, con tutte le regole. Ma credimi, non è affatto lento. È molto meno lavoro del primo modo di ordinare le cose!

Come si chiama questo tipo? Si chiama Quick Sort! Quel tipo è stato creato da un uomo chiamato CAR Hoare e lo ha chiamato Quick Sort. Ora, Quick Sort viene usato sempre!

Quick Sort suddivide grandi mazzi in piccoli. Vale a dire, rompe grandi compiti in quelli piccoli.

Hmmm.Potrebbe esserci una regola lì dentro, credo. Per rendere piccoli i compiti più grandi, suddividili.

Questo tipo è abbastanza veloce. Quanto veloce? Big O ci dice: questo genere ha bisogno del lavoro di O (n log n), nel caso medio.

È più o meno veloce del primo? Big O, per favore aiuto!

Il primo tipo era O (n al quadrato). Ma Quick Sort è O (n log n). Sai che n log n è minore di n al quadrato, per grande n, giusto? Bene, è così che sappiamo che Quick Sort è veloce!

Se devi ordinare un mazzo, qual è il modo migliore? Bene, puoi fare quello che vuoi, ma sceglierei Quick Sort.

Perché scelgo l'ordinamento rapido? Non mi piace lavorare, ovviamente! Voglio che il lavoro sia svolto non appena riesco a farlo.

Come faccio a sapere che l'ordinamento rapido è meno efficace? So che O (n log n) è minore di O (n al quadrato). Gli O sono più piccoli, quindi Quick Sort è meno lavoro!

Adesso conosci il mio amico, Big O. Ci aiuta a fare meno lavoro. E se conosci il grande O, puoi fare anche meno lavoro!

Hai imparato tutto questo con me! Sei così intelligente! Grazie mille!

Ora che il lavoro è finito, andiamo a giocare!

[1]: C'è un modo per imbrogliare e aggiungere tutte le cose dalla prima alla seconda, tutte in una volta. Qualche ragazzino di nome Gauss lo ha scoperto quando aveva otto anni. Non sono così intelligente, quindi non chiedermi come ha fatto .







algorithm language-agnostic geometry rectangles