Mercurial > dive4elements > gnv-client

comparison gnv-artifacts/src/main/java/de/intevation/gnv/raster/Vectorizer.java @ 424:21fbd254db71

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added support for converting 2D rasters into polygons. gnv-artifacts/trunk@472 c6561f87-3c4e-4783-a992-168aeb5c3f6f
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 21 Dec 2009 18:00:54 +0000
parents
children 6642ab6c583c
comparison
equal deleted inserted replaced
423:2402173a1490 424:21fbd254db71
1 package de.intevation.gnv.raster;
2
3 import java.util.BitSet;
4 import java.util.List;
5 import java.util.ArrayList;
6
7 import gnu.trove.TIntStack;
8 import gnu.trove.TIntObjectHashMap;
9
10 /**
11 * @author Sascha L. Teichmann (sascha.teichmann@intevation.de)
12 */
13 public class Vectorizer
14 {
15 public interface RingsHandler {
16
17 void handleRings(List rings, int value, int width);
18
19 } // interface RingsHandler
20
21 public static final class Edge {
22
23 public Edge prev;
24 public Edge next;
25
26 public int a;
27 public int b;
28
29 public Edge() {
30 }
31
32 public Edge(int a, int b) {
33 this.a = a;
34 this.b = b;
35 }
36
37 public void chain(Edge other, int found) {
38
39 if (found == a) {
40 other.next = this;
41 prev = other;
42 return;
43 }
44
45 if (found == b) {
46 next = other;
47 other.prev = this;
48 return;
49 }
50
51 throw new IllegalStateException("cannot chain");
52 }
53
54 public boolean isComplete() {
55 Edge current = this;
56 do {
57 if (current.prev == null || current.next == null) {
58 return false;
59 }
60 current = current.next;
61 }
62 while (current != this);
63 return true;
64 }
65
66 public int length() {
67 int length = 0;
68 Edge current = this;
69 do { ++length; } while ((current = current.next) != this);
70 return length;
71 }
72 } // class Edge
73
74 protected static Edge simplify(Edge edge, int width) {
75
76 Edge e1 = edge;
77 Edge e2 = edge.next;
78 Edge e3 = e2.next;
79
80 int length = edge.length();
81
82 int count = 0;
83
84 do {
85 int e1x = e1.a % width;
86 int e1y = e1.a / width;
87 int e2x = e2.a % width;
88 int e2y = e2.a / width;
89 int e3x = e3.a % width;
90 int e3y = e3.a / width;
91
92 if ((e1x == e2x && e2x == e3x && e1x == e3x)
93 || (e1y == e2y && e2y == e3y && e1y == e3y)) {
94 e1.next = e3;
95 e3.prev = e1;
96 e2 = e3;
97 e3 = e2.next;
98 count = 0;
99 --length;
100 }
101 else {
102 e1 = e1.next;
103 e2 = e2.next;
104 e3 = e3.next;
105 ++count;
106 }
107 }
108 while (count < length + 2);
109
110 return e1;
111 }
112
113 protected int [] raster;
114 protected int width;
115 protected TIntObjectHashMap openEdges;
116 protected ArrayList rings;
117
118 public Vectorizer() {
119 openEdges = new TIntObjectHashMap();
120 rings = new ArrayList();
121 }
122
123 public Vectorizer(int [] raster, int width) {
124 this();
125 this.raster = raster;
126 this.width = width;
127 }
128
129 public static final int tl(int i, int w) {
130 int x = i % w;
131 int y = i / w;
132 return x + (w + 1)*y;
133 }
134
135 public static final int tr(int i, int w) {
136 return tl(i, w) + 1;
137 }
138
139 public static final int bl(int i, int w) {
140 return tl(i, w) + w + 1;
141 }
142
143 public static final int br(int i, int w) {
144 return bl(i, w) + 1;
145 }
146
147 protected void resetRegion() {
148 openEdges.clear();
149 rings.clear();
150 }
151
152 protected void emit(Edge edge) {
153
154 Edge otherA = (Edge)openEdges.remove(edge.a);
155
156 if (otherA != null) {
157 otherA.chain(edge, edge.a);
158 }
159
160 Edge otherB = (Edge)openEdges.remove(edge.b);
161 if (otherB != null) {
162 otherB.chain(edge, edge.b);
163 }
164
165 if (edge.isComplete()) {
166 rings.add(simplify(edge, width + 1));
167 }
168 else {
169 if (otherA == null) {
170 openEdges.put(edge.a, edge);
171 }
172 if (otherB == null) {
173 openEdges.put(edge.b, edge);
174 }
175 }
176 }
177
178 public int process(RingsHandler handler) {
179
180 BitSet visited = new BitSet(raster.length);
181
182 TIntStack stack = new TIntStack();
183
184 int regions = 0;
185
186
187 for (int i = 0; i < raster.length; ++i) {
188 if (visited.get(i)) {
189 continue;
190 }
191
192 ++regions;
193
194 int currentValue = raster[i];
195 visited.set(i);
196
197 int current = i;
198 visited.set(current);
199
200 for (;;) {
201 int tl = tl(current, width);
202 int tr = tr(current, width);
203 int bl = bl(current, width);
204 int br = br(current, width);
205
206 int t = current - width;
207
208 if (t < 0) {
209 emit(new Edge(tr, tl));
210 }
211 else {
212 if (raster[t] != currentValue) {
213 emit(new Edge(tr, tl));
214 }
215 else {
216 if (!visited.get(t)) {
217 visited.set(t);
218 stack.push(t);
219 }
220 }
221 }
222
223 int b = current + width;
224
225 if (b >= raster.length) {
226 emit(new Edge(bl, br));
227 }
228 else {
229 if (raster[b] != currentValue) {
230 emit(new Edge(bl, br));
231 }
232 else {
233 if (!visited.get(b)) {
234 visited.set(b);
235 stack.push(b);
236 }
237 }
238 }
239
240 int x = current % width;
241
242 if (x == 0) {
243 emit(new Edge(tl, bl));
244 }
245 else {
246 int l = current - 1;
247 if (raster[l] != currentValue) {
248 emit(new Edge(tl, bl));
249 }
250 else {
251 if (!visited.get(l)) {
252 visited.set(l);
253 stack.push(l);
254 }
255 }
256 }
257
258 if (x == width - 1) {
259 emit(new Edge(br, tr));
260 }
261 else {
262 int r = current + 1;
263 if (raster[r] != currentValue) {
264 emit(new Edge(br, tr));
265 }
266 else {
267 if (!visited.get(r)) {
268 visited.set(r);
269 stack.push(r);
270 }
271 }
272 }
273
274 if (stack.size() == 0) {
275 break;
276 }
277
278 current = stack.pop();
279 }
280
281 handler.handleRings(rings, currentValue, width + 1);
282
283 resetRegion();
284 }
285
286 return regions;
287 }
288 }
289 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8:
http://dive4elements.wald.intevation.org