Koordinaten benachbarter Felder (2D) mit demselben Inhalt ermitteln. Starthilfe gesucht!

[downunderthunder]

Hallo,
ich würde mich über ein wenig Starthilfe bzgl. des folgenden Problems freuen:

Ich habe eine 2Dimensionale Matrix, nehmen wir an 100x100 Felder.

Jedes dieser Felder kann entweder den Wert 0 oder 1 beinhalten.
Es gibt "1" Zusammenhängende Felder, d.h. Felder mit dem Inhalt 1, die mindestens ein weiteres Nachbarfeld mit dem Inhalt 1 haben.
Ich würde gerne einen solchen Nachbarschaftsfelderzug erfassen, also die Koordinaten all dieser benachbarten Felder in ein Array speichern , um
dann später das dem Mittelpunkt dieses Nachbarschaftsfelderzuges am nächsten kommende Koordinatenpaar zu ermitteln.

numpy bietet sich hier an? Wenn ja, wie z.B.?

Gerne könnte ich ein kleines Bildchen erstellen, das mein Vorhaben veranschaulicht, jedoch fehlt es hier an der Möglichkeit, Bilder anzufügen.

[rogerb]

Hallo downunderthunder,

wenn du eine fertige Lösung suchst, wirst du hier wahrscheinlich das richtige finden:
https://scikit-image.org/docs/dev/api/s ... asure.html
Insbesondere diese Funktionen:
https://scikit-image.org/docs/dev/api/s ... html#label
https://scikit-image.org/docs/dev/api/s ... ml#moments

Hier ist aber trotzdem mal ein beispielhafter Ansatz ohne externe Library.

Code: Alles auswählen

import random


class Area:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.found = set()

        # Feld mit zufälligen "1" oder "0" zu jeweils (width) Spalten
        # und (height) Zeilen
        self.grid = [
            [random.randint(0, 1) for _ in range(width)]
            for _ in range(height)
        ]

    def find_neighbors(self, column, row):
        # Koordinate im gültigen Bereich?
        if 0 <= column < self.width and 0 <= row < self.height:
            value = self.grid[row][column]
        else:
            return

        # Wert "1" gefunden und noch nicht in der Menge der gefudenen
        if value and (column, row) not in self.found:
            self.found.add((column, row))
        else:
            return

        # diagonale und seitliche Nachbarn rekursiv prüfen
        # self.find_neighbors(column - 1, row - 1)   # links, oben
        self.find_neighbors(column, row - 1)       # oben
        # self.find_neighbors(column + 1, row - 1)   # rechts, oben
        self.find_neighbors(column - 1, row)       # links
        self.find_neighbors(column + 1, row)       # rechts
        # self.find_neighbors(column - 1, row + 1)   # links, unten
        self.find_neighbors(column, row + 1)       # unten
        # self.find_neighbors(column + 1, row + 1)   # unten, rechts
        return self.found


    def display(self):
        for row in self.grid:
            print(row)



area = Area(10, 10)
area.display()
column = 5
row = 5
print(f'Zusammenhängende "1"-Felder um Position({column}, {row}):\n{area.find_neighbors(column, row)}')

"""
Ausgabe:
[0, 0, 1, 0, 1, 1, 0, 1, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[1, 1, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
[1, 0, 1, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 0, 1, 1, 1, 0, 1, 1, 0]
[1, 1, 0, 0, 0, 1, 0, 1, 0, 1]
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 0, 0, 1, 0, 1, 1]
[0, 0, 1, 1, 1, 0, 0, 0, 1, 1]
Zusammenhängende "1"-Felder um Position(5, 5):
{(5, 5), (5, 4), (6, 4), (7, 3), (4, 5), (5, 6), (5, 3), (6, 3), (3, 5)}
"""

Damit wird noch nicht der Schwerpunkt der zusammenhängenden Punkte berechnet, sondern nur die Koordinaten.

Ich hoffe, die Kommentare enthalten genug Erklärung, sonst frag nochmal nach.
Man kann auch die diagonalen Nachbarn prüfen, dann müssen die entsprechenden Zeilen eben wieder aktiviert werden.

[ThomasL]

Hi rogerb,

Code: Alles auswählen

        # Wert "1" gefunden und noch nicht in der Menge der gefundenen
        if value and (column, row) not in self.found:
            self.found.add((column, row))

Warum die Abfrage ob die Koordinate schon enthalten ist?

[rogerb]

Hallo ThomasL,

Warum die Abfrage ob die Koordinate schon enthalten ist?

Als Rekursionsanker müssen zwei Bedingungen geprüft werden:
1) Keine "1" gefunden
2) Feld schon besucht

Bei ringförmig verbundenen "1"-en würde man sonst ja immer weiter im Kreise suchen, bis die maximale Rekursionstiefe erreicht ist.
Selbst bei nur zwei verbundenen Feldern tritt das Problem auf, da der Algorithmus ja nach dem Schritt in eine bestimmte Richtung auch immer wieder auf das vorherige Feld schaut.

[EyDu]

Oder auch `cv2.connectedComponents` bzw. `scipy.ndimage.measurements.label`. Bei beiden kann (mehr oder weniger) festgelegt werden, wie "Nachbar" definiert ist.

[__blackjack__]

@rogerb: Das wäre eventuell deutlicher wenn das ``return`` nicht im ``else`` stehen würde. Dann würde man die ``if``-Abfragen eher als ”early returns” erkennen. Noch besser wäre IMHO diese ``return``\s da gar nicht stehen zu haben, sondern die beiden ``if``\s einfach zu verschachteln.

Was komisch bis falsch ist, ist das ”globale” `self.found` und das `find_neighbors()` mal nackte ``return``\s und mal ``return self.found`` verwendet. Man kann sich nicht wirklich auf den Rückgabetyp verlassen, und man kann die Methode nur einmal wirklich sinnvoll aufrufen, danach kommen falsche Ergebnisse wenn man sie auf Felder mit einer 1 anwendet.

Code: Alles auswählen

    def find_neighbors(self, column, row, found=None):
        if found is None:
            found = set()

        # Koordinate im gültigen Bereich?
        if 0 <= column < self.width and 0 <= row < self.height:
            value = self.grid[row][column]

            # Wert "1" gefunden und noch nicht in der Menge der gefudenen
            if value and (column, row) not in found:
                found.add((column, row))

                # Diagonale und seitliche Nachbarn rekursiv prüfen
                # self.find_neighbors(column - 1, row - 1, found)   # links, oben
                self.find_neighbors(column, row - 1, found)  # oben
                # self.find_neighbors(column + 1, row - 1, found)   # rechts, oben
                self.find_neighbors(column - 1, row, found)  # links
                self.find_neighbors(column + 1, row, found)  # rechts
                # self.find_neighbors(column - 1, row + 1, found)   # links, unten
                self.find_neighbors(column, row + 1, found)  # unten
                # self.find_neighbors(column + 1, row + 1, found)   # unten, rechts

        return found

[rogerb]

@__blackjack__,

self.found ist nicht global, sondern eine Instanzvariable. Aus gutem Grund, denn es sollen ja noch weitere Funktionen implementiert werden und dafür ist es sinnvoll die gefundenen Koordinaten zu behalten. Das bedeutet, dass es eigentlich auch gar keinen Rückgabewert geben muss.
Nimmt man für "found" eine einfache lokale Variable, muss man diese durch alle Rekursionsebenen mitschleppen.

Die "early returns" machen doch gerade deutlich was der Rekursionsanker ist, und tragen so zum Verständnis bei. Zugegeben, die returns in die Else-Zweige zu packen ist nicht so schön, aber dafür muss man ja nur die If-Bedingungen negieren und schon fallen die else-Zweige weg. Early returns sind ein auch gutes Mittel um die tiefe Einrückung zu verhindern.
Und bei so einem Zwischenstand sind solche Optimierungen sowieso verfrüht.

[__deets__]

