Parse 2D array ai rettangoli

Question

Sto cercando un modo per convertire un array 2D per il minor numero di rettangoli possibili come in questo esempio:

       X
    12345678
    --------
  1|00000000
  2|00011100
  3|00111000
Y 4|00111000
  5|00111000
  6|00000000

.

Alle coordinate angolari dei rettangoli:

Seguendo il modello (x1, y1); (x2; y2)

rectangle #1 (4,2);(6,2)
rectangle #2 (3,3);(5,5)

.

C'è stata una domanda simile qui prima, ma sfortunatamente, il collegamento fornito nella sua risposta è rotto, e non posso più controllarlo.

Mi piacerebbe farlo in c # ma qualsiasi tipo di aiuto è apprezzato.

(non deve nemmeno essere il minor numero di rettangoli possibili, ma il minimo è il migliore :))

Grazie in anticipo!

Answer 1

Penso che tu stia cercando di coprire un set di punti nel piano 2D con il numero minimo richiesto di rettangoli. Una risposta a Trova i rettangoli K coprono il numero massimo di punti ha detto che questo era un problema completo di NP e collegato a http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf (che funziona per me) Una ricerca Google trova http://2011.ccang.ca/pdfschedule/papers/paper102.pdf .

Le carte sono d'accordo sul fatto che il rivestimento rettangolo è completo, ma non lo dimostriamo, e i riferimenti per questo sembrano essere insolitamente elusivi -

Cosa prendo da questi documenti è questo:

1) È improbabile che vi sia un modo a prezzi accessibili per ottenere la risposta assolutamente migliore per grandi problemi, quindi potresti dover spendere un sacco di tempo per ottenere risposte esatte per problemi che sono in senso piccolo, esauriente su tutte le possibili alternative o forse usando qualcosa come il ramo e legato, o accontentarsi di metodi accessibili - come ricerca avida, o ricerca del fascio o ricerca limitata discrepanza - che non sono garantite per darti la risposta assolutamente migliore.

2) In questo caso sembrano essere versioni più limitate di questo problema che non sono np-completi. Potresti leggere una carta e scoprire che ci sono alcuni dettagli del tuo problema significa che questo metodo si applica a te. Un esempio è "un algoritmo per la costruzione delle regioni con rettangoli: Indipendenza e set minimo generatrici Per collezioni di intervalli * "di Franzblau e Kleitman - L'ho trovato nella biblioteca digitale ACM, però - non so se è generalmente accessibile. Funziona per un insieme limitato di poligoni.

Answer 2

Questo potrebbe aiutarti a iniziare.Se converti i dati binari sui numeri, ottieni questo:

0
28
56
56
56
0

.

Quindi, dove mai ci sono numeri uguali consecutivi, c'è un rettangolo.