minimizzazione della sovrapposizione in rettangoli casuali

Question

Ho un numero di rettangoli probabilmente sovrapposti, di dimensione e posizione casuali all'interno di un piano fisso. Poiché questi rettangoli sono casuali, alcuni non possono sovrapporsi:

 
|----- 
| | |----| 
|----| | | 
      |----| 

Alcuni possono sovrapporsi da un solo angolo:

 
|-----| 
| |--|--| 
|--|--| | 
    |-----| 

Alcuni possono essere contenute all'interno di un altro rettangolo:

 
|----------------| 
|    | 
| |-----|  | 
| |  |  | 
| |-----|  | 
|----------------| 

Alcuni possono passare attraverso un altro rettangolo:

 
    |----------------| 
    |    | 
|--|-------------------| 
| |    | | 
|--|-------------------| 
    |----------------| 

ecc.

Sto cercando un algoritmo che mi fornisca un insieme di rettangoli che rappresentano la stessa area dell'insieme di input, ma senza sovrapposizioni. Alcuni casi sono ovvi: i rettangoli contenuti in un rettangolo più grande possono essere scartati ei rettangoli che si sovrappongono in un angolo possono essere suddivisi in tre rettangoli, così come i rettangoli che passano attraverso un altro rettangolo. Quello che sto cercando, è un algoritmo generico che si occupa di tutti questi casi. Non mi interessa molto se non è brillantemente efficiente - il set di input è piuttosto piccolo (25 rettangoli al massimo)

Trovare i rettangoli che si sovrappongono è facile, ma diventa rapidamente più difficile da lì, specialmente se si considera che un rettangolo potrebbe sovrapporsi a più altri rettangoli.

Questo sta facendo la mia testa. Qualche suggerimento?

Aggiornamento:

Ho appena realizzato una cosa:

posso né eseguire questo algoritmo nel momento in cui i rettangoli vengono aggiunti tot mise, uno per uno, o dopo che tutti i rettangoli sono stati aggiunti. Potrebbe essere più facile farlo mentre i rettangoli vengono aggiunti, poiché è necessario considerare solo un rettangolo, ma è comunque necessario tenere conto della situazione in cui un singolo rettangolo si sovrappone a più altri rettangoli.

Answer 1

Sono i rettangoli paralleli agli assi y x &? Suppongo che lo siano.

Puoi provare a utilizzare KD-Trees.

Oppure, se si desidera qualcosa di homegrown e non necessariamente efficiente, è possibile "rettangolare" e quindi, se necessario, unire nuovamente i rettangoli.

Per "rettangolazione", intendo innanzitutto che si trova un rettangolo più grande in cui tutti i rettangoli si adattano (in pratica il rettangolo formato dal margine inferiore sinistro, lato destro con grossezza, bordo inferiore minimo, margine superiore maggiore).

Ora estendere tutti i bordi dei rettangoli per tagliare attraverso il rettangolo grande. Ora hai una 'rettangolazione'. Fondamentalmente tutto ciò significa che si ordinano i bordi verticali e i bordi orizzontali e si selezionano coppie adiacenti per formare un piccolo rettangolo. Per ogni piccolo rettangolo, ora puoi verificare se questo è parte dell'area interessante o no e rifiutarlo se non lo è (è pieno dentro o completamente fuori).

Ora hai una lista di piccoli rettangoli (possibilmente O (n^2), nel tuo caso forse ~ 2500) che costituiscono l'area di tuo interesse. Se il numero è sufficientemente piccolo per l'elaborazione futura, puoi semplicemente utilizzarli oppure puoi unirli insieme per ridurre il numero di rettangoli.

Per unire l'utente è possibile considerare un rettangolo e considerare 4 possibili per un'unione (rettangolo adiacente della stessa altezza a destra o a sinistra o rettangolo adiacente di stessa larghezza verso l'alto o il basso).

È possibile velocizzare l'elaborazione (non solo durante l'unione) mantenendo un elenco ordinato di spigoli (orizzontali e paralleli) e forse alcuni hashtable.

Answer 2

Prima creare l'insieme di tutti i rettangoli "atomici" nella composizione, cioè le aree formate dalle intersezioni del rettangolo e non essere suddivise esse stesse. Ogni rettangolo effettivo copre 1 o più rettangoli atomici. Quindi esegui un algoritmo di ottimizzazione combinatorio, ad es. SETCOVER per calcolare il numero minimo di rettangoli che è necessario per coprirli tutti.

Ecco un'illustrazione dell'approccio. Hai tre rettangoli (A, B, C). Essi creano 5 regioni atomiche (1-5):

+---------+A 
|  1 | 
| +----+-----+B 
| | 2 | 3 | 
| | +-+---+C| 
| | |4| | | 
+----+--+-+ 5 | | 
     | +-----+ | 
     +--+-------+ 

I rettangoli coprono le regioni atomiche secondo la seguente tabella:

A {1,2,4} 
B {2,3,4,5} 
C {4,5} 

Il problema SETCOVER è ora quello di selezionare un sottoinsieme minimo dei rettangoli { A, B, C} in modo che tutte le regioni atomiche siano coperte quando si uniscono le regioni atomiche coperte dai rettangoli. La soluzione minima è (ovviamente)

A {1,2,4} + B {2,3,4,5} = {1,2,3,4,5} 

Si noti che qui le aree non sono rettangolari, ad es. l'area 3 ha una forma complessa.Puoi liberarti di questo problema con il seguente approccio: prendi tutte le coordinate X distinte dei punti d'angolo dei rettangoli originali e considerali come X-coordinate di una griglia e fai la stessa cosa per le coordinate Y; poi ogni rettangolo si estende su una serie di quadrati della griglia che non sono mai suddivisa, cioè .:

+---------+A  - 
|  1 | 
| +----+-----+B - 
| | 2 | 3 | 
| | +-+---+C| - 
| | |4| | | 
+----+--+-+ 5 | | - 
     | +-----+ | - 
     +--+-------+ - 

| | | | | | 

che vi dà la seguente griglia 5x5:

AAA  A = rectangle A only 
A**BB B = rectangle B only 
A*#CB * = A and B 
    BCCB C = rectangles C and B 
    BBBB # = All 

Da questo si può facilmente estrarre le 5 regioni; infatti, sono già stati contrassegnati :) (A, B, C, *, #)

Answer 3

Se non si dispone già di una serie di rettangoli, è possibile accedervi dall'altra parte - iniziare con un rettangolo grande e suddividerlo fino a quando non si dispone di un set con cui si può lavorare - ciò garantisce che non vi siano sovrapposizioni.

Inizia con un intero rettangolo di

-------- 
|  | 
|  | 
|  | 
|  | 
|  | 
-------- 

Spalato in un punto casuale e memorizzare i due rettangoli.

-------- 
|  | 
|------| 
|  | 
|  | 
|  | 
-------- 

Split un rettangolo a caso in un punto casuale

-------- 
|  | 
|------| 
| | | 
| | | 
| | | 
-------- 

ripetizione. . .

-------- 
|  | 
|------| 
| | | 
| |----| 
| | | 
-------- 

Interrompi quando hai il numero richiesto di rettangoli.

Si potrebbe fare questo produrre il tipo di 'casualità' che si desidera, scegliendo con più attenzione il rettangolo che si sta per dividere ogni volta ETCC

Answer 4

Domanda molto interessante - Penso che sia meglio risolvere il problema una coppia di rettangoli alla volta anziché guardare 3 o più contemporaneamente. Inizia scartando quelli all'interno di altri rettangoli. Ora hai solo 3 tipi di intersezioni: l'angolo si sovrappone e passa attraverso la sovrapposizione e la sovrapposizione parziale (in cui il rettangolo non passa completamente). Ognuno di questi crea un nuovo set di rettangoli, giusto?

Numerare i rettangoli di partenza da 1 a N. Partendo dal rettangolo 1 ciclo fino a trovare un rettangolo intersecante. Crea nuovi rettangoli. Elimina i due rettangoli intersecanti e aggiungi i 3 o più rettangoli appena creati al set e ricomincia.

Il risultato sarà un intero gruppo di rettangoli non sovrapposti. Questo crea il minor numero di rettangoli? Probabilmente no, ma non hai specificato che la riduzione al minimo del numero di rettangoli era importante. Si sostituisce o (n^2) tempo? Probabilmente.

Answer 5

Se non si dispone di alcun vincolo sul numero di rettangoli che il proprio algoritmo dovrebbe produrre, si può sicuramente essere avventato nel trattamento!

1. soluzione più semplice mai

creare un insieme di tutti i quadrati di area (1) che sono coperti dai rettangoli del set di input. Un quadrato è un rettangolo ... eccoti!

2. Soluzione minimalista?

Ok, era un'eruzione, tuttavia non penso che dovresti preoccuparti del set di input. Il tuo problema è in realtà diverso:

Raccogli un'area contigua con una forma complessa e cerca di coprirla esattamente con i rettangoli, riducendo al minimo il loro numero e in modo che non si sovrappongano.

Naturalmente, la tua area potrebbe non essere contigua, ma significa semplicemente che hai diverse aree contigue su cui puoi lavorare indipendentemente.

Ora, ammetto che non conosco la soluzione migliore per questo problema, ci sono vari approcci che posso immaginare e non conosco le loro prestazioni o risultati. KD-Tree dovrebbe dare una soluzione, non so se è quella minimalista!