Mercurial > dive4elements > gnv-client
comparison gnv-artifacts/src/main/java/de/intevation/gnv/raster/Vectorizer.java @ 424:21fbd254db71
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: |