source: osm/applications/editors/josm/plugins/utilsplugin/UtilsPlugin/SimplifyWayAction.java@ 5075

Last change on this file since 5075 was 5075, checked in by gabriel, 18 years ago

Import the latest upstream version of utilsplugin.
File size: 13.5 KB
Line 
1package UtilsPlugin;
2
3import static org.openstreetmap.josm.tools.I18n.tr;
4
5import java.awt.event.ActionEvent;
6import java.util.ArrayList;
7import java.util.Arrays;
8import java.util.Collection;
9import java.util.Comparator;
10import java.util.HashMap;
11import java.util.HashSet;
12import java.util.LinkedList;
13import java.util.List;
14
15import org.openstreetmap.josm.Main;
16import org.openstreetmap.josm.command.ChangeCommand;
17import org.openstreetmap.josm.command.Command;
18import org.openstreetmap.josm.command.DeleteCommand;
19import org.openstreetmap.josm.command.SequenceCommand;
20import org.openstreetmap.josm.data.SelectionChangedListener;
21import org.openstreetmap.josm.data.coor.LatLon;
22import org.openstreetmap.josm.data.osm.Node;
23import org.openstreetmap.josm.data.osm.OsmPrimitive;
24import org.openstreetmap.josm.data.osm.Segment;
25import org.openstreetmap.josm.data.osm.Way;
26import org.openstreetmap.josm.data.osm.visitor.Visitor;
27
28import org.openstreetmap.josm.data.osm.DataSet;
29import org.openstreetmap.josm.actions.JosmAction;
30
31/**
32 * Forgets the selected data, unless it is referenced by something.
33 *
34 * "Forgetting", as opposed to "deleting", means that the data is simply removed from JOSM, and
35 * not tagged as "to be deleted on server".
36 *
37 * - selected WAYS can always be forgotten.
38 * - selected SEGMENTS can be forgotten unless they are referenced by not-forgotten ways.
39 * - selected NODES can be forgotten unless they are referenced by not-forgotten segments.
40 */
41
42public class SimplifyWayAction extends JosmAction implements SelectionChangedListener {
43
44
45 private Way selectedWay = null;
46
47 /**
48 * Create a new SimplifyWayAction.
49 */
50 public SimplifyWayAction() {
51 super(tr("Simplify Way"), "simplify", tr("Delete low-information nodes from a way."), 0, 0, true);
52 try { Main.ds.addSelectionChangedListener(this); }
53 catch( NoSuchMethodError e )
54 {
55 try {
56 java.lang.reflect.Field f = DataSet.class.getDeclaredField("listeners");
57 ((Collection<SelectionChangedListener>)f.get(Main.ds)).add(this);
58// Main.ds.listeners.add(this);
59 } catch (Exception x) { System.out.println( e ); }
60 }
61 }
62
63 /**
64 * Called when the action is executed.
65 */
66 public void actionPerformed(ActionEvent e) {
67
68 Collection<OsmPrimitive> selection = Main.ds.getSelected();
69
70
71 Visitor selectVisitor = new Visitor(){
72 public void visit(Node n) {
73 }
74 public void visit(Segment s) {
75 }
76 public void visit(Way w) {
77 selectedWay = w;
78 }
79 };
80
81 for (OsmPrimitive p : selection)
82 p.visit(selectVisitor);
83
84 simplifyWay(selectedWay);
85 }
86
87 private class NodeRecord {
88 public boolean keep = false; // whether this node must be kept
89 public Node node; // the node
90 public NodeRecord previous; // the segment leading to this node
91 public double xte; // the cross-track error
92 public NodeRecord next;
93 }
94
95 /**
96 * Simplifies the given way by potentially removing nodes and segments.
97 *
98 * @param way
99 * @return true if simplification was successful (even if way was not changed)
100 * false if simplification was not possible (branching/unordered ways)
101 */
102 public boolean simplifyWay(Way way) {
103
104 // first build some structures that help us working with this way, assuming
105 // it might be very long, so we want to be efficient.
106
107 // a map holding one NodeRecord object for every node in the way, except
108 // the first node (which is never "simplified" anyway)
109 HashMap<Node,NodeRecord> nodeIndex = new HashMap<Node,NodeRecord>();
110
111 // a hash set containing all segments in this way, for fast is-in-way checks
112 HashSet<Segment> segmentIndex = new HashSet<Segment>();
113
114 // in addition to all this, we also have each NodeRecord pointing
115 // to the next one along the way, making a linked list.
116 NodeRecord firstNr = null;
117
118 // fill structures
119 NodeRecord prevNr = null;
120 for (Segment s : way.segments) {
121 if ((prevNr != null) && (!s.from.equals(prevNr.node))) {
122 // error
123 System.out.println("XXX err");
124 return false;
125 }
126 segmentIndex.add(s);
127 NodeRecord nr = new NodeRecord();
128 nr.node = s.to;
129 if (prevNr == null) {
130 nr.previous = new NodeRecord();
131 nr.previous.node = s.from;
132 // set "keep" on first node
133 nr.previous.keep = true;
134 firstNr = nr.previous;
135 firstNr.next = nr;
136 nodeIndex.put(s.from, nr.previous);
137 } else {
138 nr.previous = prevNr;
139 prevNr.next = nr;
140 }
141 nr.xte = 0;
142 nr.next = null;
143 prevNr = nr;
144 nodeIndex.put(s.to, nr);
145 }
146
147 // set "keep" on last node
148 prevNr.keep = true;
149
150 // check the current data set, and mark all nodes that are used by a segment
151 // not exclusively owned by the current way as "untouchable".
152 for (Segment s: Main.ds.segments) {
153 if (s.deleted) continue;
154 if (segmentIndex.contains(s)) continue; // these don't count
155 NodeRecord tmp;
156 tmp = nodeIndex.get(s.from); if (tmp != null) tmp.keep = true;
157 tmp = nodeIndex.get(s.to); if (tmp != null) tmp.keep = true;
158 }
159
160 for (Way w: Main.ds.ways) {
161 if (w.deleted) continue;
162 if (w.equals(way)) continue; // these don't count
163 for (Segment s: w.segments)
164 {
165 NodeRecord tmp;
166 tmp = nodeIndex.get(s.from); if (tmp != null) tmp.keep = true;
167 tmp = nodeIndex.get(s.to); if (tmp != null) tmp.keep = true;
168 }
169 }
170
171 // keep all nodes which have tags other than source and created_by
172 for (NodeRecord nr : nodeIndex.values()) {
173 Collection<String> keyset = nr.node.keySet();
174 keyset.remove("source");
175 keyset.remove("created_by");
176 if (!keyset.isEmpty()) nr.keep = true;
177 }
178
179 // compute cross-track error for all elements. cross-track error is the
180 // distance between a node and the nearest point on a line from the
181 // previous to the next node - that's the error you would introduce
182 // by removing the node.
183 for (NodeRecord r = firstNr; r.next != null; r = r.next) {
184 computeXte(r);
185 }
186
187 boolean stayInLoop = true;
188 double treshold = Double.parseDouble(Main.pref.get("simplify-way.max-error", "0.06"));
189 while(stayInLoop) {
190 NodeRecord[] sorted = new NodeRecord[nodeIndex.size()];
191 nodeIndex.values().toArray(sorted);
192 Arrays.sort(sorted, new Comparator<NodeRecord>() {
193 public int compare(NodeRecord a, NodeRecord b) {
194 return (a.xte < b.xte) ? -1 : (a.xte > b.xte) ? 1 : 0;
195 }
196 });
197
198 stayInLoop = false;
199 for (NodeRecord nr : sorted) {
200 if (nr.keep) continue;
201 if (nr.xte < treshold) {
202 // delete this node
203 nodeIndex.remove(nr.node);
204 if (nr == firstNr) {
205 firstNr = nr.next;
206 } else {
207 nr.previous.next = nr.next;
208 }
209 if (nr.next != null) {
210 nr.next.previous = nr.previous;
211 }
212 computeXte(nr.next);
213 computeXte(nr.previous);
214 stayInLoop = true;
215 }
216 break;
217 }
218 }
219
220 Segment currentOriginalSegment = null;
221 Segment currentModifiedSegment = null;
222 Way wayCopy = null;
223 int delCount = 0;
224 Collection<Command> cmds = new LinkedList<Command>();
225
226 for (Segment s : way.segments) {
227 if (currentOriginalSegment == null) {
228 currentOriginalSegment = s;
229 currentModifiedSegment = s;
230 continue;
231 }
232
233 if (nodeIndex.containsKey(s.from)) {
234 // the current remaining segment's "to" node is not
235 // deleted, so it may stay.
236 if (currentModifiedSegment != currentOriginalSegment) {
237 cmds.add(new ChangeCommand(currentOriginalSegment, currentModifiedSegment));
238 }
239 currentOriginalSegment = s;
240 currentModifiedSegment = s;
241 } else {
242 // the "to" node is to be deleted; delete segment and
243 // node
244 cmds.add(new DeleteCommand(Arrays.asList(new OsmPrimitive[]{s, s.from})));
245 delCount ++;
246 if (wayCopy == null) {
247 wayCopy = new Way(way);
248 }
249 wayCopy.segments.remove(s);
250 if (currentModifiedSegment == currentOriginalSegment) {
251 currentModifiedSegment = new Segment(currentOriginalSegment);
252 }
253 currentModifiedSegment.to = s.to;
254 }
255 }
256 if (currentModifiedSegment != currentOriginalSegment) {
257 cmds.add(new ChangeCommand(currentOriginalSegment, currentModifiedSegment));
258 }
259
260 if (wayCopy != null) {
261 cmds.add(new ChangeCommand(way, wayCopy));
262 Main.main.editLayer().add(new SequenceCommand(tr("Simplify Way (remove {0} nodes)", delCount), cmds));
263 }
264
265 return true;
266
267 }
268 public void selectionChanged(Collection<? extends OsmPrimitive> newSelection) {
269 setEnabled(!newSelection.isEmpty());
270 }
271
272 private static void computeXte(NodeRecord r) {
273 if ((r.previous == null) || (r.next == null)) {
274 r.xte = 0;
275 return;
276 }
277 Node prevNode = r.previous.node;
278 Node nextNode = r.next.node;
279 r.xte = radtomiles(linedist(prevNode.coor.lat(), prevNode.coor.lon(),
280 r.node.coor.lat(), r.node.coor.lon(),
281 nextNode.coor.lat(), nextNode.coor.lon()));
282 }
283
284 /* ----------------------------------------------------------------------
285 * Everything below this comment was converted from C to Java by Frederik
286 * Ramm. The original sources are the files grtcirc.c and smplrout.c from
287 * the gpsbabel source code (www.gpsbabel.org), which is under GPL. The
288 * relevant code portions have been written by Robert Lipe.
289 *
290 * Method names have been left unchanged where possible.
291 */
292
293 public static double EARTH_RAD = 6378137.0;
294 public static double radmiles = EARTH_RAD*100.0/2.54/12.0/5280.0;
295
296 public static double[] crossproduct(double[] v1, double[] v2) {
297 double[] rv = new double[3];
298 rv[0] = v1[1]*v2[2]-v2[1]*v1[2];
299 rv[1] = v1[2]*v2[0]-v2[2]*v1[0];
300 rv[2] = v1[0]*v2[1]-v1[1]*v2[0];
301 return rv;
302 }
303
304 public static double dotproduct(double[] v1, double[] v2) {
305 return v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2];
306 }
307
308 public static double radtomiles(double rads) {
309 return (rads*radmiles);
310 }
311
312 public static double radtometers(double rads) {
313 return (rads * EARTH_RAD);
314 }
315
316 public static double veclen(double[] vec) {
317 return Math.sqrt(vec[0]*vec[0]+vec[1]*vec[1]+vec[2]*vec[2]);
318 }
319
320 public static double gcdist(double lat1, double lon1, double lat2, double lon2)
321 {
322 double res;
323 double sdlat, sdlon;
324
325 sdlat = Math.sin((lat1 - lat2) / 2.0);
326 sdlon = Math.sin((lon1 - lon2) / 2.0);
327
328 res = Math.sqrt(sdlat * sdlat + Math.cos(lat1) * Math.cos(lat2) * sdlon * sdlon);
329
330 if (res > 1.0) {
331 res = 1.0;
332 } else if (res < -1.0) {
333 res = -1.0;
334 }
335
336 res = Math.asin(res);
337 return 2.0 * res;
338 }
339
340 static double linedist(double lat1, double lon1, double lat2, double lon2, double lat3, double lon3) {
341
342 double dot;
343
344 /* degrees to radians */
345 lat1 = Math.toRadians(lat1); lon1 = Math.toRadians(lon1);
346 lat2 = Math.toRadians(lat2); lon2 = Math.toRadians(lon2);
347 lat3 = Math.toRadians(lat3); lon3 = Math.toRadians(lon3);
348
349 /* polar to ECEF rectangular */
350 double[] v1 = new double[3];
351 double[] v2 = new double[3];
352 double[] v3 = new double[3];
353 v1[0] = Math.cos(lon1)*Math.cos(lat1); v1[1] = Math.sin(lat1); v1[2] = Math.sin(lon1)*Math.cos(lat1);
354 v2[0] = Math.cos(lon2)*Math.cos(lat2); v2[1] = Math.sin(lat2); v2[2] = Math.sin(lon2)*Math.cos(lat2);
355 v3[0] = Math.cos(lon3)*Math.cos(lat3); v3[1] = Math.sin(lat3); v3[2] = Math.sin(lon3)*Math.cos(lat3);
356
357 /* 'va' is the axis; the line that passes through the center of the earth
358 * and is perpendicular to the great circle through point 1 and point 2
359 * It is computed by taking the cross product of the '1' and '2' vectors.*/
360 double[] va = crossproduct(v1, v2);
361 double la = veclen(va);
362
363 if (la != 0) {
364 va[0] /= la;
365 va[1] /= la;
366 va[2] /= la;
367
368 /* dot is the component of the length of '3' that is along the axis.
369 * What's left is a non-normalized vector that lies in the plane of
370 * 1 and 2. */
371
372 dot = dotproduct(v3, va);
373
374 double[] vp = new double[3];
375 vp[0]=v3[0]-dot*va[0];
376 vp[1]=v3[1]-dot*va[1];
377 vp[2]=v3[2]-dot*va[2];
378
379 double lp = veclen(vp);
380
381 if (lp != 0) {
382
383 /* After this, 'p' is normalized */
384 vp[0] /= lp;
385 vp[1] /= lp;
386 vp[2] /= lp;
387
388 double[] cp1 = crossproduct(v1, vp);
389 double dp1 = dotproduct(cp1, va);
390
391 double[] cp2 = crossproduct(v2, vp);
392 double dp2 = dotproduct(cp2, va);
393
394 if ( dp1 >= 0 && dp2 >= 0 ) {
395 /* rather than call gcdist and all its sines and cosines and
396 * worse, we can get the angle directly. It's the arctangent
397 * of the length of the component of vector 3 along the axis
398 * divided by the length of the component of vector 3 in the
399 * plane. We already have both of those numbers.
400 *
401 * atan2 would be overkill because lp and Math.abs are both
402 * known to be positive. */
403 return Math.atan(Math.abs(dot)/lp);
404 }
405
406 /* otherwise, get the distance from the closest endpoint */
407 double c1 = dotproduct(v1, vp);
408 double c2 = dotproduct(v2, vp);
409 dp1 = Math.abs(dp1);
410 dp2 = Math.abs(dp2);
411
412 /* This is a hack. d$n$ is proportional to the sine of the angle
413 * between point $n$ and point p. That preserves orderedness up
414 * to an angle of 90 degrees. c$n$ is proportional to the cosine
415 * of the same angle; if the angle is over 90 degrees, c$n$ is
416 * negative. In that case, we flop the sine across the y=1 axis
417 * so that the resulting value increases as the angle increases.
418 *
419 * This only works because all of the points are on a unit sphere. */
420
421 if (c1 < 0) {
422 dp1 = 2 - dp1;
423 }
424 if (c2 < 0) {
425 dp2 = 2 - dp2;
426 }
427
428 if (Math.abs(dp1) < Math.abs(dp2)) {
429 return gcdist(lat1,lon1,lat3,lon3);
430 } else {
431 return gcdist(lat2,lon2,lat3,lon3);
432 }
433 } else {
434 /* lp is 0 when 3 is 90 degrees from the great circle */
435 return Math.PI/2;
436 }
437 } else {
438 /* la is 0 when 1 and 2 are either the same point or 180 degrees apart */
439 dot = dotproduct(v1, v2);
440 if (dot >= 0) {
441 return gcdist(lat1,lon1,lat3,lon3);
442 } else {
443 return 0;
444 }
445 }
446 }
447}
Note: See TracBrowser for help on using the repository browser.