Natürlich ist found nicht global. Aber unglücklich. Ein Instanz-Attribut, das dann auch noch als Return-Wert genutzt wird, obwohl sein scope ja nur der Aufruf ist. Bei rekursiven Algorithmen würde ich eher zu einem Akkumulator-Argument greifen. Zb via default Argument mit None

Code: Alles auswählen

def recursive(accu=None)
    if accu is None:
        accu = set()
    …
    recursive(accu)

recursive()

Alternativ mit einem Wrapper, der einen accu anlegt, und eine private eigentliche Implementierung aufruft.

[__blackjack__]

@rogerb: Okay, nicht wirklich global, aber halt auch auf der Ebene so problematisch wie globale Variablen. Das sollte der Rückgabewert sein und kein Zustand der beim nächsten Aufruf immer noch da ist und zu einem falschen Ergebnis führt. Oder Du möchtest da vielleicht zwei Mengen haben — einmal als Attribut das sich alle bisher besuchten Koordinaten merkt, und einmal für den jeweiligen Aufruf lokal und durchgereicht wird und das Ergebnis des Methodenaufrufs liefert.

[rogerb]

@__blackjack__,
die von dir beschriebene Problematik, gilt immer für Instanz-Attribute. Globale Variablen sind auf Modulebene frei veränderbar, was zu schwer nachvollziehbaren Fehlerquellen führen kann. Das kann man doch nicht einfach auf Instanz-Attribute übertragen.
Im konkreten Fall besteht die einzige Problematik darin, dass "find_neighbors" überhaupt einen Rückgabewert hat. Aber ich hatte ja schon geschrieben, dass man einfach darauf verzichten kann.
Dann kann man den Zugriff auf die gefundenen Koordinaten über einen vorgelagerten Methodenaufruf regeln.

Das Ganze in einem Wrapper zu verstecken, wie von __deets__ angemerkt, scheint mir innerhalb einer Klasse nicht notwendig zu sein. Das wäre meiner Meinung nach eine Möglichkeit, wenn man ganz auf die Klasse verzichten möchte und nur eine Funktion zur Verfügung stellen will.

Code: Alles auswählen

class Area:
    def __init__(self, grid):
        self._found = set()
        self.grid = grid
        self.width = len(grid[0])
        self.height = len(grid)

    def get_connected(self, column, row):
        self._find_neighbors(column, row)
        return self._found

    def _find_neighbors(self, column, row):
        # Früher Rücksprung falls Koordinaten ungültig
        if not 0 <= column < self.width or not 0 <= row < self.height:
            return

        value = self.grid[row][column]

        # Rücksprung falls keine "1" gefunden, oder Koordinate schon vorher gefunden
        if not value or (column, row) in self._found:
            return

        self._found.add((column, row))

        # diagonale und seitliche Nachbarn rekursiv prüfen
        self._find_neighbors(column - 1, row - 1)  # links, oben
        self._find_neighbors(column, row - 1)  # oben
        self._find_neighbors(column + 1, row - 1)  # rechts, oben
        self._find_neighbors(column - 1, row)  # links
        self._find_neighbors(column + 1, row)  # rechts
        self._find_neighbors(column - 1, row + 1)  # links, unten
        self._find_neighbors(column, row + 1)  # unten
        self._find_neighbors(column + 1, row + 1)  # unten, rechts

    def display(self):
        for row in self.grid:
            print(row)

[__deets__]

Deine Ausfuehrungen zur Schaedlichkeit von globalem Zustand sind korrekt. Nur fehlt der Schritt weiter: *jeder* Zustand ist potentiell problematisch. Eine der Hauptursachen fuer Abstuerze oder anderes Fehlverhalten sind unerwartete Zustandskombinationen. Darum ist es immer vorzuziehen, Zustand so beschraenkt wie moeglich anzulegen. Und ihn zB zu berechnen. Simple Beispiele: Flaeche/Umfang eines Kreises aus dessen Durchmesser abzuleiten, statt explizit zu speichern, und ploetzlich Inkogruenz beim update des Durchmessers zu beobachten.

