dive4elements/gnv-client: gnv-artifacts/src/main/java/de/intevation/gnv/raster/Vectorizer.java comparison

comparison gnv-artifacts/src/main/java/de/intevation/gnv/raster/Vectorizer.java @ 1119:7c4f81f74c47

merged gnv-artifacts

author	Thomas Arendsen Hein <thomas@intevation.de>
date	Fri, 28 Sep 2012 12:14:00 +0200
parents	f953c9a559d8
children

comparison

equal deleted inserted replaced

-:fca4b5eb8d2f
+:7c4f81f74c47
+/*
+* Copyright (c) 2010 by Intevation GmbH
+*
+* This program is free software under the LGPL (>=v2.1)
+* Read the file LGPL.txt coming with the software for details
+* or visit http://www.gnu.org/licenses/ if it does not exist.
+*/
+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 :

Mercurial > dive4elements > gnv-client

comparison gnv-artifacts/src/main/java/de/intevation/gnv/raster/Vectorizer.java @ 1119:7c4f81f74c47