Mercurial > dive4elements > gnv-client
view gnv-artifacts/src/main/java/de/intevation/gnv/raster/Vectorizer.java @ 1059:174f6eacd595
Added queries for TimeSeriesPoints using vectorvalues for verticalprofiles
gnv-artifacts/trunk@1138 c6561f87-3c4e-4783-a992-168aeb5c3f6f
author | Tim Englich <tim.englich@intevation.de> |
---|---|
date | Mon, 31 May 2010 08:20:17 +0000 |
parents | d766fe2d917a |
children | f953c9a559d8 |
line wrap: on
line source
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 :