Fusione e scissione sovrapposti rettangoli di produrre quelle non sovrapposti

Question

Sto cercando un algoritmo come segue:

Dato un insieme di rettangoli eventualmente sovrapposti (che sono tutti "non ruotato", possono essere rappresentati uniformemente (, top, destro e inferiore) tuplets sinistra, ecc ...), esso restituisce un insieme minimo di (non -rotated) non sovrapposte rettangoli, che occupano la stessa area.

Sembra abbastanza semplice a prima vista, ma che provano ad essere difficile (almeno per essere fatto in modo efficiente).

Ci sono alcuni metodi noti per questa / idee / puntatori?

Metodi per non necessariamente minimale, ma heuristicly piccolo, insiemi, sono interessanti e, in modo sono metodi che producono qualsiasi insieme uscita valido affatto.

Answer 1

qualcosa sulla base di un algoritmo di line-spazzata avrebbe funzionato, penso:

• Ordina tutti i rettangoli min e max x coordinate in un array, come "start-rettangolo" e "end-rettangolo di" eventi
• Passaggio attraverso l'array, aggiungendo ogni nuovo rettangolo incontrato (evento di avvio) in un insieme corrente
• Allo stesso tempo, mantenere un insieme di "rettangoli non sovrapposti" che saranno il set di uscita
• Ogni volta che si incontra un nuovo rettangolo è possibile verificare se è completamente contenuta già nel set di uscita / corrente (semplici confronti di y coordinate sarà sufficiente)
• Se non lo è, aggiungere un nuovo rettangolo per il set di uscita, con y coordinate impostate la parte del nuovo rettangolo che non sia già coperto.
• Ogni volta che si preme un rettangolo di fine evento, fermare eventuali rettangoli nel tuo set di uscita che non coprire più nulla.

Io non sono del tutto sicuro che questo copre tutto, ma credo che con qualche ritocco dovrebbe ottenere il lavoro fatto. O almeno dare qualche idea ...:)

Answer 2

Quindi, se stessi cercando di fare questo, la prima cosa che farei è venire con uno spazio di rete unificato. Trova tutti x unici e le coordinate Y, e creare una mappatura di uno spazio di indice. Quindi, se avete x valori {-1, 1.5, 3.1} quindi mappare quelli a {0, 1, 2}, e allo stesso modo per la y. Allora ogni rettangolo può essere esattamente rappresentato con queste coordinate imballato interi.

Poi mi piacerebbe assegnare un Bitvector o qualcosa che copre l'intera griglia, e rasterizzare i vostri rettangoli nella griglia. La cosa bella di avere una griglia è che è molto facile da lavorare, e limitando al x unico e coordinate y è minimale e precisa.

Un modo per venire con una soluzione piuttosto veloce è solo il dump ogni 'pixel' della griglia .. eseguirli indietro attraverso la mappatura, e il gioco è fatto. Se siete alla ricerca di un numero più ottimale di rettangoli, allora hai qualche tipo di problema di ricerca sulle vostre mani.

Diamo un'occhiata a 4 pixel adiacenti, una piccola piazza 2x2. Quando scrivo algoritmi come questi, tipicamente Credo in termini di verts, bordi e facce. Quindi, queste sono le facce intorno a vert. Se 3 di loro sono e 1 è spento, allora hai un angolo concavo. Questo è il caso unico valido. Per esempio, se non ho tutti gli angoli concavi, ho appena afferrare l'estensione e scaricare il tutto come un singolo rettangolo. Per ogni angolo concavo, è necessario decidere se dividere orizzontalmente, verticalmente o in entrambi. Credo che della scissione la marcatura bordi non attraversare quando trovare estensioni. Si potrebbe anche fare come la colorazione in gruppi, qualunque sia più facile per voi.

Gli angoli concavi e le rispettive direzioni split sono il vostro spazio di ricerca .. è possibile utilizzare qualsiasi algoritmo di ottimizzazione vuoi. Branch / lavoro potrebbe legato bene. Scommetto che si potrebbe trovare una semplice euristica che si comporta bene (ad esempio, se c'è un altro angolo concavo direttamente di fronte quello che si sta valutando, sempre diviso in quella direzione. In caso contrario, spaccatura nella direzione più breve). Si può solo andare avidi. Oppure si può semplicemente dividere ogni concava vert in entrambe le direzioni, il che in genere vi darà un numero inferiore di rettangoli di emissione di ogni 'pixel' come un rettangolo, e sarebbe piuttosto semplice.

La lettura su questo mi rendo conto che ci possono essere aree che non sono chiare. Fammi sapere se vuoi che chiarire nulla.