imported>Phzh: Form, typo / Überschrift Einleitung nicht nötig

2020-04-24T09:22:42Z

Form, typo / Überschrift Einleitung nicht nötig

Neue Seite

[[Datei:Marching Squares Isoline.svg|mini|Schematische Darstellung des Algorithmus: Die grauen Quadrate sind Datenwerte auf einem [[Gitter (Geometrie)|Gitter]]. Rot dargestellt ist die [[Isolinie]] für einen Isowert im dunklen Grauwertbereich.]]
'''Marching Squares''' (von [[Englische Sprache|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 [[Isobare]]n auf Wetterkarten und [[Höhenlinie|Niveaulinien]] in [[Höhenfeld]]ern. 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|Marching-Cubes]]-Algorithmus, welcher zum Visualisieren von [[Isofläche]]n eingesetzt wird. Marching Squares wird im 2D-Raum und Marching Cubes im 3D-Raum eingesetzt.

== Funktionsweise ==
Nachdem der Isowert festgelegt wurde, für den die Linie berechnet werden soll, müssen die Daten in ein [[Gitter (Geometrie)|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.

<gallery>
Marching Squares Case1.svg|''Fall 1'': Alle Ecken liegen über (oder unter) dem Isowert.
Marching Squares Case2.svg|''Fall 2'': Bis auf eine Ecke liegen alle Ecken über (oder unter) dem Isowert.
Marching Squares Case3.svg|''Fall 3'': Je zwei Ecken an einer Kante liegen über, bzw. unter dem Isowert.
Marching Squares Case4.svg|''Fall 4'': Je zwei gegenüberliegende Ecken liegen über, bzw. unter dem Isowert.
Marching Squares Case4a.svg|Lösung für ''Fall 4'' abhängig von Werten innerhalb der Zelle.
Marching Squares Case4b.svg|Lösung für ''Fall 4'' abhängig von Werten innerhalb der Zelle.
</gallery>

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 [[Lineare Interpolation|linear interpoliert]] werden, da der Isowert <math>I</math> und die Werte <math>f_i</math> an den Endknoten <math>p_i = (x, y)</math> bekannt sind. Für die Berechnung gilt:
<math>I = a \cdot f_1 + b \cdot f_2</math> mit <math>a + b = 1</math>

Die Schnittposition ist dann <math>p_I = a \cdot p_1 + b \cdot p_2</math>.

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

[[Datei:Marchsquares.png]]

== Quellen ==
* {{Internetquelle
|autor=Kai Hormann
|url=http://www2.in.tu-clausthal.de/~hormann/teaching/CG2SS06/CG2.22.06.2006.pdf
|titel=Computergrafik 2
|datum=2006-06-22
|format=PDF
|abruf=2009-09-05}}
* {{Literatur
|Autor=Stefan Gumhold
|Titel=Wissenschaftliche Visualisierung
|TitelErg=Abbildung
|Datum=2009
|ISBN=
|Kommentar=Vorlesungsfolien}}

== Weblinks ==
* [http://web.archive.org/web/20141230044328/http://devblog.phillipspiess.com/better%20know%20an%20algorithm/2010/02/23/better-know-marching-squares.html Better know an Algorithm – Marching Square] – Eine sehr gute englische Anleitung
* Alle [https://caj.informatik.uni-jena.de/main?eERpc2s%3D=&eFJD=RE9XTkxPQUQ%3D&eElE=TXpNMk1RJTNEJTNE 16 Konfigurationen] einer Zelle
* [http://www.tomgibara.com/computer-vision/marching-squares Implementierung] in Java

[[Kategorie:Algorithmus (Computergrafik)]]

Marching Squares - Versionsgeschichte

imported>Phzh: Form, typo / Überschrift Einleitung nicht nötig