findet alle rechteckigen Flächen mit bestimmten Eigenschaften in einer Matrix

Question

eine n * m-Matrix mit den möglichen Werten von 1 gegeben, 2 und null:

. . . . . 1 . . 
    . 1 . . . . . 1 
    . . . 2 . . . . 
    . . . . 2 . . . 
    1 . . . . . 1 . 
    . . . . . . . . 
    . . 1 . . 2 . . 
    2 . . . . . . 1 

I für alle Blöcke B Suche (alle Werte zwischen enthaltend (x0, y0) und (x1, y1)), dass:

• enthalten mindestens eine '1'
• enthalten keine '2'
• sind keine Teilmenge einer anderen Block mit den obigen Eigenschaften

Beispiel:

Die roten, grünen und blauen Bereich enthalten alle eine '1', nicht '2', und sind nicht Teil einer größeren Fläche. Es gibt natürlich mehr als 3 solcher Blöcke in diesem Bild. Ich möchte alle diese Blöcke finden.

Was wäre ein schneller Weg, um alle diese Bereiche zu finden?

Ich habe eine funktionierende Brute-Force-Lösung, die über alle möglichen Rechtecke iteriert und prüft, ob sie die ersten beiden Kriterien erfüllen; dann Iterieren über alle gefundenen Rechtecke, Entfernen aller Rechtecke, die in einem anderen Rechteck enthalten sind; und ich kann das beschleunigen, indem ich nacheinander aufeinanderfolgende identische Zeilen und Spalten entferne. Aber ich bin ziemlich sicher, dass es einen viel schnelleren Weg gibt.

Answer 1

Ich habe endlich eine Lösung gefunden, die fast linear funktioniert (es gibt einen kleinen Faktor, der von der Anzahl der gefundenen Bereiche abhängt). Ich denke, das ist die schnellstmögliche Lösung.

durch diese Antwort inspiriert: https://stackoverflow.com/a/7353193/145999

First (Bilder auch von dort genommen), I trought die Matrix durch Spalte gehen, M1 eine neue Matrix zu schaffen, die Anzahl der Schritte zum letzten Messung ‚1‘ und eine Matrix M2 die Anzahl der Schritte bis zum letzten Mess ‚2‘

vorstellen, eine ‚1‘ oder ‚2‘ in einem der grauen Blöcke im Bild oben

am Ende haben I M1 und M2 suchen so:

Nein durch M1 und M2 in umgekehrter Richtung, von Zeile:

ich führen Sie den folgenden Algorithmus:

foundAreas = new list() 

For each row y backwards: 
    potentialAreas = new List() 
    for each column x: 
     if M2[x,y]>M2[x-1,y]: 
      add to potentialAreas: 
       new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false) 
     if M2[x,y]<M2[x-1,y]: 
      for each area in potentialAreas: 
       if area.hasTop and area.hasOne<area.height: 
         add to foundAreas: 
          new Box(Area.left,y-area.height,x,y) 
      if M2[x,y]==0: delete all potentialAreas 
      else: 
       find the area in potentialAreas with height=M2[x,y] 
       or the one with the closest bigger height: set its height to M2[x,y] 
       delete all potentialAreas with a bigger height 

      for each area in potentialAreas: 
       if area.hasOne>M1[x,y]: area.hasOne=M1[x,y] 
       if M2[x,y+1]==0: area.hasTop=true 

jetzt foundAreas enthält alle Rechtecke mit den gewünschten Eigenschaften .

Answer 2

Sie können zwischen jedem Rechteck und einer richtig cleveren Lösung wählen.

Zum Beispiel können Sie bei jedem 1 ein Rechteck erstellen und seine Kanten nach und nach in vier Richtungen erweitern. Stoppen Sie, wenn Sie eine 2 treffen, zeichnen Sie dieses Rechteck auf, wenn (a) Sie in allen 4 Richtungen anhalten mussten und (b) Sie dieses Rechteck noch nicht gesehen haben.

Dann Backtrack: Sie müssen in der Lage sein, sowohl das rote Rechteck als auch das grüne Rechteck ausgehend von 1 oben links zu erzeugen.

Dieser Algorithmus hat jedoch einige ziemlich schlimmen schlimmsten Fälle. Ein Eingang, der aus allen 1 s besteht, springt mir in den Sinn. Es muss also mit einer anderen Klugheit oder einigen Einschränkungen für die Eingabe kombiniert werden.

Answer 3

Betrachten Sie das einfachere Dimension Problem:

all Finden Sie den Teil von .2.1.1...12....2..1.1..2.1..2, die mindestens eine 1 und keine 2 und sind nicht Teilzeichenfolge solchen Zeichenfolge enthält. Dies kann in linearer Zeit gelöst werden, Sie müssen nur überprüfen, ob es einen 1 zwischen zwei 2 gibt.

Jetzt können Sie leicht diesen Algorithmus für das Problem zwei Dimensionen anpassen:

Für 1≤i≤j≤n Summe aller Linien i-j das folgende Gesetz mit: .+.=., .+1=1, .+2=2, 1+1=1, 1+2=2, 2+2=2 und die Auflösung verwenden Dimensionsalgorithmus zu der resultierenden Linie.

Komplexität: O (n2m).