Marching Squares

Marching Squares (from English " marching squares" ) is an algorithm in computer graphics for the calculation of contour lines from a data source. Isolines are lines connecting the data points with the same values ​​.

Introduction

Some typical applications for Marching Squares are the visualization of isobars on weather maps and contour lines in height fields. The name of the algorithm is derived from its operation. The data set is divided into a square lattice cells, which are processed in succession. Marching Squares is related to the marching cubes algorithm, which is used for visualizing isosurfaces.

Operation

After the iso-value was set for which the line is to be calculated, the data must be rasterized into a grid, provided that the record is not already located on a uniform lattice. The data can then be divided into a coarser grid. The cells of the coarse grid are carried out step by step.

For each grid cell is checked whether its vertices lie above or below the iso-value. Up to 16 cases occur, which can be attributed in consideration of symmetries on the following four:

  • Case 1: all corners greater than / less
  • Case 2: exactly one corner is higher / lower
  • Case 3: exactly two vertices with a common edge larger / smaller
  • Case 4: exactly two opposite corners of larger / smaller

In the fourth case can not be decided first, as the two Isoliniensegmente must pass through the cell. For this, the inside of the cell to be examined.

Case 2: All vertices lie up on a corner above (or below ) the iso-value.

Case 3: Two corners on an edge above or below the iso-value.

Case 4: The two opposite corners lie above or below the iso-value.

Solution for Case 4 depending on the values ​​within the cell.

Solution for Case 4 depending on the values ​​within the cell.

To be sampled finer the isoline, as permitted by the coarse grid, so you can divide in cases 2 to 4, the grid cell again and reapply the algorithm.

Edges, in which a terminal node to the iso-value and the other is below the iso-line of cut. The cutting position can be interpolated linearly, since the iso-value and the values ​​are known at the end nodes. For the calculation applies: with

The interface position is then.

Shown illustrates

Swell

  • Stefan Gumhold: Scientific Visualization. Figure. 2009 ( Lecture slides ).

Left

  • Better know to Algorithm - Marching Square - A very good English instructions
  • All 16 configurations of a cell
  • Implementation in Java

Credentials

  • Algorithm (computer graphics )
546156
de