source: osm/applications/editors/josm/plugins/utilsplugin2/src/org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/ReplaceGeometryUtils.java@ 35681

Last change on this file since 35681 was 35681, checked in by GerdP, 3 years ago

improve javadoc
File size: 22.2 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.plugins.utilsplugin2.replacegeometry;
3
4import static org.openstreetmap.josm.tools.I18n.tr;
5
6import java.awt.geom.Area;
7import java.util.AbstractMap;
8import java.util.ArrayList;
9import java.util.Arrays;
10import java.util.Collection;
11import java.util.Collections;
12import java.util.HashMap;
13import java.util.HashSet;
14import java.util.LinkedList;
15import java.util.List;
16import java.util.Map;
17import java.util.Set;
18import java.util.stream.Collectors;
19
20import javax.swing.JOptionPane;
21
22import org.openstreetmap.josm.actions.MergeNodesAction;
23import org.openstreetmap.josm.command.ChangeNodesCommand;
24import org.openstreetmap.josm.command.ChangePropertyCommand;
25import org.openstreetmap.josm.command.Command;
26import org.openstreetmap.josm.command.DeleteCommand;
27import org.openstreetmap.josm.command.MoveCommand;
28import org.openstreetmap.josm.data.coor.LatLon;
29import org.openstreetmap.josm.data.osm.DefaultNameFormatter;
30import org.openstreetmap.josm.data.osm.Node;
31import org.openstreetmap.josm.data.osm.OsmPrimitive;
32import org.openstreetmap.josm.data.osm.Relation;
33import org.openstreetmap.josm.data.osm.RelationMember;
34import org.openstreetmap.josm.data.osm.TagCollection;
35import org.openstreetmap.josm.data.osm.Way;
36import org.openstreetmap.josm.gui.MainApplication;
37import org.openstreetmap.josm.gui.Notification;
38import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
39import org.openstreetmap.josm.spi.preferences.Config;
40import org.openstreetmap.josm.tools.Logging;
41import org.openstreetmap.josm.tools.UserCancelException;
42
43import edu.princeton.cs.algs4.AssignmentProblem;
44
45/**
46 * Utilities for Replace Geometry
47 * @author joshdoe
48 */
49public final class ReplaceGeometryUtils {
50
51 private ReplaceGeometryUtils() {
52 // Hide default constructor for utilities classes
53 }
54
55 /**
56 * Replace new or uploaded object with new object
57 * @param firstObject an object
58 * @param secondObject another object
59 * @return (in case of success) a command to update the geometry of one primitive and remove the other
60 */
61 public static ReplaceGeometryCommand buildReplaceWithNewCommand(OsmPrimitive firstObject, OsmPrimitive secondObject) {
62 if (firstObject instanceof Node && secondObject instanceof Node) {
63 return buildReplaceNodeWithNewCommand((Node) firstObject, (Node) secondObject);
64 } else if (firstObject instanceof Way && secondObject instanceof Way) {
65 return buildReplaceWayWithNewCommand(Arrays.asList((Way) firstObject, (Way) secondObject));
66 } else if (firstObject instanceof Node) {
67 return buildUpgradeNodeCommand((Node) firstObject, secondObject);
68 } else if (secondObject instanceof Node) {
69 return buildUpgradeNodeCommand((Node) secondObject, firstObject);
70 } else {
71 throw new IllegalArgumentException(
72 tr("This tool can only replace a node, upgrade a node to a way or a multipolygon, or replace a way with a way."));
73 }
74 }
75
76 /**
77 * Replace subjectObject geometry with referenceObject geometry and merge tags
78 * and relation memberships.
79 * @param subjectObject object to modify
80 * @param referenceSubject object that gives new geometry and is removed
81 * @return (in case of success) a command to update the geometry of fist object and remove the other
82 */
83 public static ReplaceGeometryCommand buildReplaceCommand(OsmPrimitive subjectObject, OsmPrimitive referenceSubject) {
84 if (subjectObject instanceof Node && referenceSubject instanceof Node) {
85 return buildReplaceNodeCommand((Node) subjectObject, (Node) referenceSubject);
86 } else if (subjectObject instanceof Way && referenceSubject instanceof Way) {
87 return buildReplaceWayCommand((Way) subjectObject, (Way) referenceSubject);
88 } else if (subjectObject instanceof Node) {
89 return buildUpgradeNodeCommand((Node) subjectObject, referenceSubject);
90 } else if (referenceSubject instanceof Node) {
91 // TODO: fix this illogical reversal?
92 return buildUpgradeNodeCommand((Node) referenceSubject, subjectObject);
93 } else {
94 throw new IllegalArgumentException(
95 tr("This tool can only replace a node, upgrade a node to a way or a multipolygon, or replace a way with a way."));
96 }
97 }
98
99 /**
100 * Replace a new or uploaded node with a new node
101 * @param firstNode a node
102 * @param secondNode another node
103 * @return (in case of success) a command to update the geometry of one primitive and remove the other
104 */
105 public static ReplaceGeometryCommand buildReplaceNodeWithNewCommand(Node firstNode, Node secondNode) {
106 if (firstNode.isNew() && !secondNode.isNew())
107 return buildReplaceNodeCommand(secondNode, firstNode);
108 else if (!firstNode.isNew() && secondNode.isNew())
109 return buildReplaceNodeCommand(firstNode, secondNode);
110 else
111 // both nodes are new OR uploaded, act like MergeNodes, moving first
112 // node to second
113 return buildReplaceNodeCommand(firstNode, secondNode);
114 }
115
116 /**
117 * Replace a node with another node (similar to MergeNodesAction)
118 * @param subjectNode node to be replaced
119 * @param referenceNode node with greater spatial quality
120 * @return command to replace node or null if user cancelled
121 */
122 public static ReplaceGeometryCommand buildReplaceNodeCommand(Node subjectNode, Node referenceNode) {
123 if (!subjectNode.getParentWays().isEmpty()) {
124 throw new ReplaceGeometryException(tr("Node belongs to way(s), cannot replace."));
125 }
126 // FIXME: handle different layers
127 List<Command> commands = new ArrayList<>();
128 Command c = MergeNodesAction.mergeNodes(
129 Arrays.asList(subjectNode, referenceNode), referenceNode);
130 if (c == null) {
131 // User cancelled
132 return null;
133 }
134 commands.add(c);
135
136 return new ReplaceGeometryCommand(
137 tr("Replace geometry for node {0}", subjectNode.getDisplayName(DefaultNameFormatter.getInstance())),
138 commands);
139 }
140
141 /**
142 * Upgrade a node to a way or multipolygon
143 *
144 * @param subjectNode node to be replaced
145 * @param referenceObject object with greater spatial quality
146 * @return command to replace
147 */
148 public static ReplaceGeometryCommand buildUpgradeNodeCommand(Node subjectNode, OsmPrimitive referenceObject) {
149 if (!subjectNode.getParentWays().isEmpty()) {
150 throw new ReplaceGeometryException(tr("Node belongs to way(s), cannot replace."));
151 }
152
153 if (referenceObject instanceof Relation && !((Relation) referenceObject).isMultipolygon()) {
154 throw new ReplaceGeometryException(tr("Relation is not a multipolygon, cannot be used as a replacement."));
155 }
156
157 Node nodeToReplace = null;
158 // see if we need to replace a node in the replacement way to preserve connection in history
159 if (!subjectNode.isNew()) {
160 // Prepare a list of nodes that are not important
161 Collection<Node> nodePool = new HashSet<>();
162 if (referenceObject instanceof Way) {
163 nodePool.addAll(getUnimportantNodes((Way) referenceObject));
164 } else if (referenceObject instanceof Relation) {
165 for (RelationMember member : ((Relation) referenceObject).getMembers()) {
166 if (("outer".equals(member.getRole()) || "inner".equals(member.getRole()))
167 && member.isWay()) {
168 // TODO: could consider more nodes, such as nodes that are members of other ways,
169 // just need to replace occurences in all referrers
170 nodePool.addAll(getUnimportantNodes(member.getWay()));
171 }
172 }
173 } else {
174 assert false;
175 }
176 // see #8396: first try to find nearest new node
177 nodeToReplace = findNearestNode(subjectNode, nodePool.stream().filter(Node::isNew).collect(Collectors.toList()));
178 if (nodeToReplace == null) {
179 nodeToReplace = findNearestNode(subjectNode, nodePool);
180 }
181 }
182
183 List<Command> commands = new ArrayList<>();
184 AbstractMap<String, String> nodeTags = subjectNode.getKeys();
185
186 // merge tags
187 try {
188 commands.addAll(getTagConflictResolutionCommands(subjectNode, referenceObject));
189 } catch (UserCancelException e) {
190 // user cancelled tag merge dialog
191 return null;
192 }
193
194 // replace sacrificial node in way with node that is being upgraded
195 if (nodeToReplace != null) {
196 // node should only have one parent, a way
197 Way parentWay = (Way) nodeToReplace.getReferrers().get(0);
198 List<Node> wayNodes = parentWay.getNodes();
199 int idx = wayNodes.indexOf(nodeToReplace);
200 wayNodes.set(idx, subjectNode);
201 if (idx == 0 && parentWay.isClosed()) {
202 // node is at start/end of way
203 wayNodes.set(wayNodes.size() - 1, subjectNode);
204 }
205 commands.add(new ChangeNodesCommand(parentWay, wayNodes));
206 commands.add(new MoveCommand(subjectNode, nodeToReplace.getCoor()));
207 commands.add(new DeleteCommand(nodeToReplace));
208
209 // delete tags from node
210 if (!nodeTags.isEmpty()) {
211 for (String key : nodeTags.keySet()) {
212 commands.add(new ChangePropertyCommand(subjectNode, key, null));
213 }
214
215 }
216 } else {
217 // no node to replace, so just delete the original node
218 commands.add(new DeleteCommand(subjectNode));
219 }
220
221 MainApplication.getLayerManager().getEditDataSet().setSelected(referenceObject);
222
223 return new ReplaceGeometryCommand(
224 tr("Replace geometry for node {0}", subjectNode.getDisplayName(DefaultNameFormatter.getInstance())),
225 commands);
226 }
227
228 public static ReplaceGeometryCommand buildReplaceWayWithNewCommand(List<Way> selection) {
229 // determine which way will be replaced and which will provide the geometry
230 boolean overrideNewCheck = false;
231 int idxNew = selection.get(0).isNew() ? 0 : 1;
232 if (selection.get(1-idxNew).isNew()) {
233 // compute the nodes which are not shared by both ways
234 Set<Node> s0OnlyNodes = getDistinctNodes(selection.get(0), selection.get(1));
235 Set<Node> s1OnlyNodes = getDistinctNodes(selection.get(1), selection.get(0));
236
237 boolean hasNewS0 = s0OnlyNodes.stream().anyMatch(Node::isNew);
238 boolean hasNewS1 = s1OnlyNodes.stream().anyMatch(Node::isNew);
239 if (hasNewS0 != hasNewS1) {
240 // OK: one way doesn't have new nodes which don't appear in both ways
241 overrideNewCheck = true;
242 if (hasNewS1) {
243 idxNew = 1;
244 }
245 }
246 }
247 Way referenceWay = selection.get(idxNew);
248 Way subjectWay = selection.get(1 - idxNew);
249
250 String msg = null;
251 if (!subjectWay.isNew() && !referenceWay.isNew()) {
252 msg = tr("Please select one way that exists in the database and one new way with correct geometry.");
253 } else if (!overrideNewCheck && (subjectWay.isNew() || !referenceWay.isNew())) {
254 msg = tr("Both ways are new and have new nodes, cannot decide which one has the correct geometry.");
255 }
256 if (msg != null) {
257 throw new ReplaceGeometryException(msg);
258 }
259 return buildReplaceWayCommand(subjectWay, referenceWay);
260 }
261
262 /**
263 * Replace geometry of subjectWay by that of referenceWay. Tries to keep the history of nodes.
264 * @param subjectWay way to modify
265 * @param referenceWay way to remove
266 * @return Command to replace geometry or null if user cancelled
267 */
268 public static ReplaceGeometryCommand buildReplaceWayCommand(Way subjectWay, Way referenceWay) {
269
270 Area a = MainApplication.getLayerManager().getEditDataSet().getDataSourceArea();
271 if (!isInArea(subjectWay, a) || !isInArea(referenceWay, a)) {
272 throw new ReplaceGeometryException(tr("The ways must be entirely within the downloaded area."));
273 }
274
275 if (hasImportantNode(referenceWay, subjectWay)) {
276 throw new ReplaceGeometryException(
277 tr("The way to be replaced cannot have any nodes with properties or relation memberships unless they belong to both ways."));
278 }
279
280 List<Command> commands = new ArrayList<>();
281
282 // merge tags
283 try {
284 commands.addAll(getTagConflictResolutionCommands(referenceWay, subjectWay));
285 } catch (UserCancelException e) {
286 // user cancelled tag merge dialog
287 Logging.trace(e);
288 return null;
289 }
290
291 // Prepare a list of nodes that are not used anywhere except in the way
292 List<Node> nodePool = getUnimportantNodes(subjectWay);
293
294 // And the same for geometry, list nodes that can be freely deleted
295 List<Node> geometryPool = new LinkedList<>();
296 for (Node node : referenceWay.getNodes()) {
297 List<OsmPrimitive> referrers = node.getReferrers();
298 if (node.isNew() && !node.isDeleted() && referrers.size() == 1
299 && referrers.get(0).equals(referenceWay) && !subjectWay.containsNode(node)
300 && !hasInterestingKey(node) && !geometryPool.contains(node))
301 geometryPool.add(node);
302 }
303
304 int gLen = geometryPool.size();
305 int nLen = nodePool.size();
306 int maxDim = Math.max(gLen, nLen);
307 boolean useRobust = Config.getPref().getBoolean("utilsplugin2.replace-geometry.robustAssignment", true)
308 && maxDim <= Config.getPref().getInt("utilsplugin2.replace-geometry.robustAssignment.max-size", 300);
309
310 // Find new nodes that are closest to the old ones, remove matching old ones from the pool
311 // Assign node moves with least overall distance moved
312 Map<Node, Node> nodeAssoc = new HashMap<>();
313 if (gLen > 0 && nLen > 0) {
314 if (useRobust) { // use robust, but slower assignment
315 double[][] cost = new double[maxDim][maxDim];
316 for (int i = 0; i < maxDim; i++) {
317 for (int j = 0; j < maxDim; j++) {
318 cost[i][j] = Double.MAX_VALUE;
319 }
320 }
321
322 double maxDistance = Double.parseDouble(Config.getPref().get("utilsplugin2.replace-geometry.max-distance", "1"));
323 for (int i = 0; i < nLen; i++) {
324 for (int j = 0; j < gLen; j++) {
325 double d = nodePool.get(i).getCoor().distance(geometryPool.get(j).getCoor());
326 if (d > maxDistance) {
327 cost[i][j] = Double.MAX_VALUE;
328 } else {
329 cost[i][j] = d;
330 }
331 }
332 }
333 AssignmentProblem assignment;
334 try {
335 assignment = new AssignmentProblem(cost);
336 for (int i = 0; i < maxDim; i++) {
337 int nIdx = i;
338 int gIdx = assignment.sol(i);
339 if (cost[nIdx][gIdx] != Double.MAX_VALUE) {
340 nodeAssoc.put(geometryPool.get(gIdx), nodePool.get(nIdx));
341 }
342 }
343 // node will be moved, remove from pool
344 for (Node n : nodeAssoc.values()) {
345 nodePool.remove(n);
346 }
347 } catch (Exception e) {
348 useRobust = false;
349 new Notification(
350 tr("Exceeded iteration limit for robust method, using simpler method.")
351 ).setIcon(JOptionPane.WARNING_MESSAGE).show();
352 nodeAssoc = new HashMap<>();
353 }
354 }
355 if (!useRobust) { // use simple, faster, but less robust assignment method
356 for (Node n : geometryPool) {
357 Node nearest = findNearestNode(n, nodePool);
358 if (nearest != null) {
359 nodeAssoc.put(n, nearest);
360 nodePool.remove(nearest);
361 }
362 }
363
364 }
365 }
366
367 // Now that we have replacement list, move all unused new nodes to nodePool (and delete them afterwards)
368 for (Node n : geometryPool) {
369 if (nodeAssoc.containsKey(n))
370 nodePool.add(n);
371 }
372
373 // And prepare a list of nodes with all the replacements
374 List<Node> geometryNodes = referenceWay.getNodes();
375 for (int i = 0; i < geometryNodes.size(); i++) {
376 if (nodeAssoc.containsKey(geometryNodes.get(i)))
377 geometryNodes.set(i, nodeAssoc.get(geometryNodes.get(i)));
378 }
379
380 // Now do the replacement
381 commands.add(new ChangeNodesCommand(subjectWay, geometryNodes));
382
383 // Move old nodes to new positions
384 for (Map.Entry<Node, Node> entry : nodeAssoc.entrySet()) {
385 commands.add(new MoveCommand(entry.getValue(), entry.getKey().getCoor()));
386 }
387
388 // Remove geometry way from selection
389 MainApplication.getLayerManager().getEditDataSet().clearSelection(referenceWay);
390
391 // And delete old geometry way
392 commands.add(new DeleteCommand(referenceWay));
393
394 // Delete nodes that are not used anymore
395 if (!nodePool.isEmpty())
396 commands.add(new DeleteCommand(nodePool));
397
398 // Two items in undo stack: change original way and delete geometry way
399 return new ReplaceGeometryCommand(
400 tr("Replace geometry for way {0}", subjectWay.getDisplayName(DefaultNameFormatter.getInstance())),
401 commands);
402 }
403
404 /**
405 * Create a list of distinct nodes that are not tagged and not used anywhere except in the way.
406 * @param way the way
407 * @return list of distinct nodes that are not tagged and not used anywhere except in the way
408 */
409 static List<Node> getUnimportantNodes(Way way) {
410 List<Node> nodePool = new LinkedList<>();
411 for (Node n : way.getNodes()) {
412 List<OsmPrimitive> referrers = n.getReferrers();
413 if (!n.isDeleted() && referrers.size() == 1 && referrers.get(0).equals(way)
414 && !hasInterestingKey(n) && !nodePool.contains(n)) {
415 nodePool.add(n);
416 }
417 }
418 return nodePool;
419 }
420
421 /**
422 * Checks if a way has at least one important node (e.g. interesting tag,
423 * role membership), and thus cannot be safely modified.
424 * @param geometry the new geometry for the replaced way
425 * @param way the way that should be replaced
426 * @return true if at least one node is not in {@code geometry} but is important
427 */
428 static boolean hasImportantNode(Way geometry, Way way) {
429 for (Node n : way.getNodes()) {
430 // if original and replacement way share a node, it's safe to replace
431 if (geometry.containsNode(n)) {
432 continue;
433 }
434 //TODO: if way is connected to other ways, warn or disallow?
435 for (OsmPrimitive o : n.getReferrers()) {
436 if (o instanceof Relation) {
437 return true;
438 }
439 }
440 if (hasInterestingKey(n)) {
441 return true;
442 }
443 }
444 return false;
445 }
446
447 static boolean hasInterestingKey(OsmPrimitive object) {
448 return object.getKeys().keySet().stream().anyMatch(k -> !OsmPrimitive.isUninterestingKey(k));
449 }
450
451 static boolean isInArea(Node node, Area area) {
452 LatLon ll = node.getCoor();
453 return node.isNewOrUndeleted() || area == null || ll == null || area.contains(ll.getX(), ll.getY());
454 }
455
456 static boolean isInArea(Way way, Area area) {
457 if (area == null) {
458 return true;
459 }
460
461 for (Node n : way.getNodes()) {
462 if (!isInArea(n, area)) {
463 return false;
464 }
465 }
466
467 return true;
468 }
469
470 /**
471 * Merge tags from source to target object, showing resolution dialog if
472 * needed.
473 *
474 * @param source object tags are merged from
475 * @param target object tags are merged to
476 * @return The list of {@link Command commands} needed to apply resolution actions.
477 * @throws UserCancelException If the user cancelled a dialog.
478 */
479 static List<Command> getTagConflictResolutionCommands(OsmPrimitive source, OsmPrimitive target) throws UserCancelException {
480 Collection<OsmPrimitive> primitives = Arrays.asList(source, target);
481 // launch a conflict resolution dialog, if necessary
482 return CombinePrimitiveResolverDialog.launchIfNecessary(
483 TagCollection.unionOfAllPrimitives(primitives), primitives, Collections.singleton(target));
484 }
485
486 /**
487 * Find node from the collection which is nearest to <tt>node</tt>. Max distance is taken in consideration.
488 * @param node the node
489 * @param nodes the collection
490 * @return null if there is no such node.
491 */
492 static Node findNearestNode(Node node, Collection<Node> nodes) {
493 if (nodes.contains(node))
494 return node;
495
496 Node nearest = null;
497 // TODO: use meters instead of degrees, but do it fast
498 double distance = Double.parseDouble(Config.getPref().get("utilsplugin2.replace-geometry.max-distance", "1"));
499 LatLon coor = node.getCoor();
500
501 for (Node n : nodes) {
502 double d = n.getCoor().distance(coor);
503 if (d < distance) {
504 distance = d;
505 nearest = n;
506 }
507 }
508 return nearest;
509 }
510
511 /**
512 * Return the nodes that appear only in 1st way , not in 2nd way.
513 * @param way1 1st way
514 * @param way2 2nd way
515 * @return set of distinct nodes which appear only in first way
516 */
517 private static Set<Node> getDistinctNodes(Way way1, Way way2) {
518 Set<Node> distincNodes = new HashSet<>(way1.getNodes());
519 distincNodes.removeAll(way2.getNodes());
520 return distincNodes;
521 }
522}
Note: See TracBrowser for help on using the repository browser.