Dato molte linee orizzontali e verticali, come trovare tutti i rettangoli che contengono un sub-rettangolo al loro interno?

Question

Ho molte linee orizzontali e verticali che compongono il rettangolo come in questo esempio.

Esiste un algoritmo o un codice che può individuare ogni rettangolo che non contiene un altro rettangolo. Voglio dire, il rettangolo più grande in questa immagine non è un rettangolo che sto cercando perché contiene altri rettangoli all'interno di esso.

I rettangoli che sto cercando devono essere vuoti. Ho una lista dei punti iniziali e finali di ogni riga come (a, b) a (c, d). Voglio di conseguenza una lista di rettangoli (x, y, w, h) o equivalenti.

Si noti che alcune linee hanno linee che si intersecano ad angoli retti, ad esempio la linea superiore del rettangolo più largo in questa immagine è una linea singola ha una linea verticale che si interseca andando verso il basso.

Answer 1

Tutte le linee sono parallele all'asse xo y? O tutte le tue linee parallele o perpendicolari?

Dall'esempio che ho dato, suppongo che tutte le linee siano parallele all'asse x o y. In tal caso le tue linee saranno [(a, b), (a, d)] o [(a, b), (c, b)].

In ogni caso, il primo compito è trovare gli angoli. questo è un insieme di punti in cui due linee perpendicolari si incontrano.

Il secondo compito è rilevare i rettangoli. Per ogni coppia di angoli è possibile controllare se formano rettangoli.

Il terzo compito è quello di trovare se un rettangolo ha dei rettangoli all'interno di se stesso.

Per il primo compito, è necessario separare le linee in due gruppi: verticale e orizzontale. Dopo quella specie uno dei set. Ex. Ordina le linee verticali in base alle loro coordinate dell'asse x. Quindi puoi prendere tutte le linee orizzontali e fare una ricerca binaria per trovare tutti i punti di intersezione.

Per la seconda attività, considerare ogni coppia di angoli e verificare se esistono gli altri due angoli. Se sì, quindi vedere se ci sono linee per unire tutti questi quattro angoli. Se sì, hai un rettangolo.

Per la terza attività, inserire tutti i rettangoli in un albero ad intervalli. Dopodiché puoi verificare se due rettangoli si sovrappongono.

Answer 2

Penso che una diversa rappresentazione ti aiuterà a risolvere il tuo problema. Ad esempio, considera il rettangolo grande (senza il blocco alla fine). Ci sono quattro coordinate xey uniche, ordinali e indicizzali. Pittoricamente sarebbe simile a questa:

Se c'è un angolo di un rettangolo sulla coordinata (x_i, y_j) metterlo in una matrice in questo modo:

__|_1__2__3__4_ 
1 | x x 0 x 
2 | x x 0 0 
3 | 0 x x x 
4 | x x x x 

Ora, per definizione, un rettangolo in lo spazio reale è un rettangolo sulle coordinate della matrice. Ad esempio c'è un rettangolo allo (3,2) (3,4) (4,4), (4,3) ma non è un rettangolo "base" poiché contiene un sub-rettangolo (3,3) (3,4), (4,4), (4,3). Un algoritmo ricorsivo è facilmente visibile qui e per una maggiore velocità utilizza la memoizzazione per evitare calcoli ripetitivi.

Answer 3

A sweep-line algorithm ...

strutture richieste:

• V = Un insieme di linee verticali, filtrate per ascissa.

• H = Un insieme di tutti i punti di inizio e fine delle linee orizzontali (e ogni punto mantiene un riferimento alla linea) e ordinati per coordinate x.

• CH = Un (inizialmente vuoto) ordinato (per coordinata y) set di linee correnti.

• CR = Un insieme ordinato (per coordinata y) di rettangoli correnti. Questi rettangoli avranno coordinate sinistra, superiore e inferiore, ma non ancora coordinate giuste. Nota che non ci saranno sovrapposizioni in questo set.

Algoritmo:

Contemporaneamente processo V e H da sinistra a destra.

Ogni volta che viene rilevato un inizio della linea orizzontale, aggiungere la linea a CH.

Ogni volta che si incontra una estremità della linea orizzontale, rimuoverla da CH.

Quando viene rilevato un linea verticale:

• Eliminare dal CR tutti i rettangoli che si sovrappongono con la linea. Per tutto il rettangolo rimosso, se è completamente contenuto nella linea, confronta le sue dimensioni con il rettangolo migliore finora e memorizzalo se è migliore.

• Processo ciascun elemento in CH iterativamente tra il punto inferiore e il punto superiore della linea come segue:

  • Aggiungere un rettangolo a CR con l'ultimo punto elaborati come fondo, il punto corrente come superiore e la coordinata y della linea verticale come sinistra.

Done.

Nota:

Quando la coordinata x di punti di inizio orizzontali o punti finali o linee verticali sono uguali seguente ordine deve essere mantenuta:

x of horizontal start < x of vertical line < x of horizontal finish 

Altrimenti ti mancherà rettangoli.

Answer 4

Questo tipo di domande viene ampiamente risolto da alcuni algoritmi standard Computational Geometry. Posso pensare ad un algoritmo vertical sweep line per questo particolare problema.

Supponendo che un rettangolo sia rappresentato da una coppia di punti (p1, p2), dove p1 è nell'angolo in alto a sinistra e p2 è nell'angolo in basso a destra. E un punto ha due attributi (è possibile accedere come p.x e p.y).

Ecco l'algoritmo.

1. ordinare tutte le coppie di punti - O(n log n)
2. inizializzare un elenco chiamato sweep line status. Ciò manterrà tutti i rettangoli che si incontrano fino ad ora, ovvero alive. Inizializza anche un altro elenco chiamato event queue che contiene eventi imminenti. Questo event queue attualmente detiene i punti di partenza di tutti i rettangoli.
3. Elaborare gli eventi, iniziare dal primo elemento nello event queue.
   • Se l'evento è un start point, quindi aggiungere tale rettangolo sweep line status (in modo ordinato da coordinata y) (in O(log n) tempo) e aggiungere il punto in basso a destra della event queue nella posizione appropriata (filtrate per punti) (sempre nel tempo O(log n)). Quando lo aggiungi a sweep line status, devi solo verificare se questo punto si trova nel rettangolo vivo sopra di esso nello sweep line status. Se si trova all'interno, questo non è il tuo rettangolo, altrimenti aggiungilo alla lista dei rettangoli richiesti.
   • Se l'evento è un punto finale, rimuovere il rettangolo di correspoinding dallo sweep line status.

tempo (per n rettangoli) Esecuzione:

• Ordinamento prende O(n log n).
• Numero di eventi = 2 * n = O(n)
• Ogni evento si O(log n) tempo (per inserimenti in event queue nonché sweep line status. Così totale è O(n log n).

Pertanto, O(n log n).

Per maggiori dettagli, si prega di fare riferimento a Bentley–Ottmann algorithm. Quanto sopra solo una semplice modifica di questo

MODIFICA:

Appena realizzato quell'input è in termini di segmenti di linea, ma poiché formano sempre rettangoli (secondo la domanda), un attraversamento lineare per un pre-processo può convertirli nella forma di rettangolo (coppia di punti).