Marching squares
From Wikipedia, the free encyclopedia
Marching squares is a computer graphics algorithm that generates contour lines for a two-dimensional scalar field. It is similar to the three-dimensional marching cubes algorithm.
[edit] How it works
The algorithm can be understood by looking at a simpler version of it, used to trace the edge of an object. Such an "object" could be a set of pixels in an image with a distinct colour, for example. The image is divided up into a series of discrete cells - a raster image of pixels is already in this form. Each cell consists of a single value - either one value for the shape being traced, or another for the background. Lets call them white for the background, black for the object.
The cells are scanned, examining four adjacent cells at a time in a 2 x 2 grid. For any given position in the entire field, the 2 x 2 grid can be in one of 16 possible states. For example, if the grid is only over the background, all cells might be white or 0. If completely within the object, it would be all black. For positions at the edge of the object, the 2 x 2 grid yields other combinations.
The 1 of 16 states is used to determine which location in the image is examined next. For example, if we have scanned from left to right across the background until we hit the left edge of the object, we might have the 2 grid cells on the left being white, the two on the right being black. This state (which we might call 0110, or 6) is used to index a table which tells us where to move next. In this case it might return 0 for the x direction, and +1 for the y direction, meaning the test grid is moved down by one cell. This process is repeated, with each combination of black and white used to "steer" the grid such that it follows the edge of the object, maintaining its state with some combination of black and white cells. Once the test grid reaches its starting point (or the array boundary), the object has been fully traced and the loop terminates.
This simple version of the algorithm can be generalised to follow any nominated contour in an array of data points. In this case, each data point usually has a threshold value applied to it (the contour value) such that the test grid is set to one of 16 distinct states, rather than working on the real data value directly which would be inefficient and unnecessary.
