Marching Squares

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Schematische Darstellung des Algorithmus: Die grauen Quadrate sind Datenwerte auf einem Gitter. Rot dargestellt ist die Isolinie für einen Isowert im dunklen Grauwertbereich.

Marching Squares (von englisch „marschierende Quadrate“) ist ein Algorithmus aus der Computergrafik zur Berechnung von Isolinien aus einer Datenquelle. Isolinien sind Linien, die Datenpunkte mit gleichen Werten verbinden.

Einige typische Anwendungen für Marching Squares sind die Visualisierung von Isobaren auf Wetterkarten und Niveaulinien in Höhenfeldern. Der Name des Algorithmus leitet sich von seiner Funktionsweise ab. Der Datensatz wird in quadratische Gitterzellen zerlegt, welche nacheinander abgearbeitet werden. Marching Squares ist verwandt mit dem Marching-Cubes-Algorithmus, welcher zum Visualisieren von Isoflächen eingesetzt wird. Marching Squares wird im 2D-Raum und Marching Cubes im 3D-Raum eingesetzt.

Funktionsweise[Bearbeiten | Quelltext bearbeiten]

Nachdem der Isowert festgelegt wurde, für den die Linie berechnet werden soll, müssen die Daten in ein Gitter rasterisiert werden, sofern sich der Datensatz nicht schon auf einem gleichmäßigen Gitter befindet. Der Datensatz kann dann in ein gröberes Gitter unterteilt werden. Die Zellen dieses groben Gitters werden schrittweise durchlaufen.

Für jede Gitterzelle wird überprüft, ob ihre Eckpunkte über oder unter dem Isowert liegen. Es können 16 Fälle auftreten, die sich unter Berücksichtigung von Symmetrien auf die folgenden vier zurückführen lassen:

  • Fall 1: alle Ecken größer / kleiner
  • Fall 2: genau eine Ecke größer / kleiner
  • Fall 3: genau zwei Ecken mit gemeinsamer Kante größer / kleiner
  • Fall 4: genau zwei gegenüberliegende Ecken größer / kleiner

Im 4. Fall kann zunächst nicht entschieden werden, wie die beiden Isoliniensegmente durch die Zelle verlaufen müssen. Dafür muss das Innere der Zelle untersucht werden.

Soll die Isolinie feiner abgetastet werden, als es das grobe Gitter zulässt, so kann man in den Fällen 2 bis 4 die Gitterzelle erneut unterteilen und den Algorithmus wiederholt anwenden.

Kanten, bei denen ein Endknoten über dem Isowert und der andere darunter liegt werden von der Isolinie geschnitten. Die Schnittposition kann linear interpoliert werden, da der Isowert und die Werte an den Endknoten bekannt sind. Für die Berechnung gilt: mit

Die Schnittposition ist dann .

Beispiel[Bearbeiten | Quelltext bearbeiten]

Hier wird ein Objekt umfahren. Es gibt 16 verschiedene Möglichkeiten. In der Abbildung zeigen die Pfeile in die nächste anzufahrende Richtung.

Marchsquares.png

Quellen[Bearbeiten | Quelltext bearbeiten]

  • Kai Hormann: Computergrafik 2. (PDF) 22. Juni 2006, abgerufen am 5. September 2009.
  • Stefan Gumhold: Wissenschaftliche Visualisierung. Abbildung. 2009 (Vorlesungsfolien).

Weblinks[Bearbeiten | Quelltext bearbeiten]