Come disegnare rettangoli per array 2D

3

Ho un array booleano 2D simile a questo:

[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]

(0 = falso, 1 = vero)

Ho trovato un modo per combinare gli zeri adiacenti sul piano orizzontale come:

[----------------------------]
[----------------------------]
[----------------------------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[----------------------------]
[----------------------------]

Il codice per raggiungere questo è come tale:

for y = 0 to ySize
    for x = 0 to xSize
        if array[y][x] = 0
            set width = 1

            for x2 = x + 1 to xSize
                if array[y][x2] = 0
                    width++
                else
                    break

            add object at x, y and set width to width
            set x = x + width - 1

Quindi esegue il loop dell'array 2D alla ricerca di zeri e, se ne trova uno, esegue il loop fino alla fine della riga per trovare dove non è più uno zero.

Quindi crea un oggetto nella posizione in cui ha prima trovato uno zero e lo allunga per riempire la parte finché non è uno zero.

Voglio adattare questo codice per creare rettangoli invece di tavole lunghe, come:

 ____________________________
|                            |
|                            |   <------ rect at 0, 0 with size (10, 3)
|____________________________|
|       |[1][1][1]|          |
|       |[1][1][1]|          |
|       |[1][1][1]|          |   <------ rect at 6, 3 with size (4, 5)
|       |[1][1][1]|          |
|       |[1][1][1]|__________|
|       |                    |
|_______|____________________|   <------ rect at 3, 8 with size (7, 2)

   ^
   |
   |
  rect at 0, 3 with size (3, 7)

Quindi, invece di creare 15 assi orizzontali, crea 4 rettangoli che circondano quelli.

In breve, voglio creare un algoritmo che, quando viene fornito un array 2D di uni e zeri, crei rettangoli attorno a quelli.

Per un esempio più piccolo:

             {
[0][0][0]         { 0, 0, 0 },
[0][1][0]         { 0, 1, 0 },
[0][0][0]         { 0, 0, 0 }
             }

Restituisce la posizione e la dimensione dei rettangoli come:

[-------]  
[-][1][-]
[-------]

{
    {0, 0, 3, 1}, //rect at (0, 0) with width 3, height 1
    {0, 1, 1, 1}, //rect at (0, 1) with width 1, height 1
    {2, 1, 1, 1}, //rect at (2, 1) with width 1, height 1
    {0, 2, 3, 1}  //rect at (0, 2) with width 3, height 1
}

Che aspetto dovrebbe avere questo algoritmo?

Modifica: ci dovrebbe essere un certo sforzo per minimizzare il numero di rettangoli usati (altrimenti, potrebbe semplicemente lasciarlo così com'è).

Inoltre, non importa se preferisce i rettangoli orizzontali o verticali. Esempio:

[-------]
[-][1][-]
[-------]

è uguale a

 _     _
| |[ ]| |
| |[1]| |
|_|[ ]|_|

Alla fine entrambi hanno 4 rettangoli attorno a [1].

    
posta David Chen 21.03.2015 - 05:12
fonte

2 risposte

1

Penso che questo sia un problema non facile quando si gestiscono array più complessi, come ad esempio:

[0][0][0][0][0][0][1][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][1][0][0][0][0][0]
[0][0][0][0][0][0][0][1][0][0]
[0][0][0][0][0][1][0][0][1][0]       
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][1][0][0][0]
[0][0][0][0][1][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][1][0][0][0][0][0][0]

La vera complessità sta nel tentativo di utilizzare i minimi rettangoli possibili. Un approccio sarebbe quello di calcolare la colonna del primo '1' che appare in ogni riga. Quindi, la colonna minima viene utilizzata per creare un sottoarray. Ad esempio:

[0][0][0][0][0][0][1][0][0][0] (6)              |--------|0][0][0][1][0][0][0]
[0][0][0][0][0][0][0][0][0][0] (-1)             |        |0][0][0][0][0][0][0]
[0][0][0][0][1][0][0][0][0][0] (4)              |        |0][1][0][0][0][0][0]
[0][0][0][0][0][0][0][1][0][0] (7)              |        |0][0][0][0][1][0][0]
[0][0][0][0][0][1][0][0][1][0] (5) -> min=3 ->  |        |0][0][1][0][0][1][0] --> ...
[0][0][0][0][0][0][0][0][0][0] (-1)             |        |0][0][0][0][0][0][0]
[0][0][0][0][0][0][1][0][0][0] (6)              |        |0][0][0][1][0][0][0]
[0][0][0][0][1][0][0][0][0][0] (4)              |        |0][1][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0] (-1)             |        |0][0][0][0][0][0][0]
[0][0][0][1][0][0][0][0][0][0] (3)              ---------|1][0][0][0][0][0][0]

Quindi continua la iterazione dalla prima riga. Tuttavia, non sono sicuro che questa soluzione trovi il minor numero di rettangoli.

Un altro approccio sarebbe partire dal punto più vicino al centro dell'array 2D ed eseguire un algoritmo BFS, fino a trovare un '1'. Quindi, questo BFS avrà creato un rettangolo e quindi la successiva iterazione verrà eseguita per il nuovo punto più vicino al centro. Questo approccio è sicuramente sub-ottimale, dal momento che verranno creati molti piccoli rettangoli negli angoli.

    
risposta data 27.03.2015 - 11:03
fonte
0

Potrei vedere questa funzione ricorsiva in cui cerchi l'angolo in alto a sinistra del prossimo rettangolo possibile. Scorri verso destra e verso il basso, tenendo traccia della nuova larghezza e altezza del rettangolo per determinare la lunghezza da controllare nella successiva riga / colonna di scansione. Quando hai colpito entrambi i bordi sinistro e inferiore, aggiungi risultato all'elenco dei risultati, contrassegna quelle "celle" come usate e reiterate. Quando non trovi celle vuote, hai finito.

    
risposta data 23.04.2015 - 17:24
fonte

Leggi altre domande sui tag