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

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