Da deine Klasse die Menge der besuchten Elemente nur waehrend der Laufzeit des Algorithmus, aber nicht danach benoetigt, wuerde ich den nicht anlegen. Und ja: wenn die Klasse nur aus Konstruktor und einer einmal aufzurufenden Methode besteht, dann ist sie besser eine Funktion. Das kommt noch oben drauf. Wobei man sie ja schnell nuetlicher machen kann, zb mit Mutatoren fuer die Positionen.

[pillmuncher]

__deets__ und __blackjack__ haben völlig recht.

Statt einem Attribut sollte man einen Accumulator verwenden. Mir persönlich würde besser gefallen, wenn alle drei Base Cases explizit gemacht würden, wenn die Punkte der rekursiven Aufrufe einer anderen Systematik folgen würden, und wenn es (x, y) wäre statt (column, row):

Code: Alles auswählen

class Area:
    def __init__(self, grid):
        self.grid = grid
        self.width = len(grid[0])
        self.height = len(grid)

    def get_connected(self, x, y):
        found = set()
        self._find_neighbors(found, x, y)
        return found

    def _find_neighbors(self, found, x, y):
        # Base Case #1: Koordinate ungültig.
        if not 0 <= x < self.width or not 0 <= y < self.height:
            return
        # Base Case #2: keine "1" hier.
        if not self.grid[y][x]:
            return
        # Base Case #3: "1" bereits früher hier gefunden.
        if (x, y) in found:
            return
        found.add((x, y))
        # Flooding:
        self._find_neighbors(found, x, y - 1)
        self._find_neighbors(found, x, y + 1)
        self._find_neighbors(found, x - 1, y)
        self._find_neighbors(found, x + 1, y)
        self._find_neighbors(found, x - 1, y - 1)
        self._find_neighbors(found, x - 1, y + 1)
        self._find_neighbors(found, x + 1, y - 1)
        self._find_neighbors(found, x + 1, y + 1)

Und weil Rekursion in Python problematisch sein kann, nochmal ohne diese:

Code: Alles auswählen

class Area:
    def __init__(self, grid):
        self.grid = grid
        self.width = len(grid[0])
        self.height = len(grid)

    def get_connected(self, x, y):
        found = set()
        todo = [(x, y)]
        while todo:
            x, y = todo.pop()
            # Base Case #1: Koordinate ungültig.
            if not 0 <= x < self.width or not 0 <= y < self.height:
                continue
            # Base Case #2: keine "1" hier.
            if not self.grid[y][x]
                continue
            # Base Case #3: "1" bereits früher gefunden.
            if (x, y) in found:
                continue
            found.add((x, y))
            # Flooding:
            todo.append((x, y - 1))
            todo.append((x, y + 1))
            todo.append((x - 1, y))
            todo.append((x + 1, y))
            todo.append((x - 1, y - 1))
            todo.append((x - 1, y + 1))
            todo.append((x + 1, y - 1))
            todo.append((x + 1, y + 1))
        return found

Ungetestet. Übrigens einer der sehr wenigen Fälle, in denen ich continue verwenden würde.

[rogerb]

Mir ist schon aufgefallen, dass ihr euch gerne unkritisch beipflichtet, aber es geht ja nicht ums Recht haben. Bei solchen Themen müssen oft Vor- und Nachteile gegeneinander abgewogen werden.
Ein Accumulator muss bei einem rein funktionalen Ansatz verwendet werden. Aber nicht weil das besonders elegant wäre, sondern weil es eben nicht anders geht, wenn man einen Zustand zwischenspeichern muss.
Da das Alles aber sowieso in einer Klasse stattfindet, bietet sich ein Instanz-Attribut einfach an. Allein schon weil es die Funktionsaufrufe übersichtlicher macht.
Ein Argument gegen einen Akkumulator im Kontext einer Klasse, wäre noch das ständige Ablegen auf den Stack bei jedem rekursiven Aufruf. Ich muss zugeben, dass das hier aber nicht zählt, da, soweit ich weiß, keine Kopien von einem Set angelegt werden. Bei anderen Datentypen aber durchaus zu bedenken.

