Algorithm taken from: http://en.wikipedia.org/wiki/Marching_squares . See that web page for a thorough description and helpful illustrations. In short, however, Marching Squares takes a 2d array of numbers and generates isolines for specified values.

The data array generally contains measurements of a natural phenomenon, so that adjacent numbers have some relation to each other. For example, they might be terrain elevations, RF power from a transmitter, snow fall amounts, and so on.

Given a threshold, a copy of the data is made where each value is changed to 0 or 1 depending if the measurement is below or above it. The algorithm described below is applied one time for each isoline wanted. Each isoline is converted to Java GeneralPath instances, which are Shapes supporting holes and disconnected regions.

NOTE: data is first padded with a new row at top and another at bottom, as well as a new first and last column. The new rows and columns are set to one less than the smallest data value. This ensures that all isos will be closed polygons. All generated GeneralPaths can then be easily filled and drawn.

Taken from the Wikipedia page:

Basic Algorithm

Here are the steps of the algorithm:

Apply a threshold to the 2D field to make a binary image containing:

1 where the data value is above the isovalue 0 where the data value is below the isovalue

Every 2x2 block of pixels in the binary image forms a contouring cell, so the whole image is represented by a grid of such cells (shown in green in the picture below). Note that this contouring grid is one cell smaller in each direction than the original 2D field.

For each cell in the contouring grid:

  1. Compose the 4 bits at the corners of the cell to build a binary index:

walk around the cell in a clockwise direction appending the bit to the index, using bitwise OR and left-shift, from most significant bit at the top left, to least significant bit at the bottom left. The resulting 4-bit index can have 16 possible values in the range 0-15

  1. Use the cell index to access a pre-built lookup table with 16 entries

listing the edges needed to represent the cell (shown in the lower right part of the picture below).

  1. Apply linear interpolation between the original field data values to

find the exact position of the contour line along the edges of the cell.