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.

A diagram highlighting the coordinate system used in the implementation.

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.