Wenn man jetzt mit der Akkumulatorvariante fertig ist und einen Wert zurück geben will, hat man ein Problem, denn man muss ja irgendwie dran kommen.
__deets__ hat den Teil in seinem Beispiel geschickt weggelassen.
Naja, bei __blackjack__'s Beispiel gibt man dann jedesmal einen Wert in Leere zurück, bis er beim letzten mal endlich übernommen wird.
Bei pillmuncher haben wir dann so etwas:

Code: Alles auswählen

found = set()
self._find_neighbors(found, x, y)
return found

In benachbarten Codezeilen geht das vielleicht noch, aber wenn man sich mal vorstellt, dass theoretisch irgendwann später der Wert, welcher zuvor innerhalb der Methode verändert wurde, abgeholt wird, ist das eher fragwürdig.
Das ist für mich auf jeden Fall keine Alternative für ein Instanz-Attribut.

[pillmuncher]

@rogerb: Das hat alles nichts damit zu tun, dass wir uns hier alle gerne gegenseitig beipflichten, sondern im meinem Fall eher damit, dass ich seit bald 35 Jahren programmiere und all diese Fehler bereits gemacht habe, die ich den Leuten auszureden versuche. Ein Experte ist schließlich jemand, der jeden möglichen Fehler in seinem Fachgebiet wenigstens einmal gemacht hat. Und ich denke, das habe ich. Ich arbeite jedenfalls daran. Deswegen hier meine Expertise:

Derartige Sachen kann man nur dann mit einem Attribut implementieren, wenn man die komplette, alleinige Kontrolle über den Zugriff auf und die Lebenszeit von einem Objekt hat. Man kann so, wie du es ursprünglich programmiert hattest, die Methode find_neighbors() nämlich nur ein einziges Mal während der Lenbenszeit eines Area-Objekts aufrufen und ein garantiert richtiges Ergebnis erhalten. Denn zwischen einem Aufruf und dem nächsten können sich die zugrunde liegende Daten bereits derart geändert haben, dass das Ergebnis des zweiten Aufrufs falsch ist. Von den Problemen gar nicht zu reden, die man sich bei konkurrierendem Zugriff im Kontext von Multithreading einhandeln würde. Da ist es viel mehr Arbeit, überall im Code dafür zu sorgen, dass ein Area-Objekt nicht nach außen durchschlupft, als es einfach gleich so zu programmieren, dass man daran nicht mehr denken muss.

Instruktiv ist hier auch die Art und Weise, wie object.__deepcopy__() und copy.deepcopy() funktionieren.

Übrigens habe ich auch eine Lösung präsentiert, bei dem der Accumulator nie den Kontext der Funktion verlässt und die nicht die Gefahr birgt, das Rekursionslimit zu sprengen.

[__deets__]

@rogerb: du faengst an nach den wirklich kleinsten denkbaren Strohalmen zu greifen. In Python gibt es keinerlei Unterschiede zwischen verschiedenen Typen und wie viel Platz die auf dem Stack beanspruchen. Ein int genauso wie ein set ist einfach eine Referenz, intern ein Pointer auf ein PyObject. Und das Argument, ein funktionaler Ansatz waere nur mit Akku gut, weil es eben nicht anders geht, und wuerde die Argumentliste aufblaehen, ist angesichts deiner eigenen Einlassungen zu globalem Zustand absurd komisch. Jede globale Variable in einer Funktion reduziert ebenfalls die Parameteranzahl. Und die ach so boese Stackgroesse. Aber die Vorteile, sich bei der Betrachtung einer Funktion auf so wenig Kontext wie noetig verlassen zu muessen, gelten nunmal universal.

Dir geht einfach auf den Senkel, dass du hier ungefragt Code-Reviews erhaelst. Das ist alles.

Und hier noch zum guten Schluss meine Umsetzung deiner Area-Klasse mit dem Akku, um meine "Auslassungssuende" zu korrigieren. Und sieh da: man kommt *ganz genauso* dran wie bei dir, naemlich einfach durch Rueckgabe. Eine mentale Uebung von der wir beide wissen, dass du dazu sehr wohl in der Lage bist. Aber darum ging es ja nicht, sonder darum, deine eigenen Rosinen zu picken

