2D Array Koordinaten.

[Wilk86]

Hallo Forum,

Ich hab Schwierigkeiten aus einer 2D Array die Koordinaten zu speichern in einer/mehrere Arrays und die 8 ist die Koordinaten im Array

Code: Alles auswählen

raster = [[0, 8, 8, 0, 0, 0],
          [0, 8, 8, 8, 0, 0],
          [0, 0, 0, 8, 8, 0],
          [0, 8, 0, 0, 0, 0],
          [0, 8, 8, 8, 0, 0]]

die Regel ist alle benachbarten 8 in einer Array schreiben. Die 8 kann bis zu 5 Nachbarn besitzen und darf nur 1 Feld entfernt sein ist es weiter als 1 Feld entsteht eine neu Gruppe. So sollte es aussehen Koordinaten = [0.1, 0.2, 1.1, 1.2, 1.3, 2.3, 2.4] Koordinaten2 = [3.1, 4.1, 4.2, 4,3]

ich habe schon mit append, remove, insert versucht aber das problem ist mein Hirn.

Könnt ihr mir weiter helfen?

[Sirius3]

@Wilk86: sollen die Koordinaten wirklich Kommazahlen sein?? Und wer ist der 5. Nachbar?
Was hast Du denn schon versucht? Hast Du Schwierigkeiten einen Algorithmus für das Problem zu entwickeln oder den Algorithmus nach Python zu übersetzen?

[BlackJack]

@Wilk86: Man könnte das als Graphenproblem auffassen. Die Knoten sind die Zellen mit den 8en und die Kanten verbinden die Nachbarknoten. Was man dann sucht sind alle zusammenhängenden Teilgraphen oder Komponenten. Mögliches und relativ einfaches vorgehen: Man geht davon aus das jeder Knoten eine eigene Komponente ist und markiert alle mit eindeutigen Nummern. Und dann fängt man an die Kanten durchzugehen und wann immer man auf eine Kante trifft die zwei Knoten mit verschiedenen Nummern haben ersetzt man die eine davon in allen Knoten mit der Nummer durch die andere. Wenn man am Ende alle Kanten durch hat, haben alle Knoten die zu einer zusammenhängenden Komponente gehören die gleiche Nummer und man kann die Komponenten auf diese Weise identifizieren. Das lässt sich recht einfach und schnell selber implementieren.

Wenn man das schon fertig implementiert haben möchte gibt es das `networkx`-Package das man installieren könnte.

Wenn die Daten umfangreicher sind als das 5×6-Raster, dann möchte man das vielleicht nicht in selbstgeschriebenem Python-Code lösen und auch nicht erst einen Graphen aufbauen. Da bietet es sich an eine Lösung mit Numpy/Scipy und dort speziell mit `scipy.ndimage` und der `label()`-Funktion aufzubauen.

[pillmuncher]

@Wilk86: Was BlackJack gesagt hat. Man könnte alternativ auch eine Disjoint-Set Datenstruktur mittels Union-Find aufbauen oder diesen Algorithmus anwenden:

Code: Alles auswählen

def connected_components(neighbors):

    seen = set()

    def component(node):
        todo = set([node])
        while todo:
            node = todo.pop()
            seen.add(node)
            todo |= neighbors[node] - seen
            yield node

    for node in neighbors:
        if node not in seen:
            yield component(node)

neighbors muss dabei ein Dictionary sein, das jeden Knoten auf eine Adjazenzliste abbildet, d.h. auf die Liste seiner Nachbarknoten. Das Dictionary mit den Adjazenzlisten lässt sich so erzeugen:

Code: Alles auswählen

from  collections import defaultdict

def make_adjacency_dict(matrix, width, height):
    adjacent = defaultdict(list)
    for x in range(1, width - 1):
        for y in range(1, height - 1):
            if matrix[x][y] != 8:
                continue
            if matrix[x - 1][y] == 8:
                adjacent[x, y].append((x - 1, y))
            if matrix[x + 1][y] == 8:
                adjacent[x, y].append((x + 1, y))
            if matrix[x][y - 1] == 8:
                adjacent[x, y].append((x, y - 1))
            if matrix[x][y + 1] == 8:
                adjacent[x, y].append((x, y + 1))
    return adjacent

Die Zeitkomplexität des Algorithmus zum Aufbau der Adjazenzlisten ist O(n) und die des Algorithmus zum Finden der verbundenen Komponenten ist O(n log n + k), wobei n die Anzahl der Knoten und k die Anzahl der ungeordneten Paare benachbarter Knoten ist. Ein theoretisch schnellerer Algorithmus ist mir nicht bekannt.

Ach ja: aller Code ist ungetestet.