0 Daumen
222 Aufrufe

Aufgabe Geoinformatik:

Ihnen llegt folgendes Raster vor. Dieses wird mit dem Komprimierungsverfahren Quadtree gespeichert. Verfassen Sie einen Lösungsvorschlag, wie das Raster damit abgespelchert wird.

22222233
22222233
22222222
22225555
22225555
22224455
22224455
22224455
Avatar von

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Komprimierungsverfahren Quadtree

Ein Quadtree ist eine baumartige Datenstruktur, die dazu verwendet wird, zweidimensionale räumliche Daten effizient zu speichern und zu verwalten. Beim Komprimierungsverfahren Quadtree wird das Raster in vier gleich große Quadranten aufgeteilt. Jeder Quadrant kann wiederum weiter unterteilt werden, bis die Quadranten entweder homogen sind oder eine bestimmte Mindestgröße erreicht haben. Homogen bedeutet in diesem Kontext, dass alle Werte innerhalb des Quadranten gleich sind.

Schrittweise Erklärung zur Komprimierung des gegebenen Rasters:

Gegebenes Raster:
\( \begin{array}{cccccccc} 2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 \\ 2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 & 5 & 5 & 5 & 5 \\ 2 & 2 & 2 & 2 & 5 & 5 & 5 & 5 \\ 2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\ 2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\ 2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\ \end{array} \)

Schritt 1: Erste Unterteilung

Wir teilen das Raster in vier Quadranten auf:

\( \begin{array}{cccc|cccc} 2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 \\ 2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 & 5 & 5 & 5 & 5 \\ \hline 2 & 2 & 2 & 2 & 5 & 5 & 5 & 5 \\ 2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\ 2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\ 2 & 2 & 2 & 2 & 4 & 4 & 5 & 5 \\ \end{array} \)

Schritt 2: Überprüfung der Quadranten

1. Quadrant 1 (links oben, 4x4):
\( \begin{array}{cccc} 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ \end{array} \)
Dieser Quadrant ist homogen (alle Elemente sind 2), daher wird er nicht weiter unterteilt.

2. Quadrant 2 (rechts oben, 4x4):
\( \begin{array}{cccc} 2 & 2 & 3 & 3 \\ 2 & 2 & 3 & 3 \\ 2 & 2 & 2 & 2 \\ 5 & 5 & 5 & 5 \\ \end{array} \)
Dieser Quadrant ist nicht homogen und muss weiter unterteilt werden.

3. Quadrant 3 (links unten, 4x4):
\( \begin{array}{cccc} 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ \end{array} \)
Dieser Quadrant ist homogen (alle Elemente sind 2), daher wird er nicht weiter unterteilt.

4. Quadrant 4 (rechts unten, 4x4):
\( \begin{array}{cccc} 5 & 5 & 5 & 5 \\ 4 & 4 & 5 & 5 \\ 4 & 4 & 5 & 5 \\ 4 & 4 & 5 & 5 \\ \end{array} \)
Dieser Quadrant ist nicht homogen und muss weiter unterteilt werden.

Schritt 3: Weitere Unterteilung von Quadrant 2 und Quadrant 4

Quadrant 2 (weiter unterteilt):
\( \begin{array}{cc|cc} 2 & 2 & 3 & 3 \\ 2 & 2 & 3 & 3 \\ \hline 2 & 2 & 2 & 2 \\ 5 & 5 & 5 & 5 \\ \end{array} \)

Quadrant 4 (weiter unterteilt):
\( \begin{array}{cc|cc} 5 & 5 & 5 & 5 \\ 4 & 4 & 5 & 5 \\ \hline 4 & 4 & 5 & 5 \\ 4 & 4 & 5 & 5 \\ \end{array} \)

Beide Unterteilungen zeigen, dass wir zu tieferen Ebenen des Quadtrees gelangen müssen. Die weiteren kleinen Quadranten innerhalb von Quadrant 2 und Quadrant 4 werden für Homogenität überprüft und falls notwendig, weiter unterteilt, bis nur homogene Quadranten übrigbleiben.

Python-Code zur Illustration

Hier ist ein Beispiel, wie man dies in Python umsetzen könnte:

python
class QuadtreeNode:
    def __init__(self, value=None):
        self.value = value
        self.children = None

def build_quadtree(grid, x, y, size):
    first_value = grid[x][y]
    homogeneous = True
    for i in range(size):
        for j in range(size):
            if grid[x+i][y+j] != first_value:
                homogeneous = False
                break
        if not homogeneous:
            break
    
    node = QuadtreeNode(first_value if homogeneous else None)
    if not homogeneous:
        half_size = size // 2
        node.children = [
            build_quadtree(grid, x, y, half_size),
            build_quadtree(grid, x, y + half_size, half_size),
            build_quadtree(grid, x + half_size, y, half_size),
            build_quadtree(grid, x + half_size, y + half_size, half_size),
        ]
    return node

def print_quadtree(node, indent=0):
    if node.children is None:
        print("  " * indent + str(node.value))
    else:
        for child in node.children:
            print_quadtree(child, indent + 1)

# Gegebenes Raster
grid = [
    [2, 2, 2, 2, 2, 2, 3, 3],
    [2, 2, 2, 2, 2, 2, 3, 3],
    [2, 2, 2, 2, 2, 2, 2, 2],
    [2, 2, 2, 2, 5, 5, 5, 5],
    [2, 2, 2, 2, 5, 5, 5, 5],
    [2, 2, 2, 2, 4, 4, 5, 5],
    [2, 2, 2, 2, 4, 4, 5, 5],
    [2, 2, 2, 2, 4, 4, 5, 5],
]

# Quadtree erstellen
quadtree = build_quadtree(grid, 0, 0, len(grid))

# Quadtree ausgeben
print_quadtree(quadtree)


Dieser Code zeigt, wie man das Raster in einen Quadtree umwandeln und diesen ausgeben kann. Dabei wird geprüft, ob ein Quadrant homogen ist (alle Felder haben denselben Wert) und gegebenenfalls in vier kleinere Quadranten unterteilt.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community