Code: Alles auswählen

class Area:
    def __init__(self, width, height, grid):
        self.width = width
        self.height = height

        # Feld mit zufälligen "1" oder "0" zu jeweils (width) Spalten
        # und (height) Zeilen
        self.grid = [
            [random.randint(0, 1) for _ in range(width)]
        for _ in range(height)
        ]

    def find_neighbors(self, column, row, found=None):
        if found is None:
            found = set()
        # Koordinate im gültigen Bereich?
        if 0 <= column < self.width and 0 <= row < self.height:
            value = self.grid[row][column]
        else:
            return found

        # Wert "1" gefunden und noch nicht in der Menge der gefudenen
        if value and (column, row) not in found:
            found.add((column, row))
        else:
            return found

        # diagonale und seitliche Nachbarn rekursiv prüfen
        # self.find_neighbors(column - 1, row - 1)   # links, oben
        self.find_neighbors(column, row - 1, found)       # oben
        # self.find_neighbors(column + 1, row - 1)   # rechts, oben
        self.find_neighbors(column - 1, row, found)       # links
        self.find_neighbors(column + 1, row, found)       # rechts
        # self.find_neighbors(column - 1, row + 1)   # links, unten
        self.find_neighbors(column, row + 1, found)       # unten
        # self.find_neighbors(column + 1, row + 1)   # unten, rechts
        return found

[rogerb]

@pillmuncher,

dein iterativer Ansatz ist sicher eine robuste Lösung mit der man das am Ende gut umsetzen könnte. Denn rekursiv läuft man schon bei einer Feldgröße von 50x50, oder noch früher in Probleme.
Hauptsächlich ging es aber um den Akkumulator bei Verwendung einer Rekursion. Daher bin ich darauf nicht eingegangen.

Ich habe mir den source-code von copy.py angeschaut. Wenn ich das richtig verstehe, werden Compound-Typen rekursiv und type-spezifisch kopiert. Dabei gibt es ein "memo"-Dictionary welches die id zu den verschachtelten Compound-Objekten nachhält. Das verhindert, dass Objekte während des Kopierens der Garbage-Collection zum Opfer fallen? Das memo entspricht dann dem found in deinem Beispiel. Ich vermute, was du damit sagen willst ist, dass es bei einem rekursiven Algorithmus einiges an zusätzlicher Absicherung bedarf um robust zu sein.

Mein ursprünglicher Code hatte tatsächlich das Problem, dass ein zweiter Aufruf der Methode nur None zurückgibt. Das war falsch, habe ich aber später korrigiert.
So, mit Multithreading hast du allerdings Recht. Wenn ich mehreren Threads Zugriff auf das selbe area-Objekt gebe, gibt es Durcheinander. Das passiert bei deinem rekursiven Ansatz mit dem Akkumulator nicht. Ich hab ihn jedenfalls nicht kaputt gekriegt. Dass du von außen auf eine Variable zugreifst, die innerhalb der Methode verändert wurde, finde ich aber immer noch fragwürdig.

Ich habe hier schon einige Threads mitgelesen, bei denen recht kontrovers diskutiert wurde. Am Ende, wenn die Argumente schließlich ausgehen und man sich immer noch nicht einigen konnte, liest man dann "Das mache ich schon seit x Jahren so und da muss das ja wohl stimmen". Das wirkt bei mir alles andere als überzeugend, im Gegenteil. Ich respektiere Erfahrung, aber ich finde hier im Forum ist das nichts worauf man sich berufen kann. Für mich fängt jeder Post bei Null an. Ob das was jemand schreibt, sinnvoll ist, hängt vom Inhalt ab und es muss auch kritischen Gegenfragen standhalten.

[__deets__]

Es geht bei memo nicht um die Vermeidung von GC. Sondern um die Unterbrechung von Zyklen. Sowas hier

l = []
l.append(l)

würde sonst eine Endlosrekursion auslösen.