# Marching Squares Implementation

This is an entirely straightforward implementation of the classic marching squares algorithm in Java (see http://en.wikipedia.org/wiki/Marching_squares for an introduction to the algorithm).

It consists of the following three classes, the source for which I am placing in the public domain:

• Direction - an enumeration of basic directions.
• Path - a sequence of directions rooted in the plane.
• MarchingSquares - implements the algorithm.

## Usage Example

The code anticipates that data will have been pre-thresholded into zero and non-zero byte values. Given a matrix of such values (supplied as a byte array) the code can find perimeters between regions of zero and non-zero values.

```byte[] example = new byte[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }; MarchingSquares ms = new MarchingSquares(5,6, example); Path path = ms.identifyPerimeter(); //the path returned will be [S, S, E, S, E, N, N, N, W, W] //the origin of the path being the point (2,-2) ```

The diagram below shows exhibits the coordinate system used by the algorithm.

For more information see the comments in the supplied code.

## Notes

• The code could easily be modified to work with much more general data (eg. non-thresholded data) by hiding the data behind an interface, I happen to need greater efficiency.
• Data beyond the boundary of the data array are assumed to be identically zero.
• There is a really nasty suprise waiting for anyone who doesn't pay attention to this documentation... The origin of the path returned by the algorithm is in plane coordinates (y-axis up), but the supplied data is expected to be in screen coordinates (y-axis down).. What this means in practice is simply that the initial y coordinate comes back out of the algorithm negated. See the diagram above.
• The code as supplied requires generics, but it would be a very simple matter to strip these out.