Cercare un algoritmo non "forza bruta" per rimuovere le aree intersecanti di una raccolta di Rects

Question

Ho una raccolta di Rects di dimensioni n, la maggior parte delle quali si intersecano. Mi piacerebbe rimuovere le intersezioni e ridurre i Rects che si intersecano in rects non intersecanti più piccoli.

Potrei facilmente forzare una soluzione, ma sto cercando un algoritmo efficiente.

Ecco una visualizzazione:

originale:

Processed:

Idealmente la firma del metodo sarebbe simile a questa:

public static List<RectF> resolveIntersection(List<RectF> rects); 

l'uscita sarebbe maggiore o uguale all'ingresso, in cui l'uscita risolve la rappresentazione visiva di cui sopra.

Answer 1

questo è un problema che ho risolto in passato. La prima cosa è ordinare i rettangoli usando il valore x o y di uno dei bordi. Diciamo che ordinate nella direzione y e usate il bordo superiore. Il rettangolo più in alto nell'esempio è il primo in ordine. Per ogni rettangolo conosci la sua dimensione nella direzione y.

Ora, per ogni voce (chiamarla la voce corrente, corrisponde a un rettangolo) nell'elenco ordinato si ricerca in avanti attraverso l'elenco fino a raggiungere una voce superiore alla voce corrente + la dimensione del rettangolo corrispondente. (chiamalo la voce di arresto)

Qualsiasi voce nell'elenco ordinato tra la voce corrente e questa voce di arresto saranno potenziali intersezioni. Basta controllare se i rettangoli x-intervalli si intersecano.

Quando si sceglie di ordinare nella direzione x o y, sarà preferibile scegliere la dimensione più grande in quanto ciò implicherà meno intersezioni in media, quindi meno controllo.

Ecco un esempio. Rettangoli sono definiti come R (x1, x2, y1, y2) dove X1 è il lato sinistro, x2 è destra, y1 è alto e y2 è inferiore

rectangle 1 (1,5,0,4) 
rectangle 2 (7,9,6,8) 
rectangle 3 (2,4,2,3) 
rectangle 4 (3,6,3,7) 
rectangle 5 (3,6,9,15) 

ordinamento secondo y1 invia

#    y1 size 
rectangle 1  0 4 
rectangle 3  2 3 
rectangle 4  3 4 
rectangle 2  6 2 
rectangle 5  9 6 

quindi, il rettangolo 1 ha y1 + dimensione = 0 + 4 = 4 che implica intersecherà potenzialmente il rettangolo 3 (valore y1 = 3 < 4) e il rettangolo 4 (valore y1 = 3 < 4) ma non il rettangolo 2 (valore y1 = 6> 4) ... non è necessario controllare i rettangoli nell'elenco dopo 2

Rectangle 3 ha y2 + size = 2 + 3 = 5 che implica potrebbe intersecare il rettangolo 4 (valore y1 = 3 < 5) ma non ripetere 2 (valore y1 = 6> 5) non è necessario controllare i rettangoli nell'elenco dopo 2

Il rettangolo 4 ha y2 + size = 3 + 4 = 7 che implica che intersecherà potenzialmente il rettangolo 2 (valore y1 = 6 < 7) ma non si ripeterà 5 (valore y1 = 9> 7)

Naturalmente, con un numero elevato di rettangoli in genere dovrai solo controllare una frazione delle possibili coppie per l'intersezione.

Answer 2

quello che stai descrbing è il problema di imballaggio, hanno uno sguardo al wikipedia

si riferisce a this articolo che descrive un algoritmo per i rettangoli di imballaggio in rettangoli

questo è dall'articolo:

Questo articolo descrive un algoritmo veloce per imballare una serie di rettangoli di ampiezze e altezze variabili in un unico rettangolo che racchiude, senza sovrapposizione e in un modo che riduce al minimo la quantità di spazio sprecato nel rettangolo che lo racchiude .

Answer 3

Gli algoritmi di scorrimento consentono di elaborare intersezioni in universi 2D. Voglio dire prendere in considerazione una linea orizzontale che si sposta da un bordo del rettangolo al bordo del rettangolo successivo. La linea colpisce un numero di rettangoli, formando le cosiddette liste attive. L'elenco attivo viene aggiornato ad ogni mossa.

Studiando gli intervalli di ascisse lungo la linea orizzontale, è possibile rilevare le sovrapposizioni.

Un attento studio di tutte le configurazioni dovrebbe consentire di suddividere i rettangoli nel modo desiderato in un'unica scansione, con una complessità inferiore alla forza bruta (più vicino a N^1.5 che a N^2).