Vollständige Rechtecke finden, die 0 einschließen

Es gibt verschiedene Rechtecke in gegebenen 1000 x 1000-Arrays. in <Figure 1>, die als gelbe Zelle angezeigte serielle „1“ ist das Muster eines Rechtecks. Die Mindestgröße des Rechtecks ​​in <Figure 1> ist 3 x 3 als grüne Zelle dargestellt.

Innerhalb des Rechtecks ​​sollte mindestens eine ‘0’ stehen.

Aber in dieser Anordnung gibt es auch eine nicht geschlossene Form oder ein gerades Linienmuster.

(Der Anfangswert von array ist ‘0’, und die Muster werden als eine Reihe von ‘1’ dargestellt. Sie überlappen sich nicht und schließen sich nicht ein.)

Was könnte ein effizienter Algorithmus sein, um die vollständigen Rechtecke im Array zu finden, mit Ausnahme der nicht geschlossenen Form oder der geraden Linie? In der obigen Abbildung ist die Anzahl der vollständigen Rechtecke beispielsweise 3

Das ist ganz einfach. Wenn Sie haben n Quadrate, Sie können die Rechtecke in zählen O(n).

Annahmen:

• Die Grenzen jedes gültigen Rechtecks ​​teilen sich keine Zellen mit einem ungültigen Pfad.
• Wenn sich ein Rechteck in einem anderen befindet, würden Sie sich freuen, sie zu finden

Sie würden zusätzlichen Speicher benötigen, der so groß ist wie die Eingabe. Nennen wir das visited und mit 0 initialisieren.

Lassen Sie uns zuerst eine Hilfsfunktion konstruieren:

is_rectangle(square s)
    from s, go right while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go down while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go left while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go up while you see 1s and visited is 0
        mark them as 1 in visited
    if then one above is not s
        return 0
    return 1

Diese Funktion verfolgt grundsätzlich die 1s in Richtung rechts-unten-links-oben und prüft, ob die Bedingungen erfüllt sind (Länge mindestens 3 und Erreichen der Startposition). Es markiert auch die besuchten Plätze.

Das Wichtige an dieser Funktion ist, dass sie nur richtig funktioniert, wenn das Anfangsquadrat die obere linke Ecke ist.

Nun, die Lösung des Problems ist einfach:

num_rectangles = 0
initialize visited to 0 (rows x columns)
for r in rows
    for c in columns
        if visitied[r][c] or image[r][c] == 0
            continue
        num_rectangles += is_rectangle(<r,c>)
return num_rectangles

So wird der Algorithmus ausgeführt:

1. Fehlerhafter (und markierter) Teil eines fehlerhaften Rechtecks

2. Gefunden (und markiert) ein Rechteck.

3. Fehlgeschlagen auf einem einzelnen Quadrat (einer vertikalen Linie)

4. Fehlgeschlagen auf einem einzelnen Quadrat (einer vertikalen Linie)

5. Fehlgeschlagen auf einem einzelnen Quadrat (einer vertikalen Linie)

6. Finden Sie nach vielen ähnlichen Schritten das nächste Rechteck.

7. Und das nächste Rechteck

8. Ende des Algorithmus

Der folgende O(n)-Algorithmus funktioniert auf jeder 2D-Matrix von 0/1-Werten (das heißt, sich schneidende/überlappende Rechtecke sind erlaubt, ebenso wie beliebige nicht rechteckige offene/geschlossene Formen). Die Definition eines Rechtecks, das ich hier verwende, ist “das Innere besteht vollständig aus 0-Zellen” (wenn also z. B. ein Rechteck ein anderes vollständig enthält, wird nur das innere Rechteck gefunden; wenn auch enthaltende Rechtecke berücksichtigt werden sollten, dann jedes gefundene Rechteck kann gelöscht und der Algorithmus neu gestartet werden). Es basiert auf der Beobachtung, dass jede 0-Zelle im Inneren von sein kann höchstens ein 1-Rechteck.

Ich verwende die Konvention, dass x = 0 die Position ganz links und y = 0 die Position ganz oben ist.

1. Finde die obere linke Ecke. Beginnen Sie mit der Zelle oben links und fahren Sie von links nach rechts und von oben nach unten fort, um die nächste nicht besuchte Zelle zu finden, die die obere linke Ecke eines Rechtecks ​​mit durchgehender 0 sein könnte: Insbesondere muss es eine 0-Zelle sein hat 1-Zellen-Nachbarn in den SW-, W-, NW-, N- und NE-Positionen und 0-Zellen in den verbleibenden 3 benachbarten Positionen.
2. Finden Sie die obere rechte Ecke. Scannen Sie durch die Nachbarn zu ihrer Rechten, während diese Zellen 0 sind und einen 1-Zellen-N-Nachbarn haben.
3. Könnte dies die oberste Reihe eines durchgezogenen 0-Rechtecks ​​sein? Wenn die letzte Zelle, die von der obigen Schleife gefunden wird, bevor sie endet, eine Zelle ist, die die obere rechte Zelle in einem durchgehenden 0-Rechteck sein könnte (insbesondere eine 0-Zelle mit 1-Zellen-Nachbarn in NW, N, NE, E und SE-Zellen und 0-Zellen in den verbleibenden 3 Positionen), dann haben wir sowohl die obere y-Koordinate als auch die genaue Breite der ermittelt nur möglich solides 0-Rechteck, das eine dieser Zellen verwendet. Wenn die letzte Zelle diese Bedingungen in der oberen rechten Ecke nicht erfüllt, kann keine dieser Zellen Teil eines soliden 0-Rechtecks ​​sein: Markieren Sie sie als besucht und gehen Sie zu 1.
4. Nennen Sie die Start- und End-x-Koordinaten des Streifens von 0-Zellen x1 und x2; nennen wir die vertikale Position y1.
5. Scannen Sie nach unten, eine Reihe nach der anderen. Setzen Sie y2 = y1, und während die Linie zwischen x1 und x2 an der vertikalen Position y2 Teil des durchgezogenen 0-Rechtecks ​​sein könnte, erhöhen Sie y2. Insbesondere lautet der Test an jeder vertikalen Position y2: Die Zellen bei (x1 – 1, y2) und (x2 + 1, y2) müssen beide 1 sein, und alle Zellen dazwischen müssen 0 sein.
6. Könnte dies die unterste Reihe eines durchgezogenen 0-Rechtecks ​​sein? Wenn die letzte Zeile, die von der vorherigen Schleife gefunden wurde, bevor sie endet, eine Zeile ist, die die unterste Zeile eines durchgehenden 0-Rechtecks ​​sein könnte (insbesondere gibt es 1-Zellen auf der ganzen Strecke von (x1 – 1, y2 + 1) bis (x2 + 1, y2 + 1)), dann haben wir ein vollständig solides 0-Rechteck gefunden, das von 1-Zellen umgeben ist: Wenn seine Größe größer ist als das größte bisher entdeckte, dann zeichne es als das neue größte Rechteck auf. Andernfalls (wenn es in der nächsten Zeile keine durchgezogene Reihe von 1-Zellen gibt), kann keine der untersuchten 0-Zellen Teil eines durchgezogenen 0-Rechtecks ​​sein: Markieren Sie sie alle als besucht und gehen Sie zu 1.

Wenn Sie in Ihrem Array nur rechteckige Formen haben können, entspricht dies einem klassischen Problem der Berechnung von Binärbildern: Wenden Sie einfach einen Standardalgorithmus für verbundene Komponenten an. Sie beschriften nur verbundene Komponenten von 0 und zählen sie.

Sehen http://en.wikipedia.org/wiki/Connected-component_labeling zum Beispiel. Diese Art von Algorithmus ist für Bilder recht einfach, nimmt jedoch etwas Speicherplatz in Anspruch (gleiche Größe wie Ihr Eingabearray, vom Typ short oder int). Achten Sie auf die Konnektivität: Wenn Sie 4-Konnektivität wählen, zählen Sie eingeschlossene Rechtecke, auch wenn einige Ecken fehlen. Aber der Algorithmus ist einfacher als bei 8-Konnektivität.

Wenn Sie komplexere geschlossene Formen haben können, fügen Sie einfach eine Nachbearbeitung hinzu: Zählen Sie für jede verbundene Komponente die Anzahl der Pixel innerhalb des Begrenzungsrahmens der Komponente (wenn die beiden Zahlen gleich sind, haben Sie ein Rechteck).

Habe eine Weile darüber nachgedacht. Ich bin auf diese Methode gekommen:

1) Beseitigen Sie alle Nullen an den Rändern – ändern Sie ihren Wert auf 2

2) Füllen Sie die Matrix um die 2er herum

Dadurch bleibt nur eine Insel aus Nullen übrig, die nun auf Konvexität getestet werden kann. Also für jede Insel:

3) Suchen Sie in X und Y nach dem Ausmaß des Werts 0 – geben Sie ein potenzielles inneres Rechteck

4) Wenn das innere Rechteck eine 1 enthält ODER das äußere Rechteck eine 0 enthält, füllen Sie diese Insel mit 2s, da sie nicht konvex ist (daher kein Rechteck).

Angenommen, Sie finden einen guten Flood-Fill-Algorithmus (nicht wie meiner), sollte dies effizient sein, um den Suchraum schnell zu beschneiden.

Und jetzt zum Code (sorry, es ist Cis):

using System;
using System.Collections.Generic;

namespace Test
{
class MainClass
{
    static private int [,] matrix = new int[,] {
        {0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
        {0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
        {0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
        {0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
        {0,0,1,1,1,1,0,0,0,0,0,0,0,0,0},
        {0,0,1,0,0,1,0,0,1,1,1,0,1,1,0},
        {0,0,1,1,1,1,0,0,1,0,1,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,1,1,0,0,0,0}
    };

    static private int width = matrix.GetLength(0);
    static private int height = matrix.GetLength(1);

    private const int DEAD = 2;
    private const int RECT = 3;

    public static void Main (string[] args)
    {
        //width = matrix.GetLength(0);
        //height = matrix.GetLength(1);

        PrintMatrix ();
        EliminateFromEdges (DEAD);
        PrintMatrix ();
        FloodFill (DEAD); // very inefficient - find a better floodfill algorithm
        PrintMatrix ();

        // test each island of zeros for convexness
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                if (matrix[i,j] == 0)
                {
                    if (TestIsland(i,j) == false)
                    {
                        // eliminate this island as it is not convex
                        matrix[i,j] = DEAD;
                        FloodFill(DEAD);
                        PrintMatrix ();
                    }
                    else
                    {
                        // flag this rectangle as such
                        matrix[i,j] = RECT;
                        FloodFill(RECT);
                        PrintMatrix ();
                    }
                }
            }
        }

        // We're done, anything flagged as RECT can be expanded to yield the rectangles
        PrintMatrix ();
    }

    // flag any zero at edge of matrix as 'dead'
    static private void EliminateFromEdges(int value)
    {
        for (int i = 0; i < width; i++) 
        {
            if (matrix [i, 0] == 0) 
            {
                matrix [i, 0] = value;
            }
            if (matrix [i, height - 1] == 0)
            {
                matrix [i, height - 1] = value;
            }
        }
        for (int j = 1; j < height - 1; j++)
        {
            if (matrix [0, j] == 0)
            {
                matrix [0, j] = value;
            }
            if (matrix [width - 1, j] == 0)
            {
                matrix [width - 1, j] = value;
            }
        }
    }

    // propagte a value to neighbouring cells
    static private void FloodFill (int value)
    {
        bool change_made = true; // set to true to start things off
        while (change_made) {
            change_made = false;
            for (int i = 1; i < width - 1; i++) {
                for (int j = 1; j < height - 1; j++) {
                    if ((matrix [i, j] == 0) &&
                        ((matrix [i - 1, j] == value) || 
                        (matrix [i + 1, j] == value) ||
                        (matrix [i, j - 1] == value) || 
                        (matrix [i, j + 1] == value))) {
                        matrix [i, j] = value;
                        change_made = true;
                    }
                }
            }
        }
    }

    static private bool TestIsland (int x, int y)
    {
        // find convex extend of island
        int x2 = x;
        int y2 = y;
        while (matrix[++x2, y] == 0);
        x2--;
        while (matrix[x,++y2] == 0);
        y2--;

        // check inner cells (want all zeroes)
        for (int i = x; i <= x2; i++) 
        {
            for (int j = y; j <= y2; j++) 
            {
                if (matrix[i,y] != 0)
                {
                    return false;
                }
            }
        }

        // check surrounding cells (want all ones)
        x--; y--;
        x2++; y2++;
        for (int i = x; i <= x2; i++) 
        {
            if ((matrix[i,y] != 1) || (matrix[i,y2] != 1))
            {
                return false;
            }
        }
        for (int j = y + 1; j <= y2 - 1; j++) 
        {
            if ((matrix[x,j] != 1) || (matrix[x2,j] != 1))
            {
                return false;
            }
        }

        return true;
    }

    // for debug purposes
    static private void PrintMatrix ()
    {
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                switch(matrix[i,j])
                {
                case DEAD:
                    Console.Write("-");
                    break;
                case RECT:
                    Console.Write("+");
                    break;
                default:
                    Console.Write(matrix[i,j]);
                    break;
                }
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
}
}

Die Ausgabe dieses Codes

000000001111000
011111101001010
010000101001010
010000101001010
010000101000010
010000101000010
011111101001010
000000001111000
001111000000000
001001001110110
001111001010000
000000001110000

--------1111---
-1111110100101-
-1000010100101-
-1000010100101-
-1000010100001-
-1000010100001-
-1111110100101-
-0000000111100-
-0111100000000-
-0100100111011-
-0111100101000-
--------111----

--------1111---
-111111-1--1-1-
-100001-1--1-1-
-100001-1--1-1-
-100001-1----1-
-100001-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----

Das ist, was ich denke, könnte ziemlich ressourcenineffizient sein. Weiß nicht darüber.

1. Gehen Sie eine Reihe entlang, es sei denn, Sie finden mindestens eine 3 1s.
2. Traversieren Sie nach unten und tun Sie es boolean &-Operation mit den Zeilen unten –> Sie sollten das Format von ergeben 100..001 wenn es sich um ein gültiges Rechteck handelt. (Vorausgesetzt, Sie können das alles boolean Operationen)
3. Sie haben ein Rechteck gefunden, wenn Sie in Schritt 2 mindestens eine Zeile gefunden haben und schließlich alle 1s.
4. Wiederholen Sie dies mit dem nächsten Element der Reihe!