sascha@424: package de.intevation.gnv.raster; sascha@424: sascha@424: import java.util.BitSet; sascha@424: import java.util.List; sascha@424: import java.util.ArrayList; sascha@424: sascha@424: import gnu.trove.TIntStack; sascha@424: import gnu.trove.TIntObjectHashMap; sascha@424: sascha@424: /** sascha@424: * @author Sascha L. Teichmann (sascha.teichmann@intevation.de) sascha@424: */ sascha@424: public class Vectorizer sascha@424: { sascha@424: public interface RingsHandler { sascha@424: sascha@436: void handleRings( sascha@436: List rings, sascha@436: int value, sascha@436: int width, sascha@436: int height); sascha@424: sascha@424: } // interface RingsHandler sascha@424: sascha@424: public static final class Edge { sascha@424: sascha@424: public Edge prev; sascha@424: public Edge next; sascha@424: sascha@424: public int a; sascha@424: public int b; sascha@424: sascha@424: public Edge() { sascha@424: } sascha@424: sascha@424: public Edge(int a, int b) { sascha@424: this.a = a; sascha@424: this.b = b; sascha@424: } sascha@424: sascha@437: public Edge(Edge other) { sascha@437: a = other.a; sascha@437: b = other.b; sascha@437: } sascha@437: sascha@424: public void chain(Edge other, int found) { sascha@424: sascha@424: if (found == a) { sascha@424: other.next = this; sascha@424: prev = other; sascha@424: return; sascha@424: } sascha@424: sascha@424: if (found == b) { sascha@424: next = other; sascha@424: other.prev = this; sascha@424: return; sascha@424: } sascha@424: sascha@424: throw new IllegalStateException("cannot chain"); sascha@424: } sascha@424: sascha@424: public boolean isComplete() { sascha@424: Edge current = this; sascha@424: do { sascha@424: if (current.prev == null || current.next == null) { sascha@424: return false; sascha@424: } sascha@424: current = current.next; sascha@424: } sascha@424: while (current != this); sascha@424: return true; sascha@424: } sascha@424: sascha@424: public int length() { sascha@424: int length = 0; sascha@424: Edge current = this; sascha@437: do { ++length; } sascha@437: while ((current = current.next) != null && current != this); sascha@424: return length; sascha@424: } sascha@436: sascha@436: public int hashCode() { sascha@436: return (a << 16) | b; sascha@436: } sascha@436: sascha@436: public boolean equals(Object other) { sascha@436: Edge e = (Edge)other; sascha@436: return a == e.a && b == e.b; sascha@436: } sascha@424: } // class Edge sascha@424: sascha@424: protected static Edge simplify(Edge edge, int width) { sascha@424: sascha@424: Edge e1 = edge; sascha@424: Edge e2 = edge.next; sascha@424: Edge e3 = e2.next; sascha@424: sascha@424: int length = edge.length(); sascha@424: sascha@437: if (length < 2) { sascha@437: return e1; sascha@437: } sascha@437: sascha@424: int count = 0; sascha@424: sascha@424: do { sascha@424: int e1x = e1.a % width; sascha@424: int e1y = e1.a / width; sascha@424: int e2x = e2.a % width; sascha@424: int e2y = e2.a / width; sascha@424: int e3x = e3.a % width; sascha@424: int e3y = e3.a / width; sascha@424: sascha@424: if ((e1x == e2x && e2x == e3x && e1x == e3x) sascha@424: || (e1y == e2y && e2y == e3y && e1y == e3y)) { sascha@424: e1.next = e3; sascha@424: e3.prev = e1; sascha@424: e2 = e3; sascha@424: e3 = e2.next; sascha@424: count = 0; sascha@424: --length; sascha@424: } sascha@424: else { sascha@424: e1 = e1.next; sascha@424: e2 = e2.next; sascha@424: e3 = e3.next; sascha@424: ++count; sascha@424: } sascha@424: } sascha@437: while (length > 1 && count < length + 2); sascha@424: sascha@424: return e1; sascha@424: } sascha@424: sascha@424: protected int [] raster; sascha@424: protected int width; sascha@424: protected TIntObjectHashMap openEdges; sascha@436: protected List rings; sascha@436: protected boolean simplify; sascha@424: sascha@424: public Vectorizer() { sascha@436: this(true); sascha@436: } sascha@436: sascha@436: public Vectorizer(boolean simplify) { sascha@436: openEdges = new TIntObjectHashMap(); sascha@436: rings = new ArrayList(); sascha@436: this.simplify = simplify; sascha@424: } sascha@424: sascha@424: public Vectorizer(int [] raster, int width) { sascha@424: this(); sascha@424: this.raster = raster; sascha@424: this.width = width; sascha@424: } sascha@424: sascha@424: public static final int tl(int i, int w) { sascha@424: int x = i % w; sascha@424: int y = i / w; sascha@424: return x + (w + 1)*y; sascha@424: } sascha@424: sascha@424: public static final int tr(int i, int w) { sascha@424: return tl(i, w) + 1; sascha@424: } sascha@424: sascha@424: public static final int bl(int i, int w) { sascha@424: return tl(i, w) + w + 1; sascha@424: } sascha@424: sascha@424: public static final int br(int i, int w) { sascha@424: return bl(i, w) + 1; sascha@424: } sascha@424: sascha@424: protected void resetRegion() { sascha@424: openEdges.clear(); sascha@424: rings.clear(); sascha@424: } sascha@424: sascha@424: protected void emit(Edge edge) { sascha@424: sascha@424: Edge otherA = (Edge)openEdges.remove(edge.a); sascha@424: if (otherA != null) { sascha@424: otherA.chain(edge, edge.a); sascha@424: } sascha@424: sascha@424: Edge otherB = (Edge)openEdges.remove(edge.b); sascha@424: if (otherB != null) { sascha@424: otherB.chain(edge, edge.b); sascha@424: } sascha@424: sascha@424: if (edge.isComplete()) { sascha@436: rings.add(simplify ? simplify(edge, width + 1) : edge); sascha@424: } sascha@424: else { sascha@424: if (otherA == null) { sascha@424: openEdges.put(edge.a, edge); sascha@424: } sascha@424: if (otherB == null) { sascha@424: openEdges.put(edge.b, edge); sascha@424: } sascha@424: } sascha@424: } sascha@424: sascha@424: public int process(RingsHandler handler) { sascha@424: sascha@424: BitSet visited = new BitSet(raster.length); sascha@424: sascha@424: TIntStack stack = new TIntStack(); sascha@424: sascha@424: int regions = 0; sascha@424: sascha@436: int height = raster.length / width; sascha@424: sascha@424: for (int i = 0; i < raster.length; ++i) { sascha@424: if (visited.get(i)) { sascha@424: continue; sascha@424: } sascha@424: sascha@424: ++regions; sascha@424: sascha@424: int currentValue = raster[i]; sascha@424: visited.set(i); sascha@424: sascha@424: int current = i; sascha@424: visited.set(current); sascha@424: sascha@424: for (;;) { sascha@424: int tl = tl(current, width); sascha@424: int tr = tr(current, width); sascha@424: int bl = bl(current, width); sascha@424: int br = br(current, width); sascha@424: sascha@424: int t = current - width; sascha@424: sascha@424: if (t < 0) { sascha@424: emit(new Edge(tr, tl)); sascha@424: } sascha@424: else { sascha@424: if (raster[t] != currentValue) { sascha@424: emit(new Edge(tr, tl)); sascha@424: } sascha@424: else { sascha@424: if (!visited.get(t)) { sascha@424: visited.set(t); sascha@424: stack.push(t); sascha@424: } sascha@424: } sascha@424: } sascha@424: sascha@424: int b = current + width; sascha@424: sascha@424: if (b >= raster.length) { sascha@424: emit(new Edge(bl, br)); sascha@424: } sascha@424: else { sascha@424: if (raster[b] != currentValue) { sascha@424: emit(new Edge(bl, br)); sascha@424: } sascha@424: else { sascha@424: if (!visited.get(b)) { sascha@424: visited.set(b); sascha@424: stack.push(b); sascha@424: } sascha@424: } sascha@424: } sascha@424: sascha@424: int x = current % width; sascha@424: sascha@424: if (x == 0) { sascha@424: emit(new Edge(tl, bl)); sascha@424: } sascha@424: else { sascha@424: int l = current - 1; sascha@424: if (raster[l] != currentValue) { sascha@424: emit(new Edge(tl, bl)); sascha@424: } sascha@424: else { sascha@424: if (!visited.get(l)) { sascha@424: visited.set(l); sascha@424: stack.push(l); sascha@424: } sascha@424: } sascha@424: } sascha@424: sascha@424: if (x == width - 1) { sascha@424: emit(new Edge(br, tr)); sascha@424: } sascha@424: else { sascha@424: int r = current + 1; sascha@424: if (raster[r] != currentValue) { sascha@424: emit(new Edge(br, tr)); sascha@424: } sascha@424: else { sascha@424: if (!visited.get(r)) { sascha@424: visited.set(r); sascha@424: stack.push(r); sascha@424: } sascha@424: } sascha@424: } sascha@424: sascha@424: if (stack.size() == 0) { sascha@424: break; sascha@424: } sascha@424: sascha@424: current = stack.pop(); sascha@424: } sascha@424: sascha@436: handler.handleRings( sascha@436: rings, sascha@436: currentValue, sascha@436: width + 1, sascha@436: height + 1); sascha@424: sascha@424: resetRegion(); sascha@424: } sascha@424: sascha@424: return regions; sascha@424: } sascha@424: } sascha@424: // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8: