--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gnv-artifacts/src/main/java/de/intevation/gnv/raster/Vectorizer.java	Fri Sep 28 12:13:56 2012 +0200
@@ -0,0 +1,508 @@
+package de.intevation.gnv.raster;
+
+import gnu.trove.TIntObjectHashMap;
+import gnu.trove.TIntStack;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.List;
+
+import org.apache.log4j.Logger;
+
+/**
+ * Instances of this class are able to vectorize 2D integer arrays
+ * with a kind of flood filling regions detection mechanism to
+ * a set of line strings and polygons.
+ *
+ * @author <a href="mailto:sascha.teichmann@intevation.de">Sascha L. Teichmann</a>
+ */
+public class Vectorizer
+{
+    private static Logger log = Logger.getLogger(Vectorizer.class);
+
+    /**
+     * Callback to process the found line strings and polygons.
+     */
+    public interface RingsHandler {
+
+        /**
+         * Called from {@link #process(de.intevation.gnv.raster.Vectorizer.RingsHandler) }
+         * to give the found features to the postprocessing backend.
+         * @param rings The found line strings and polygons.
+         * @param value The integer value of the raster surrounded by
+         * the features.
+         * @param width The width of the index space of the vectorized data.
+         * @param height The height of the index space of the vectorized data.
+         */
+        void handleRings(
+            List<Edge> rings,
+            int        value,
+            int        width,
+            int        height);
+
+    } // interface RingsHandler
+
+    /**
+     * Doubly link list representing a line string or a polygon.
+     */
+    public static final class Edge {
+
+        /**
+         * The predecessor.
+         */
+        public Edge prev;
+        /**
+         * The successor.
+         */
+        public Edge next;
+
+        /**
+         * Index of first vertex. To separate x and y values
+         * you have to divide the value by the width of the
+         * index space.
+         */
+        public int a;
+        /**
+         * Index of second vertex. To separate x and y values
+         * you have to divide the value by the width of the
+         * index space.
+         */
+        public int b;
+
+        /**
+         * Default constructor.
+         */
+        public Edge() {
+        }
+
+        /**
+         * Constructor to create Edge with two vertices.
+         * @param a The first vertex.
+         * @param b The second vertex.
+         */
+        public Edge(int a, int b) {
+            this.a = a;
+            this.b = b;
+        }
+
+        /**
+         * Copy constructor
+         * @param other The edge to clone.
+         */
+        public Edge(Edge other) {
+            a = other.a;
+            b = other.b;
+        }
+
+        /**
+         * Chain a given edge segment to this segment. The
+         * side of the chaining is determined by a given
+         * parameter.
+         * @param other The segment to chain.
+         * @param found The side to chain.
+         */
+        public void chain(Edge other, int found) {
+
+            if (found == a) {
+                other.next = this;
+                prev = other;
+                return;
+            }
+
+            if (found == b) {
+                next = other;
+                other.prev = this;
+                return;
+            }
+
+            throw new IllegalStateException("cannot chain");
+        }
+
+        /**
+         * Tells if the list is complete which means that this
+         * edge list is a closed polygon.
+         * @return true if edge list is closed else false.
+         */
+        public boolean isComplete() {
+            Edge current = this;
+            do {
+                if (current.prev == null || current.next == null) {
+                    return false;
+                }
+                current = current.next;
+            }
+            while (current != this);
+            return true;
+        }
+
+        /**
+         * Returns the length of this edge list in next direction.
+         * Segments in prev direction are ignored.
+         * @return The length of this edge list.
+         */
+        public int length() {
+            int length = 0;
+            Edge current = this;
+            do { ++length; }
+            while ((current = current.next) != null && current != this);
+            return length;
+        }
+
+        /**
+         * Returns the head node of this edge list.
+         * @return The head node.
+         */
+        public Edge head() {
+            Edge current = this;
+            while (current.prev != null) {
+                current = current.prev;
+            }
+            return current;
+        }
+
+        /**
+         * Hashes the two vertex indices to a common value.
+         * @return The hash value.
+         */
+        @Override
+        public int hashCode() {
+            return (a << 16) | b;
+        }
+
+        /**
+         * Two edges are considered equal if they have the same
+         * a and b vertices.
+         * @param other The other edge.
+         * @return true if the edges are equal else false.
+         */
+        @Override
+        public boolean equals(Object other) {
+            Edge e = (Edge)other;
+            return a == e.a && b == e.b;
+        }
+    } // class Edge
+
+    /**
+     * Simplifies a given edge list by removing collinear vertices.
+     * Attention: The original list is modified.
+     * @param edge The edge list to simplify.
+     * @param width The width of the vertex index space.
+     * @return The simplified list.
+     */
+    protected static Edge simplify(Edge edge, int width) {
+
+        Edge e1 = edge, start = edge;
+
+        int length = edge.length();
+
+        if (length < 2) {
+            return e1;
+        }
+
+        Edge e2 = edge.next;
+
+        int count = 0;
+
+        do {
+            int e1x = e1.a % width;
+            int e1y = e1.a / width;
+            int e2x = e1.b % width;
+            int e2y = e1.b / width;
+            int e3x = e2.b % width;
+            int e3y = e2.b / width;
+
+            if ((e1x == e2x && e2x == e3x && e1x == e3x)
+                    ||  (e1y == e2y && e2y == e3y && e1y == e3y)) {
+                e1.b = e2.b;
+                Edge removed = e1.next;
+                e1.next = e2.next;
+                if (e1.next != null) {
+                    e1.next.prev = e1;
+                }
+                e2 = e1.next;
+                count = 0;
+                --length;
+                if (removed == start) {
+                    start = e1;
+                }
+            }
+            else {
+                e1 = e1.next;
+                e2 = e2.next;
+                ++count;
+            }
+        }
+        while (length > 1 && e2 != null && count < length + 2);
+
+        return start;
+    }
+
+    /**
+     * The raster to be traced.
+     */
+    protected int []            raster;
+    /**
+     * The width of the raster.
+     */
+    protected int               width;
+    /**
+     * Map of the currently open edges.
+     */
+    protected TIntObjectHashMap openEdges;
+    /**
+     * List of rings already found.
+     */
+    protected List<Edge>        rings;
+    /**
+     * Flag to signal if a simplification should be performed
+     * after a ring is completed.
+     */
+    protected boolean           simplify;
+
+    /**
+     * Default constructor. Simplification is turned on.
+     */
+    public Vectorizer() {
+        this(true);
+    }
+
+    /**
+     * Constructor to create a vectorized with an explicit
+     * simplification policy.
+     * @param simplify Indicates if simplification should be
+     * used on ring completion.
+     */
+    public Vectorizer(boolean simplify) {
+        openEdges     = new TIntObjectHashMap();
+        rings         = new ArrayList<Edge>();
+        this.simplify = simplify;
+    }
+
+    /**
+     * Constructor to create a vectorizer with a given raster and width.
+     * Simplification is turn on.
+     * @param raster The raster to be vectorized.
+     * @param width The width of the raster.
+     */
+    public Vectorizer(int [] raster, int width) {
+        this(true, raster, width);
+    }
+
+    /**
+     * Constructor to create a vectorizer with a given raster, width
+     * and an explicit simplification policy.
+     * @param simplify Indicates if simplification should be
+     * used on ring completion.
+     * @param raster The raster to be vectorized.
+     * @param width The width of the raster.
+     */
+    public Vectorizer(boolean simplify, int [] raster, int width) {
+        this(simplify);
+        this.raster = raster;
+        this.width  = width;
+    }
+
+    /**
+     * Returns (x, y+1) for given vertex in index space.
+     * @param i vertex in index space.
+     * @param w width of raster.
+     * @return (x, y+1) in index space.
+     */
+    public static final int tl(int i, int w) {
+        int x = i % w;
+        int y = i / w;
+        return x + (w + 1)*y;
+    }
+
+    /**
+     * Returns tl(i, w) + 1.
+     * @param i vertex in index space.
+     * @param w width of raster.
+     * @return tl(i, w) + 1.
+     */
+    public static final int tr(int i, int w) {
+        return tl(i, w) + 1;
+    }
+
+    /**
+     * Returns tl(i, w) + w + 1.
+     * @param i vertex in index space.
+     * @param w width of raster.
+     * @return tl(i, w) + w + 1.
+     */
+    public static final int bl(int i, int w) {
+        return tl(i, w) + w + 1;
+    }
+
+    /**
+     * Returns bl(i, w) + 1.
+     * @param i vertex in index space.
+     * @param w width of raster.
+     * @return bl(i, w) + 1.
+     */
+    public static final int br(int i, int w) {
+        return bl(i, w) + 1;
+    }
+
+    /**
+     * Resets open resources after a set of features were found.
+     */
+    protected void resetRegion() {
+        openEdges.clear();
+        rings.clear();
+    }
+
+    /**
+     * Adds an edge to the map of open edges, joins it
+     * with its direct neighbors of if complete add the
+     * list to the complete features.
+     * @param edge
+     */
+    protected void emit(Edge edge) {
+
+        Edge otherA = (Edge)openEdges.remove(edge.a);
+        if (otherA != null) {
+            otherA.chain(edge, edge.a);
+        }
+
+        Edge otherB = (Edge)openEdges.remove(edge.b);
+        if (otherB != null) {
+            otherB.chain(edge, edge.b);
+        }
+
+        if (edge.isComplete()) {
+            rings.add(simplify ? simplify(edge, width + 1) : edge);
+        }
+        else {
+            if (otherA == null) {
+                openEdges.put(edge.a, edge);
+            }
+            if (otherB == null) {
+                openEdges.put(edge.b, edge);
+            }
+        }
+    }
+
+    /**
+     * Vectorize the raster. The found features are fed into
+     * the given ring handler.
+     * @param handler The RingHandler to postprocess the found features.
+     * @return The number of regions found.
+     */
+    public int process(RingsHandler handler) {
+
+        BitSet visited = new BitSet(raster.length);
+
+        TIntStack stack = new TIntStack();
+
+        int regions = 0;
+
+        int height = raster.length / width;
+
+        for (int i = 0; i < raster.length; ++i) {
+            if (visited.get(i)) {
+                continue;
+            }
+
+            ++regions;
+
+            int currentValue = raster[i];
+            visited.set(i);
+
+            int current = i;
+            visited.set(current);
+
+            for (;;) {
+                int tl = tl(current, width);
+                int tr = tr(current, width);
+                int bl = bl(current, width);
+                int br = br(current, width);
+
+                int t = current - width;
+
+                if (t < 0) {
+                    emit(new Edge(tr, tl));
+                }
+                else {
+                    if (raster[t] != currentValue) {
+                        emit(new Edge(tr, tl));
+                    }
+                    else {
+                        if (!visited.get(t)) {
+                            visited.set(t);
+                            stack.push(t);
+                        }
+                    }
+                }
+
+                int b = current + width;
+
+                if (b >= raster.length) {
+                    emit(new Edge(bl, br));
+                }
+                else {
+                    if (raster[b] != currentValue) {
+                        emit(new Edge(bl, br));
+                    }
+                    else {
+                        if (!visited.get(b)) {
+                            visited.set(b);
+                            stack.push(b);
+                        }
+                    }
+                }
+
+                int x = current % width;
+
+                if (x == 0) {
+                    emit(new Edge(tl, bl));
+                }
+                else {
+                    int l = current - 1;
+                    if (raster[l] != currentValue) {
+                        emit(new Edge(tl, bl));
+                    }
+                    else {
+                        if (!visited.get(l)) {
+                            visited.set(l);
+                            stack.push(l);
+                        }
+                    }
+                }
+
+                if (x == width - 1) {
+                    emit(new Edge(br, tr));
+                }
+                else {
+                    int r = current + 1;
+                    if (raster[r] != currentValue) {
+                        emit(new Edge(br, tr));
+                    }
+                    else {
+                        if (!visited.get(r)) {
+                            visited.set(r);
+                            stack.push(r);
+                        }
+                    }
+                }
+
+                if (stack.size() == 0) {
+                    break;
+                }
+
+                current = stack.pop();
+            }
+
+            handler.handleRings(
+                rings,
+                currentValue,
+                width + 1,
+                height + 1);
+
+            resetRegion();
+        }
+
+        return regions;
+    }
+}
+// vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :