Index: trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java =================================================================== --- trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 3553) +++ trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 3554) @@ -2,9 +2,11 @@ package org.openstreetmap.josm.actions; +import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.combineTigerTags; +import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.completeTagCollectionForEditing; +import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.normalizeTagCollectionBeforeEditing; import static org.openstreetmap.josm.tools.I18n.marktr; import static org.openstreetmap.josm.tools.I18n.tr; import static org.openstreetmap.josm.tools.I18n.trn; -import java.awt.GridBagLayout; import java.awt.event.ActionEvent; import java.awt.event.KeyEvent; @@ -14,21 +16,18 @@ import java.util.Collection; import java.util.Collections; +import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; +import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; -import java.util.Map.Entry; import java.util.Set; import java.util.TreeMap; -import java.util.TreeSet; - -import javax.swing.Box; -import javax.swing.JComboBox; -import javax.swing.JLabel; + import javax.swing.JOptionPane; -import javax.swing.JPanel; import org.openstreetmap.josm.Main; +import org.openstreetmap.josm.actions.ReverseWayAction.ReverseWayResult; import org.openstreetmap.josm.actions.SplitWayAction.SplitWayResult; import org.openstreetmap.josm.command.AddCommand; @@ -37,4 +36,5 @@ import org.openstreetmap.josm.command.DeleteCommand; import org.openstreetmap.josm.command.SequenceCommand; +import org.openstreetmap.josm.corrector.UserCancelException; import org.openstreetmap.josm.data.UndoRedoHandler; import org.openstreetmap.josm.data.coor.EastNorth; @@ -45,8 +45,8 @@ import org.openstreetmap.josm.data.osm.Relation; import org.openstreetmap.josm.data.osm.RelationMember; -import org.openstreetmap.josm.data.osm.TigerUtils; +import org.openstreetmap.josm.data.osm.TagCollection; import org.openstreetmap.josm.data.osm.Way; -import org.openstreetmap.josm.gui.ExtendedDialog; -import org.openstreetmap.josm.tools.GBC; +import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog; +import org.openstreetmap.josm.tools.Pair; import org.openstreetmap.josm.tools.Shortcut; @@ -56,4 +56,5 @@ private int cmdsCount = 0; + /** * This helper class describes join ares action result. @@ -63,41 +64,20 @@ public static class JoinAreasResult { - public Way outerWay; - public List innerWays; - public boolean mergeSuccessful; public boolean hasChanges; public boolean hasRelationProblems; - } - - // HelperClass - // Saves a node and two positions where to insert the node into the ways - private static class NodeToSegs implements Comparable { - public int pos; - public Node n; - public double dis; - public NodeToSegs(int pos, Node n, LatLon dis) { - this.pos = pos; - this.n = n; - this.dis = n.getCoor().greatCircleDistance(dis); - } - - public int compareTo(NodeToSegs o) { - if(this.pos == o.pos) - return (this.dis - o.dis) > 0 ? 1 : -1; - return this.pos - o.pos; - } - - @Override - public int hashCode() { - return pos; - } - - @Override - public boolean equals(Object o) { - if (o instanceof NodeToSegs) - return compareTo((NodeToSegs) o) == 0; - else - return false; + + public List polygons; + } + + public static class Multipolygon { + public Way outerWay; + public List innerWays; + + public Relation relation; + + public Multipolygon(Way way) { + outerWay = way; + innerWays = new ArrayList(); } } @@ -126,17 +106,15 @@ } - /** - * HelperClass - * saves a way and the "inside" side - * insideToTheLeft: if true left side is "in", false -right side is "in". - * Left and right are determined along the orientation of way. - */ - private static class WayInPath { + + //HelperClass + //saves a way and the "inside" side + // insideToTheLeft: if true left side is "in", false -right side is "in". Left and right are determined along the orientation of way. + private static class WayInPolygon { public final Way way; - public boolean insideToTheLeft; - - public WayInPath(Way way, boolean insideLeft) { - this.way = way; - this.insideToTheLeft = insideLeft; + public boolean insideToTheRight; + + public WayInPolygon(Way _way, boolean _insideRight) { + this.way = _way; + this.insideToTheRight = _insideRight; } @@ -148,10 +126,207 @@ @Override public boolean equals(Object other) { - if (!(other instanceof WayInPath)) - return false; - WayInPath otherMember = (WayInPath) other; - return otherMember.way.equals(this.way) && otherMember.insideToTheLeft == this.insideToTheLeft; - } - } + if (!(other instanceof WayInPolygon)) return false; + WayInPolygon otherMember = (WayInPolygon) other; + return otherMember.way.equals(this.way) && otherMember.insideToTheRight == this.insideToTheRight; + } + } + + /** + * This helper class describes a polygon, assembled from several ways. + * @author viesturs + * + */ + private static class AssembledPolygon { + public List ways; + + public AssembledPolygon(List boundary) { + this.ways = boundary; + } + + public List getNodes() { + List nodes = new ArrayList(); + for (WayInPolygon way : this.ways) { + //do not add the last node as it will be repeated in the next way + if (way.insideToTheRight) { + for (int pos = 0; pos < way.way.getNodesCount() - 1; pos++) { + nodes.add(way.way.getNode(pos)); + } + } + else { + for (int pos = way.way.getNodesCount() - 1; pos > 0; pos--) { + nodes.add(way.way.getNode(pos)); + } + } + } + + return nodes; + } + } + + + public static class AssembledMultipolygon { + public AssembledPolygon outerWay; + public List innerWays; + + public AssembledMultipolygon(AssembledPolygon way) { + outerWay = way; + innerWays = new ArrayList(); + } + } + + /** + * This hepler class implements algorithm traversing trough connected ways. + * Assumes you are going in clockwise orientation. + * @author viesturs + * + */ + private static class WayTraverser { + + private Set availableWays; + private WayInPolygon lastWay; + private boolean lastWayReverse; + + public WayTraverser(Collection ways) { + + availableWays = new HashSet(ways); + lastWay = null; + } + + public void removeWays(Collection ways) { + availableWays.removeAll(ways); + } + + public boolean hasWays() { + return availableWays.size() > 0; + } + + public WayInPolygon startNewWay(WayInPolygon way) { + lastWay = way; + lastWayReverse = !lastWay.insideToTheRight; + + return lastWay; + } + + public WayInPolygon startNewWay() { + if (availableWays.size() == 0) { + lastWay = null; + } else { + lastWay = availableWays.iterator().next(); + lastWayReverse = !lastWay.insideToTheRight; + } + + return lastWay; + } + + + public WayInPolygon advanceNextLeftmostWay() { + return advanceNextWay(false); + } + + public WayInPolygon advanceNextRightmostWay() { + return advanceNextWay(true); + } + + private WayInPolygon advanceNextWay(boolean rightmost) { + + Node headNode = !lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode(); + Node prevNode = !lastWayReverse ? lastWay.way.getNode(lastWay.way.getNodesCount() - 2) : lastWay.way.getNode(1); + + //find best next way + WayInPolygon bestWay = null; + Node bestWayNextNode = null; + boolean bestWayReverse = false; + + for (WayInPolygon way : availableWays) { + if (way.way.firstNode().equals(headNode)) { + //start adjacent to headNode + Node nextNode = way.way.getNode(1); + + if (nextNode.equals(prevNode)) + { + //this is the path we came from - ignore it. + } + else if (bestWay == null || (isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) { + //the new way is better + bestWay = way; + bestWayReverse = false; + bestWayNextNode = nextNode; + } + } + + if (way.way.lastNode().equals(headNode)) { + //end adjacent to headNode + Node nextNode = way.way.getNode(way.way.getNodesCount() - 2); + + if (nextNode.equals(prevNode)) { + //this is the path we came from - ignore it. + } + else if (bestWay == null || (isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) { + //the new way is better + bestWay = way; + bestWayReverse = true; + bestWayNextNode = nextNode; + } + } + } + + lastWay = bestWay; + lastWayReverse = bestWayReverse; + + return lastWay; + } + + public boolean isLastWayInsideToTheRight() { + return lastWayReverse != lastWay.insideToTheRight; + } + + public Node getLastWayStartNode() { + return lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode(); + } + + public Node getLastWayEndNode() { + return lastWayReverse ? lastWay.way.firstNode() : lastWay.way.lastNode(); + } + } + + /** + * Provides some node order , based on coordinates, nodes with equal coordinates are equal. + * @author viesturs + * + */ + private class NodePositionComparator implements Comparator { + + @Override + public int compare(Node n1, Node n2) { + + double dLat = n1.getCoor().lat() - n2.getCoor().lat(); + double dLon = n1.getCoor().lon() - n2.getCoor().lon(); + + if (dLat > 0) + return 1; + else if (dLat < 0) + return -1; + else if (dLon == 0) //dlat is 0 here + return 0; + else + return dLon > 0 ? 1 : -1; + } + } + + + /** + * Helper storage class for finding findOuterWays + * @author viesturs + */ + static class PolygonLevel { + public final int level; + public final AssembledMultipolygon pol; + + public PolygonLevel(AssembledMultipolygon _pol, int _level) { + pol = _pol; + level = _level; + } + } + // Adds the menu entry, Shortcuts, etc. @@ -173,13 +348,7 @@ } - // Too many ways - if(ways.size() > 2) { - JOptionPane.showMessageDialog(Main.parent, tr("Only up to two areas can be joined at the moment.")); - return; - } - List allNodes = new ArrayList(); - for (Way way: ways) { - if(!way.isClosed()) { + for (Way way : ways) { + if (!way.isClosed()) { JOptionPane.showMessageDialog(Main.parent, tr("\"{0}\" is not closed and therefore cannot be joined.", way.getName())); return; @@ -192,5 +361,5 @@ Area dataSourceArea = Main.main.getCurrentDataSet().getDataSourceArea(); if (dataSourceArea != null) { - for (Node node: allNodes) { + for (Node node : allNodes) { if (!dataSourceArea.contains(node.getCoor())) { int option = JOptionPane.showConfirmDialog(Main.parent, @@ -209,99 +378,154 @@ } - if (checkForTagConflicts(ways.getFirst(), ways.getLast())) - //there was conflicts and user canceled abort the action. + //analyze multipolygon relations and collect all areas + List areas = collectMultipolygons(ways); + + if (areas == null) + //too complex multipolygon relations found return; - - JoinAreasResult result = joinAreas(ways.getFirst(), ways.getLast()); - - if (result.hasChanges) { - Main.map.mapView.repaint(); - DataSet ds = Main.main.getCurrentDataSet(); - ds.fireSelectionChanged(); - } else { + if (!testJoin(areas)) { JOptionPane.showMessageDialog(Main.parent, tr("No intersection found. Nothing was changed.")); - } - } - - /** - * Will join two overlapping areas - * @param Way First way/area - * @param Way Second way/area - */ - private JoinAreasResult joinAreas(Way a, Way b) { + return; + } + + if (!resolveTagConflicts(areas)) + return; + //user cancelled, do nothing. + + try { + JoinAreasResult result = joinAreas(areas); + + if (result.hasChanges) { + + Main.map.mapView.repaint(); + DataSet ds = Main.main.getCurrentDataSet(); + ds.fireSelectionChanged(); + } else { + JOptionPane.showMessageDialog(Main.parent, tr("No intersection found. Nothing was changed.")); + } + } + catch (UserCancelException exception) { + //revert changes + //FIXME: this is dirty hack + makeCommitsOneAction(tr("Reverting changes")); + Main.main.undoRedo.undo(); + Main.main.undoRedo.redoCommands.clear(); + } + } + + + /** + * Tests if the areas have some intersections to join. + * @param areas + * @return + */ + private boolean testJoin(List areas) { + List allStartingWays = new ArrayList(); + + for (Multipolygon area : areas) { + allStartingWays.add(area.outerWay); + allStartingWays.addAll(area.innerWays); + } + + //find intersection points + ArrayList nodes = addIntersections(allStartingWays, true); + return nodes.size() > 0; + } + + /** + * Will join two or more overlapping areas + * @param areas - list of areas to join + * @return new area formed. + */ + private JoinAreasResult joinAreas(List areas) throws UserCancelException { JoinAreasResult result = new JoinAreasResult(); result.hasChanges = false; - // Fix self-overlapping first or other errors - boolean same = a.equals(b); - if(!same) { - int i = 0; - - //join each area with itself, fixing self-crossings. - JoinAreasResult resultA = joinAreas(a, a); - JoinAreasResult resultB = joinAreas(b, b); - - if (resultA.mergeSuccessful) { - a = resultA.outerWay; - ++i; - } - if(resultB.mergeSuccessful) { - b = resultB.outerWay; - ++i; - } - - result.hasChanges = i > 0; - cmdsCount = i; - } - - ArrayList nodes = addIntersections(a, b); + List allStartingWays = new ArrayList(); + List innerStartingWays = new ArrayList(); + List outerStartingWays = new ArrayList(); + + for (Multipolygon area : areas) { + outerStartingWays.add(area.outerWay); + innerStartingWays.addAll(area.innerWays); + } + + allStartingWays.addAll(innerStartingWays); + allStartingWays.addAll(outerStartingWays); + + //first remove nodes in the same coordinate + boolean removedDuplicates = false; + removedDuplicates |= removeDuplicateNodes(allStartingWays); + + if (removedDuplicates) { + result.hasChanges = true; + commitCommands(marktr("Removed duplicate nodes")); + } + + //find intersection points + ArrayList nodes = addIntersections(allStartingWays, false); //no intersections, return. - if(nodes.size() == 0) return result; + if (nodes.size() == 0) return result; commitCommands(marktr("Added node on all intersections")); + ArrayList relations = new ArrayList(); + // Remove ways from all relations so ways can be combined/split quietly - ArrayList relations = removeFromRelations(a); - if(!same) { - relations.addAll(removeFromRelations(b)); + for (Way way : allStartingWays) { + relations.addAll(removeFromAllRelations(way)); } // Don't warn now, because it will really look corrupted - boolean warnAboutRelations = relations.size() > 0; - - ArrayList allWays = splitWaysOnNodes(a, b, nodes); - - // Find inner ways save them to a list - ArrayList outerWays = findOuterWays(allWays); - ArrayList innerWays = findInnerWays(allWays, outerWays); - - // Join outer ways - Way outerWay = joinOuterWays(outerWays); - - // Fix Multipolygons if there are any - List newInnerWays = fixMultipolygons(innerWays, outerWay, same); - - // Delete the remaining inner ways - if(innerWays != null && innerWays.size() > 0) { - cmds.add(DeleteCommand.delete(Main.map.mapView.getEditLayer(), innerWays, true)); + boolean warnAboutRelations = relations.size() > 0 && allStartingWays.size() > 1; + + ArrayList preparedWays = new ArrayList(); + + for (Way way : outerStartingWays) { + ArrayList splitWays = splitWayOnNodes(way, nodes); + preparedWays.addAll(markWayInsideSide(splitWays, false)); + } + + for (Way way : innerStartingWays) { + ArrayList splitWays = splitWayOnNodes(way, nodes); + preparedWays.addAll(markWayInsideSide(splitWays, true)); + } + + // Find boundary ways + ArrayList discardedWays = new ArrayList(); + List bounadries = findBoundaryPolygons(preparedWays, discardedWays); + + //find polygons + List preparedPolygons = findPolygons(bounadries); + + //assemble final ways + List polygons = new ArrayList(); + for (AssembledMultipolygon pol : preparedPolygons) { + polygons.add(joinPolygon(pol)); + } + + // Delete the discarded inner ways + if (discardedWays.size() > 0) { + cmds.add(DeleteCommand.delete(Main.map.mapView.getEditLayer(), discardedWays, true)); } commitCommands(marktr("Delete Ways that are not part of an inner multipolygon")); // We can attach our new multipolygon relation and pretend it has always been there - addOwnMultigonRelation(newInnerWays, outerWay, relations); - fixRelations(relations, outerWay); + for (Multipolygon pol : polygons) { + addOwnMultigonRelation(pol.innerWays, pol.outerWay, relations); + fixRelations(relations, pol.outerWay); + } + commitCommands(marktr("Fix relations")); - stripTags(newInnerWays); - - makeCommitsOneAction( - same - ? marktr("Joined self-overlapping area") - : marktr("Joined overlapping areas") - ); - - if(warnAboutRelations) { + for (Multipolygon pol : polygons) { + stripTags(pol.innerWays); + } + + makeCommitsOneAction(marktr("Joined overlapping areas")); + + if (warnAboutRelations) { JOptionPane.showMessageDialog(Main.parent, tr("Some of the ways were part of relations that have been modified. Please verify no errors have been introduced.")); } @@ -309,7 +533,5 @@ result.hasChanges = true; result.mergeSuccessful = true; - result.outerWay = outerWay; - result.innerWays = newInnerWays; - + result.polygons = polygons; return result; } @@ -319,132 +541,288 @@ * @param Way First way to check * @param Way Second Way to check - * @return boolean True if not all conflicts could be resolved, False if everything's fine - */ - private boolean checkForTagConflicts(Way a, Way b) { - ArrayList ways = new ArrayList(); - ways.add(a); - ways.add(b); - - // FIXME: This is mostly copied and pasted from CombineWayAction.java and one day should be moved into tools - // We have TagCollection handling for that now - use it here as well - Map> props = new TreeMap>(); - for (Way w : ways) { - for (String key: w.keySet()) { - if (!props.containsKey(key)) { - props.put(key, new TreeSet()); - } - props.get(key).add(w.get(key)); - } - } - - Way ax = new Way(a); - Way bx = new Way(b); - - Map components = new HashMap(); - JPanel p = new JPanel(new GridBagLayout()); - for (Entry> e : props.entrySet()) { - if (TigerUtils.isTigerTag(e.getKey())) { - String combined = TigerUtils.combineTags(e.getKey(), e.getValue()); - ax.put(e.getKey(), combined); - bx.put(e.getKey(), combined); - } else if (e.getValue().size() > 1) { - if("created_by".equals(e.getKey())) - { - ax.remove("created_by"); - bx.remove("created_by"); + * @return boolean True if all conflicts are resolved, False if conflicts remain. + */ + private boolean resolveTagConflicts(List polygons) { + + List ways = new ArrayList(); + + for (Multipolygon pol : polygons) { + ways.add(pol.outerWay); + ways.addAll(pol.innerWays); + } + + if (ways.size() < 2) + return true; + + //mostly copied from CombineWayAction.java. + TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways); + TagCollection completeWayTags = new TagCollection(wayTags); + combineTigerTags(completeWayTags); + normalizeTagCollectionBeforeEditing(completeWayTags, ways); + TagCollection tagsToEdit = new TagCollection(completeWayTags); + completeTagCollectionForEditing(tagsToEdit); + + CombinePrimitiveResolverDialog dialog = CombinePrimitiveResolverDialog.getInstance(); + dialog.getTagConflictResolverModel().populate(tagsToEdit, completeWayTags.getKeysWithMultipleValues()); + dialog.setTargetPrimitive(ways.get(0)); + Collection parentRelations = CombineWayAction.getParentRelations(ways); + parentRelations = filterOwnMultipolygonRelations(parentRelations, polygons); + dialog.getRelationMemberConflictResolverModel().populate( + parentRelations, + ways + ); + dialog.prepareDefaultDecisions(); + + // resolve tag conflicts if necessary + // + if (!completeWayTags.isApplicableToPrimitive() || !parentRelations.isEmpty()) { + dialog.setVisible(true); + if (dialog.isCancelled()) + return false; + } + + for (Way way : ways) { + dialog.setTargetPrimitive(way); + cmds.addAll(dialog.buildResolutionCommands()); + } + + commitCommands(marktr("Fix tag conflicts")); + return true; + } + + + /** + * This method removes duplicate points (if any) from the input way. + * @param way the way to process + * @return true if any changes where made + */ + private boolean removeDuplicateNodes(List ways) { + //TODO: maybe join nodes with JoinNodesAction, rather than reconnect the ways. + + Map nodeMap = new TreeMap(new NodePositionComparator()); + int totalNodesRemoved = 0; + + for (Way way : ways) { + if (way.getNodes().size() < 2) { + continue; + } + + int nodesRemoved = 0; + List newNodes = new ArrayList(); + Node prevNode = null; + + for (Node node : way.getNodes()) { + if (!nodeMap.containsKey(node)) { + //new node + nodeMap.put(node, node); + + //avoid duplicate nodes + if (prevNode != node) { + newNodes.add(node); + } else { + nodesRemoved ++; + } } else { - JComboBox c = new JComboBox(e.getValue().toArray()); - c.setEditable(true); - p.add(new JLabel(e.getKey()), GBC.std()); - p.add(Box.createHorizontalStrut(10), GBC.std()); - p.add(c, GBC.eol()); - components.put(e.getKey(), c); - } - } else { - String val = e.getValue().iterator().next(); - ax.put(e.getKey(), val); - bx.put(e.getKey(), val); - } - } - - if (components.isEmpty()) - return false; // No conflicts found - - ExtendedDialog ed = new ExtendedDialog(Main.parent, - tr("Enter values for all conflicts."), - new String[] {tr("Solve Conflicts"), tr("Cancel")}); - ed.setButtonIcons(new String[] {"dialogs/conflict.png", "cancel.png"}); - ed.setContent(p); - ed.showDialog(); - - if (ed.getValue() != 1) return true; // user cancel, unresolvable conflicts - - for (Entry e : components.entrySet()) { - String val = e.getValue().getEditor().getItem().toString(); - ax.put(e.getKey(), val); - bx.put(e.getKey(), val); - } - - cmds.add(new ChangeCommand(a, ax)); - cmds.add(new ChangeCommand(b, bx)); - commitCommands(marktr("Fix tag conflicts")); - return false; - } - - /** - * Will find all intersection and add nodes there for two given ways - * @param Way First way - * @param Way Second way - * @return ArrayList List of new nodes - */ - private ArrayList addIntersections(Way a, Way b) { - boolean same = a.equals(b); - int nodesSizeA = a.getNodesCount(); - int nodesSizeB = b.getNodesCount(); - - ArrayList nodes = new ArrayList(); - ArrayList nodesA = new ArrayList(); - ArrayList nodesB = new ArrayList(); - - for (int i = (same ? 1 : 0); i < nodesSizeA - 1; i++) { - for (int j = (same ? i + 2 : 0); j < nodesSizeB - 1; j++) { - // Avoid re-adding nodes that already exist on (some) intersections - if(a.getNode(i).equals(b.getNode(j)) || a.getNode(i+1).equals(b.getNode(j))) { - nodes.add(b.getNode(j)); - continue; - } else - if(a.getNode(i).equals(b.getNode(j+1)) || a.getNode(i+1).equals(b.getNode(j+1))) { - nodes.add(b.getNode(j+1)); - continue; + //node with same coordinates already exists, substitute with existing node + Node representator = nodeMap.get(node); + + if (representator != node) { + nodesRemoved ++; } - LatLon intersection = getLineLineIntersection( - a.getNode(i) .getEastNorth().east(), a.getNode(i) .getEastNorth().north(), - a.getNode(i+1).getEastNorth().east(), a.getNode(i+1).getEastNorth().north(), - b.getNode(j) .getEastNorth().east(), b.getNode(j) .getEastNorth().north(), - b.getNode(j+1).getEastNorth().east(), b.getNode(j+1).getEastNorth().north()); - if(intersection == null) { - continue; - } - - // Create the node. Adding them to the ways must be delayed because we still loop over them - Node n = new Node(intersection); - cmds.add(new AddCommand(n)); - nodes.add(n); - // The distance is needed to sort and add the nodes in direction of the way - nodesA.add(new NodeToSegs(i, n, a.getNode(i).getCoor())); - if(same) { - nodesA.add(new NodeToSegs(j, n, a.getNode(j).getCoor())); - } else { - nodesB.add(new NodeToSegs(j, n, b.getNode(j).getCoor())); - } - } - } - - addNodesToWay(a, nodesA); - if(!same) { - addNodesToWay(b, nodesB); - } - - return nodes; + + //avoid duplicate node + if (prevNode != representator) { + newNodes.add(representator); + } + } + prevNode = node; + } + + if (nodesRemoved > 0) { + + if (newNodes.size() == 1) { //all nodes in the same coordinate - add one more node, to have closed way. + newNodes.add(newNodes.get(0)); + } + + Way newWay=new Way(way); + newWay.setNodes(newNodes); + cmds.add(new ChangeCommand(way, newWay)); + totalNodesRemoved += nodesRemoved; + } + } + + return totalNodesRemoved > 0; + } + + + + /** + * Will find all intersection and add nodes there for list of given ways. Handles self-intersections too. + * And make commands to add the intersection points to ways. + * @param List - a list of ways to test + * @return ArrayList List of new nodes + * Prerequisite: no two nodes have the same coordinates. + */ + private ArrayList addIntersections(List ways, boolean test) { + //TODO: this is a bit slow - O( (number of nodes)^2 + numberOfIntersections * numberOfNodes ) + + //stupid java, cannot instantiate array of generic classes.. + @SuppressWarnings("unchecked") + ArrayList[] newNodes = new ArrayList[ways.size()]; + boolean[] changedWays = new boolean[ways.size()]; + + Set intersectionNodes = new LinkedHashSet(); + + for (int pos = 0; pos < ways.size(); pos ++) { + newNodes[pos] = new ArrayList(ways.get(pos).getNodes()); + changedWays[pos] = false; + } + + //iterate over all segment pairs and introduce the intersections + + Comparator coordsComparator = new NodePositionComparator(); + + int seg1Way = 0; + int seg1Pos = -1; + + while (true) { + //advance to next segment + seg1Pos++; + if (seg1Pos > newNodes[seg1Way].size() - 2) { + seg1Way++; + seg1Pos = 0; + + if (seg1Way == ways.size()) { //finished + break; + } + } + + + //iterate over secondary segment + + int seg2Way = seg1Way; + int seg2Pos = seg1Pos + 1;//skip the adjacent segment + + while (true) { + + //advance to next segment + seg2Pos++; + if (seg2Pos > newNodes[seg2Way].size() - 2) { + seg2Way++; + seg2Pos = 0; + + if (seg2Way == ways.size()) { //finished + break; + } + } + + //need to get them again every time, because other segments may be changed + Node seg1Node1 = newNodes[seg1Way].get(seg1Pos); + Node seg1Node2 = newNodes[seg1Way].get(seg1Pos + 1); + Node seg2Node1 = newNodes[seg2Way].get(seg2Pos); + Node seg2Node2 = newNodes[seg2Way].get(seg2Pos + 1); + + int commonCount = 0; + //test if we have common nodes to add. + if (seg1Node1 == seg2Node1 || seg1Node1 == seg2Node2) { + commonCount ++; + + if (seg1Way == seg2Way && + seg1Pos == 0 && + seg2Pos == newNodes[seg2Way].size() -2) { + //do not add - this is first and last segment of the same way. + } else { + intersectionNodes.add(seg1Node1); + } + } + + if (seg1Node2 == seg2Node1 || seg1Node2 == seg2Node2) { + commonCount ++; + + intersectionNodes.add(seg1Node2); + } + + //no common nodes - find intersection + if (commonCount == 0) { + LatLon intersection = getLineLineIntersection( + seg1Node1.getEastNorth().east(), seg1Node1.getEastNorth().north(), + seg1Node2.getEastNorth().east(), seg1Node2.getEastNorth().north(), + seg2Node1.getEastNorth().east(), seg2Node1.getEastNorth().north(), + seg2Node2.getEastNorth().east(), seg2Node2.getEastNorth().north()); + + if (intersection != null) { + if (test) { + intersectionNodes.add(seg2Node1); + return new ArrayList(intersectionNodes); + } + + Node newNode = new Node(intersection); + Node intNode = newNode; + boolean insertInSeg1 = false; + boolean insertInSeg2 = false; + + //find if the intersection point is at end point of one of the segments, if so use that point + + //segment 1 + if (coordsComparator.compare(newNode, seg1Node1) == 0) { + intNode = seg1Node1; + } else if (coordsComparator.compare(newNode, seg1Node2) == 0) { + intNode = seg1Node2; + } else { + insertInSeg1 = true; + } + + //segment 2 + if (coordsComparator.compare(newNode, seg2Node1) == 0) { + intNode = seg2Node1; + } else if (coordsComparator.compare(newNode, seg2Node2) == 0) { + intNode = seg2Node2; + } else { + insertInSeg2 = true; + } + + if (insertInSeg1) { + newNodes[seg1Way].add(seg1Pos +1, intNode); + changedWays[seg1Way] = true; + + //fix seg2 position, as indexes have changed, seg2Pos is always bigger than seg1Pos on the same segment. + if (seg2Way == seg1Way) { + seg2Pos ++; + } + } + + if (insertInSeg2) { + newNodes[seg2Way].add(seg2Pos +1, intNode); + changedWays[seg2Way] = true; + + //Do not need to compare again to already split segment + seg2Pos ++; + } + + intersectionNodes.add(intNode); + + if (intNode == newNode) { + cmds.add(new AddCommand(intNode)); + } + } + } + else if (test && intersectionNodes.size() > 0) + return new ArrayList(intersectionNodes); + } + } + + for (int pos = 0; pos < ways.size(); pos ++) { + if (changedWays[pos] == false) { + continue; + } + + Way way = ways.get(pos); + Way newWay = new Way(way); + newWay.setNodes(newNodes[pos]); + + cmds.add(new ChangeCommand(way, newWay)); + } + + return new ArrayList(intersectionNodes); } @@ -470,5 +848,5 @@ // Solve the equations double det = a1*b2 - a2*b1; - if(det == 0) return null; // Lines are parallel + if (det == 0) return null; // Lines are parallel return Main.proj.eastNorth2latlon(new EastNorth( @@ -478,23 +856,5 @@ } - /** - * Inserts given nodes with positions into the given ways - * @param Way The way to insert the nodes into - * @param Collection The list of nodes with positions to insert - */ - private void addNodesToWay(Way a, ArrayList nodes) { - if(nodes.size() == 0) - return; - Way ax=new Way(a); - Collections.sort(nodes); - - int numOfAdds = 1; - for(NodeToSegs n : nodes) { - ax.addNode(n.pos + numOfAdds, n.n); - numOfAdds++; - } - - cmds.add(new ChangeCommand(a, ax)); - } + /** @@ -519,64 +879,204 @@ } - /** - * Removes a given OsmPrimitive from all relations - * @param OsmPrimitive Element to remove from all relations - * @return ArrayList List of relations with roles the primitives was part of - */ - private ArrayList removeFromRelations(OsmPrimitive osm) { - ArrayList result = new ArrayList(); - for (Relation r : Main.main.getCurrentDataSet().getRelations()) { - if (r.isDeleted()) { - continue; - } - for (RelationMember rm : r.getMembers()) { - if (rm.getMember() != osm) { + + /** + * This method analyzes the way and assigns each part what direction polygon "inside" is. + * @param parts the split parts of the way + * @param isInner - if true, reverts the direction (for multipolygon islands) + * @return list of parts, marked with the inside orientation. + */ + private ArrayList markWayInsideSide(List parts, boolean isInner) { + + ArrayList result = new ArrayList(); + + //prepare prev and next maps + Map nextWayMap = new HashMap(); + Map prevWayMap = new HashMap(); + + for (int pos = 0; pos < parts.size(); pos ++) { + + if (!parts.get(pos).lastNode().equals(parts.get((pos + 1) % parts.size()).firstNode())) + throw new RuntimeException("Way not circular"); + + nextWayMap.put(parts.get(pos), parts.get((pos + 1) % parts.size())); + prevWayMap.put(parts.get(pos), parts.get((pos + parts.size() - 1) % parts.size())); + } + + //find the node with minimum y - it's guaranteed to be outer. (What about the south pole?) + Way topWay = null; + Node topNode = null; + int topIndex = 0; + double minY = Double.POSITIVE_INFINITY; + + for (Way way : parts) { + for (int pos = 0; pos < way.getNodesCount(); pos ++) { + Node node = way.getNode(pos); + + if (node.getEastNorth().getY() < minY) { + minY = node.getEastNorth().getY(); + topWay = way; + topNode = node; + topIndex = pos; + } + } + } + + //get the upper way and it's orientation. + + boolean wayClockwise; // orientation of the top way. + + if (topNode.equals(topWay.firstNode()) || topNode.equals(topWay.lastNode())) { + Node headNode = null; // the node at junction + Node prevNode = null; // last node from previous path + wayClockwise = false; + + //node is in split point - find the outermost way from this point + + headNode = topNode; + //make a fake node that is downwards from head node (smaller Y). It will be a division point between paths. + prevNode = new Node(new EastNorth(headNode.getEastNorth().getX(), headNode.getEastNorth().getY() - 1e5)); + + topWay = null; + wayClockwise = false; + Node bestWayNextNode = null; + + for (Way way : parts) { + if (way.firstNode().equals(headNode)) { + Node nextNode = way.getNode(1); + + if (topWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { + //the new way is better + topWay = way; + wayClockwise = true; + bestWayNextNode = nextNode; + } + } + + if (way.lastNode().equals(headNode)) { + //end adjacent to headNode + Node nextNode = way.getNode(way.getNodesCount() - 2); + + if (topWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { + //the new way is better + topWay = way; + wayClockwise = false; + bestWayNextNode = nextNode; + } + } + } + } else { + //node is inside way - pick the clockwise going end. + Node prev = topWay.getNode(topIndex - 1); + Node next = topWay.getNode(topIndex + 1); + + //there will be no parallel segments in the middle of way, so all fine. + wayClockwise = angleIsClockwise(prev, topNode, next); + } + + Way curWay = topWay; + boolean curWayInsideToTheRight = wayClockwise ^ isInner; + + //iterate till full circle is reached + while (true) { + + //add cur way + WayInPolygon resultWay = new WayInPolygon(curWay, curWayInsideToTheRight); + result.add(resultWay); + + //process next way + Way nextWay = nextWayMap.get(curWay); + Node prevNode = curWay.getNode(curWay.getNodesCount() - 2); + Node headNode = curWay.lastNode(); + Node nextNode = nextWay.getNode(1); + + if (nextWay == topWay) { + //full loop traversed - all done. + break; + } + + + //find intersecting segments + // the intersections will look like this: + // + // ^ + // | + // X wayBNode + // | + // wayB | + // | + // curWay | nextWay + //----X----------------->X----------------------X----> + // prevNode ^headNode nextNode + // | + // | + // wayA | + // | + // X wayANode + // | + + int intersectionCount = 0; + + for (Way wayA : parts) { + + if (wayA == curWay) { continue; } - Relation newRel = new Relation(r); - List members = newRel.getMembers(); - members.remove(rm); - newRel.setMembers(members); - - cmds.add(new ChangeCommand(r, newRel)); - RelationRole saverel = new RelationRole(r, rm.getRole()); - if(!result.contains(saverel)) { - result.add(saverel); - } - break; - } - } - - commitCommands(marktr("Removed Element from Relations")); + if (wayA.lastNode().equals(headNode)) { + + Way wayB = nextWayMap.get(wayA); + + //test if wayA is opposite wayB relative to curWay and nextWay + + Node wayANode = wayA.getNode(wayA.getNodesCount() - 2); + Node wayBNode = wayB.getNode(1); + + boolean wayAToTheRight = isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode); + boolean wayBToTheRight = isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode); + + if (wayAToTheRight != wayBToTheRight) { + intersectionCount ++; + } + } + } + + //if odd number of crossings, invert orientation + if (intersectionCount % 2 == 1) { + curWayInsideToTheRight = !curWayInsideToTheRight; + } + + curWay = nextWay; + } + return result; } /** - * This method splits ways into smaller parts, using the prepared nodes list as split points. - * Uses SplitWayAction.splitWay for the heavy lifting. + * This is a method splits way into smaller parts, using the prepared nodes list as split points. + * Uses SplitWayAction.splitWay for the heavy lifting. * @return list of split ways (or original ways if no splitting is done). */ - private ArrayList splitWaysOnNodes(Way a, Way b, Collection nodes) { + private ArrayList splitWayOnNodes(Way way, Collection nodes) { ArrayList result = new ArrayList(); - List ways = new ArrayList(); - ways.add(a); - ways.add(b); - - for (Way way: ways) { - List> chunks = buildNodeChunks(way, nodes); + List> chunks = buildNodeChunks(way, nodes); + + if (chunks.size() > 1) { SplitWayResult split = SplitWayAction.splitWay(Main.map.mapView.getEditLayer(), way, chunks, Collections.emptyList()); //execute the command, we need the results - Main.main.undoRedo.add(split.getCommand()); - cmdsCount ++; + cmds.add(split.getCommand()); + commitCommands(marktr("Split ways into fragments")); result.add(split.getOriginalWay()); result.addAll(split.getNewWays()); + } else { + //nothing to split + result.add(way); } return result; } + /** @@ -584,14 +1084,13 @@ * @param way the way to chunk * @param splitNodes the places where to cut. - * @return list of node segments to produce. - */ - private List> buildNodeChunks(Way way, Collection splitNodes) - { + * @return list of node paths to produce. + */ + private List> buildNodeChunks(Way way, Collection splitNodes) { List> result = new ArrayList>(); List curList = new ArrayList(); - for(Node node: way.getNodes()){ + for (Node node : way.getNodes()) { curList.add(node); - if (curList.size() > 1 && splitNodes.contains(node)){ + if (curList.size() > 1 && splitNodes.contains(node)) { result.add(curList); curList = new ArrayList(); @@ -600,6 +1099,5 @@ } - if (curList.size() > 1) - { + if (curList.size() > 1) { result.add(curList); } @@ -608,153 +1106,217 @@ } - /** - * Returns all nodes for given ways - * @param Collection The list of ways which nodes are to be returned - * @return Collection The list of nodes the ways contain - */ - private Collection getNodesFromWays(Collection ways) { - Collection allNodes = new ArrayList(); - for(Way w: ways) { - allNodes.addAll(w.getNodes()); - } - return allNodes; - } - - /** - * Gets all inner ways given all ways and outer ways. - * @param multigonWays - * @param outerWays - * @return list of inner ways. - */ - private ArrayList findInnerWays(Collection multigonWays, Collection outerWays) { - ArrayList innerWays = new ArrayList(); - Set outerSet = new HashSet(); - - for(WayInPath w: outerWays) { - outerSet.add(w.way); - } - - for(Way way: multigonWays) { - if (!outerSet.contains(way)) { - innerWays.add(way); - } - } - - return innerWays; - } - - - /** - * Finds all ways for a given list of Ways that form the outer hull. - * This works by starting with one node and traversing the multigon clockwise, always picking the leftmost path. - * Prerequisites - the ways must not intersect and have common end nodes where they meet. - * @param Collection A list of (splitted) ways that form a multigon - * @return Collection A list of ways that form the outer boundary of the multigon. - */ - private static ArrayList findOuterWays(Collection multigonWays) { - - //find the node with minimum lat - it's guaranteed to be outer. (What about the south pole?) - Way bestWay = null; - Node topNode = null; - int topIndex = 0; - double minLat = Double.POSITIVE_INFINITY; - - for(Way way: multigonWays) { - for (int pos = 0; pos < way.getNodesCount(); pos ++) { - Node node = way.getNode(pos); - - if (node.getCoor().lat() < minLat) { - minLat = node.getCoor().lat(); - bestWay = way; - topNode = node; - topIndex = pos; - } - } - } - - //get two final nodes from best way to mark as starting point and orientation. - Node headNode = null; - Node prevNode = null; - - if (topNode.equals(bestWay.firstNode()) || topNode.equals(bestWay.lastNode())) { - //node is in split point - headNode = topNode; - //make a fake node that is downwards from head node (smaller latitude). It will be a division point between paths. - prevNode = new Node(new LatLon(headNode.getCoor().lat() - 1000, headNode.getCoor().lon())); - } else { - //node is inside way - pick the clockwise going end. - Node prev = bestWay.getNode(topIndex - 1); - Node next = bestWay.getNode(topIndex + 1); - - if (angleIsClockwise(prev, topNode, next)) { - headNode = bestWay.lastNode(); - prevNode = bestWay.getNode(bestWay.getNodesCount() - 2); - } - else { - headNode = bestWay.firstNode(); - prevNode = bestWay.getNode(1); - } - } - - Set outerWays = new HashSet(); - ArrayList result = new ArrayList(); - - //iterate till full circle is reached - while (true) { - - bestWay = null; - Node bestWayNextNode = null; - boolean bestWayReverse = false; - - for (Way way: multigonWays) { - boolean wayReverse; - Node nextNode; - - if (way.firstNode().equals(headNode)) { - //start adjacent to headNode - nextNode = way.getNode(1); - wayReverse = false; - - if (nextNode.equals(prevNode)) { - //this is the path we came from - ignore it. - } else if (bestWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { - //the new way is better - bestWay = way; - bestWayReverse = wayReverse; - bestWayNextNode = nextNode; + + /** + * This method finds witch ways are outer and witch are inner. + * @param boundaryWays + * @return + */ + private List findPolygons(Collection boundaries) { + + List list = findOuterWaysImpl(0, boundaries); + List result = new ArrayList(); + + //take every other level + for (PolygonLevel pol : list) { + if (pol.level % 2 == 0) { + result.add(pol.pol); + } + } + + return result; + } + + /** + * Collects outer way and corresponding inner ways from all boundaries. + * @param boundaryWays + * @return the outermostWay. + */ + private List findOuterWaysImpl(int level, Collection boundaryWays) { + + //TODO: bad performance for deep nestings... + List result = new ArrayList(); + + for (AssembledPolygon outerWay : boundaryWays) { + + boolean outerGood = true; + List innerCandidates = new ArrayList(); + + for (AssembledPolygon innerWay : boundaryWays) { + if (innerWay == outerWay) { + continue; + } + + if (wayInsideWay(outerWay, innerWay)) { + outerGood = false; + break; + } else if (wayInsideWay(innerWay, outerWay)) { + innerCandidates.add(innerWay); + } + } + + if (!outerGood) { + continue; + } + + //add new outer polygon + AssembledMultipolygon pol = new AssembledMultipolygon(outerWay); + PolygonLevel polLev = new PolygonLevel(pol, level); + + //process inner ways + if (innerCandidates.size() > 0) { + List innerList = findOuterWaysImpl(level + 1, innerCandidates); + result.addAll(innerList); + + for (PolygonLevel pl : innerList) { + if (pl.level == level + 1) { + pol.innerWays.add(pl.pol.outerWay); } } - - if (way.lastNode().equals(headNode)) { - //end adjacent to headNode - nextNode = way.getNode(way.getNodesCount() - 2); - wayReverse = true; - - if (nextNode.equals(prevNode)) { - //this is the path we came from - ignore it. - } else if (bestWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { - //the new way is better - bestWay = way; - bestWayReverse = wayReverse; - bestWayNextNode = nextNode; - } - } - } - - if (bestWay == null) - throw new RuntimeException(); - else if (outerWays.contains(bestWay)) { - break; //full circle reached, terminate. + } + + result.add(polLev); + } + + return result; + } + + + + /** + * Finds all ways that form inner or outer boundaries. + * @param Collection A list of (splitted) ways that form a multigon and share common end nodes on intersections. + * @param Collection this list is filled with ways that are to be discarded + * @return Collection> A list of ways that form the outer and inner boundaries of the multigon. + */ + public static List findBoundaryPolygons(Collection multigonWays, List discardedResult) { + //first find all discardable ways, by getting outer shells. + //this will produce incorrect boundaries in some cases, but second pass will fix it. + + List discardedWays = new ArrayList(); + Set processedWays = new HashSet(); + WayTraverser traverser = new WayTraverser(multigonWays); + + for (WayInPolygon startWay : multigonWays) { + if (processedWays.contains(startWay)) { + continue; + } + + traverser.startNewWay(startWay); + + List boundary = new ArrayList(); + WayInPolygon lastWay = startWay; + + while (true) { + boundary.add(lastWay); + + WayInPolygon bestWay = traverser.advanceNextLeftmostWay(); + boolean wayInsideToTheRight = bestWay == null ? false : traverser.isLastWayInsideToTheRight(); + + if (bestWay == null || processedWays.contains(bestWay) || !wayInsideToTheRight) { + //bad segment chain - proceed to discard it + lastWay = null; + break; + } else if (boundary.contains(bestWay)) { + //traversed way found - close the way + lastWay = bestWay; + break; + } else { + //proceed to next segment + lastWay = bestWay; + } + } + + if (lastWay != null) { + //way good + processedWays.addAll(boundary); + + //remove junk segments at the start + while (boundary.get(0) != lastWay) { + discardedWays.add(boundary.get(0)); + boundary.remove(0); + } } else { - //add to outer ways, repeat. - outerWays.add(bestWay); - result.add(new WayInPath(bestWay, bestWayReverse)); - headNode = bestWayReverse ? bestWay.firstNode() : bestWay.lastNode(); - prevNode = bestWayReverse ? bestWay.getNode(1) : bestWay.getNode(bestWay.getNodesCount() - 2); - } - } + //way bad + discardedWays.addAll(boundary); + processedWays.addAll(boundary); + } + } + + //now we have removed junk segments, collect the real result ways + + traverser.removeWays(discardedWays); + + List result = new ArrayList(); + + while (traverser.hasWays()) { + + WayInPolygon startWay = traverser.startNewWay(); + List boundary = new ArrayList(); + WayInPolygon curWay = startWay; + + do { + boundary.add(curWay); + curWay = traverser.advanceNextRightmostWay(); + + //should not happen + if (curWay == null || !traverser.isLastWayInsideToTheRight()) + throw new RuntimeException("Join areas internal error."); + + } while (curWay != startWay); + + //build result + traverser.removeWays(boundary); + result.add(new AssembledPolygon(boundary)); + } + + for (WayInPolygon way : discardedWays) { + discardedResult.add(way.way); + } + + //split inner polygons that have several touching parts. + result = fixTouchingPolygons(result); return result; } + + + /** + * This method checks if polygons have several touching parts and splits them in several polygons. + * @param polygon the polygon to process. + */ + public static List fixTouchingPolygons(List polygons) + { + List newPolygons = new ArrayList(); + + for (AssembledPolygon innerPart : polygons) { + WayTraverser traverser = new WayTraverser(innerPart.ways); + + while (traverser.hasWays()) { + + WayInPolygon startWay = traverser.startNewWay(); + List boundary = new ArrayList(); + WayInPolygon curWay = startWay; + + Node startNode = traverser.getLastWayStartNode(); + boundary.add(curWay); + + while (startNode != traverser.getLastWayEndNode()) { + curWay = traverser.advanceNextLeftmostWay(); + boundary.add(curWay); + + //should not happen + if (curWay == null || !traverser.isLastWayInsideToTheRight()) + throw new RuntimeException("Join areas internal error."); + } + + //build result + traverser.removeWays(boundary); + newPolygons.add(new AssembledPolygon(boundary)); + } + } + + return newPolygons; + } + /** @@ -766,6 +1328,5 @@ * @return true if to the right side, false otherwise */ - public static boolean isToTheRightSideOfLine(Node lineP1, Node lineP2, Node lineP3, Node testPoint) - { + public static boolean isToTheRightSideOfLine(Node lineP1, Node lineP2, Node lineP3, Node testPoint) { boolean pathBendToRight = angleIsClockwise(lineP1, lineP2, lineP3); boolean rightOfSeg1 = angleIsClockwise(lineP1, lineP2, testPoint); @@ -785,12 +1346,33 @@ * @return true if first vector is clockwise before second vector. */ - public static boolean angleIsClockwise(Node commonNode, Node firstNode, Node secondNode) - { - double dla1 = (firstNode.getCoor().lat() - commonNode.getCoor().lat()); - double dla2 = (secondNode.getCoor().lat() - commonNode.getCoor().lat()); - double dlo1 = (firstNode.getCoor().lon() - commonNode.getCoor().lon()); - double dlo2 = (secondNode.getCoor().lon() - commonNode.getCoor().lon()); - - return dla1 * dlo2 - dlo1 * dla2 > 0; + + public static boolean angleIsClockwise(Node commonNode, Node firstNode, Node secondNode) { + double dy1 = (firstNode.getEastNorth().getY() - commonNode.getEastNorth().getY()); + double dy2 = (secondNode.getEastNorth().getY() - commonNode.getEastNorth().getY()); + double dx1 = (firstNode.getEastNorth().getX() - commonNode.getEastNorth().getX()); + double dx2 = (secondNode.getEastNorth().getX() - commonNode.getEastNorth().getX()); + + return dy1 * dx2 - dx1 * dy2 > 0; + } + + + /** + * Tests if way is inside other way + * @param outside + * @param inside + * @return + */ + public static boolean wayInsideWay(AssembledPolygon inside, AssembledPolygon outside) { + Set outsideNodes = new HashSet(outside.getNodes()); + + for (Node insideNode : inside.getNodes()) { + + if (!outsideNodes.contains(insideNode)) + //simply test the one node + return nodeInsidePolygon(insideNode, outside.getNodes()); + } + + //all nodes shared. + return false; } @@ -802,6 +1384,5 @@ * FIXME: this should probably be moved to tools.. */ - public static boolean nodeInsidePolygon(ArrayList polygonNodes, Node point) - { + public static boolean nodeInsidePolygon(Node point, List polygonNodes) { if (polygonNodes.size() < 3) return false; @@ -813,6 +1394,5 @@ Node oldPoint = polygonNodes.get(polygonNodes.size() - 1); - for(Node newPoint: polygonNodes) - { + for (Node newPoint : polygonNodes) { //skip duplicate points if (newPoint.equals(oldPoint)) { @@ -821,11 +1401,8 @@ //order points so p1.lat <= p2.lat; - if (newPoint.getCoor().lat() > oldPoint.getCoor().lat()) - { + if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) { p1 = oldPoint; p2 = newPoint; - } - else - { + } else { p1 = newPoint; p2 = oldPoint; @@ -833,7 +1410,7 @@ //test if the line is crossed and if so invert the inside flag. - if ((newPoint.getCoor().lat() < point.getCoor().lat()) == (point.getCoor().lat() <= oldPoint.getCoor().lat()) - && (point.getCoor().lon() - p1.getCoor().lon()) * (p2.getCoor().lat() - p1.getCoor().lat()) - < (p2.getCoor().lon() - p1.getCoor().lon()) * (point.getCoor().lat() - p1.getCoor().lat())) + if ((newPoint.getEastNorth().getY() < point.getEastNorth().getY()) == (point.getEastNorth().getY() <= oldPoint.getEastNorth().getY()) + && (point.getEastNorth().getX() - p1.getEastNorth().getX()) * (p2.getEastNorth().getY() - p1.getEastNorth().getY()) + < (p2.getEastNorth().getX() - p1.getEastNorth().getX()) * (point.getEastNorth().getY() - p1.getEastNorth().getY())) { inside = !inside; @@ -845,4 +1422,21 @@ return inside; } + + + /** + * Joins the lists of ways. + * @param Collection The list of outer ways that belong to that multigon. + * @return Way The newly created outer way + */ + private Multipolygon joinPolygon(AssembledMultipolygon polygon) throws UserCancelException { + Multipolygon result = new Multipolygon(joinWays(polygon.outerWay.ways)); + + for (AssembledPolygon pol : polygon.innerWays) { + result.innerWays.add(joinWays(pol.ways)); + } + + return result; + } + /** @@ -851,41 +1445,27 @@ * @return Way The newly created outer way */ - private Way joinOuterWays(ArrayList outerWays) { + private Way joinWays(List ways) throws UserCancelException { //leave original orientation, if all paths are reverse. boolean allReverse = true; - for(WayInPath way: outerWays) { - allReverse &= way.insideToTheLeft; + for (WayInPolygon way : ways) { + allReverse &= !way.insideToTheRight; } if (allReverse) { - for(WayInPath way: outerWays){ - way.insideToTheLeft = !way.insideToTheLeft; - } - } - - commitCommands(marktr("Join Areas: Remove Short Ways")); - Way joinedWay = joinOrientedWays(outerWays); - if (joinedWay != null) - return closeWay(joinedWay); - else - return null; - } - - /** - * Ensures a way is closed. If it isn't, last and first node are connected. - * @param Way the way to ensure it's closed - * @return Way The joined way. - */ - private Way closeWay(Way w) { - if(w.isClosed()) - return w; - Main.main.getCurrentDataSet().setSelected(w); - Way wnew = new Way(w); - wnew.addNode(wnew.firstNode()); - cmds.add(new ChangeCommand(w, wnew)); - commitCommands(marktr("Closed Way")); - return (Way)(Main.main.getCurrentDataSet().getSelectedWays().toArray())[0]; - } + for (WayInPolygon way : ways) { + way.insideToTheRight = !way.insideToTheRight; + } + } + + Way joinedWay = joinOrientedWays(ways); + + //should not happen + if (joinedWay == null || !joinedWay.isClosed()) + throw new RuntimeException("Join areas internal error."); + + return joinedWay; + } + /** @@ -894,6 +1474,6 @@ * @return Way The newly created way */ - private Way joinOrientedWays(ArrayList ways) { - if(ways.size() < 2) + private Way joinOrientedWays(List ways) throws UserCancelException{ + if (ways.size() < 2) return ways.get(0).way; @@ -901,240 +1481,146 @@ // the user about this. + //TODO: ReverseWay and Combine way are really slow and we use them a lot here. This slows down large joins. List actionWays = new ArrayList(ways.size()); - for(WayInPath way : ways) { + for (WayInPolygon way : ways) { actionWays.add(way.way); - if (way.insideToTheLeft) { - Main.main.getCurrentDataSet().setSelected(way.way); - new ReverseWayAction().actionPerformed(null); + if (!way.insideToTheRight) { + ReverseWayResult res = ReverseWayAction.reverseWay(way.way); + Main.main.undoRedo.add(res.getReverseCommand()); cmdsCount++; } } - Way result = new CombineWayAction().combineWays(actionWays); - - if(result != null) { - cmdsCount++; - } + Pair result = CombineWayAction.combineWaysWorker(actionWays); + + Main.main.undoRedo.add(result.b); + cmdsCount ++; + + return result.a; + } + + + /** + * This method analyzes multipolygon relationships of given ways and collects addition inner ways to consider. + * @param selectedWays the selected ways + * @return list of polygons, or null if too complex relation encountered. + */ + private List collectMultipolygons(List selectedWays) { + + List result = new ArrayList(); + + //prepare the lists, to minimize memory allocation. + List outerWays = new ArrayList(); + List innerWays = new ArrayList(); + + Set processedOuterWays = new LinkedHashSet(); + Set processedInnerWays = new LinkedHashSet(); + + for (Relation r : CombineWayAction.getParentRelations(selectedWays)) { + if (r.isDeleted() || + r.get("type") == null || + !r.get("type").equalsIgnoreCase("multipolygon")) { + continue; + } + + boolean hasKnownOuter = false; + outerWays.clear(); + innerWays.clear(); + + for (RelationMember rm : r.getMembers()) { + if (rm.getRole().equalsIgnoreCase("outer")) { + outerWays.add(rm.getWay()); + hasKnownOuter |= selectedWays.contains(rm.getWay()); + } + else if (rm.getRole().equalsIgnoreCase("inner")) { + innerWays.add(rm.getWay()); + } + } + + if (!hasKnownOuter) { + continue; + } + + if (outerWays.size() > 1) { + JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle multipolygon relations with multiple outer ways.")); + return null; + } + + Way outerWay = outerWays.get(0); + + //retain only selected inner ways + innerWays.retainAll(selectedWays); + + if (processedOuterWays.contains(outerWay)) { + JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is outer in multiple multipolygon relations.")); + return null; + } + + if (processedInnerWays.contains(outerWay)) { + JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations.")); + return null; + } + + for (Way way :innerWays) + { + if (processedOuterWays.contains(way)) { + JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations.")); + return null; + } + + if (processedInnerWays.contains(way)) { + JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is inner in multiple multipolygon relations.")); + return null; + } + } + + processedOuterWays.add(outerWay); + processedInnerWays.addAll(innerWays); + + Multipolygon pol = new Multipolygon(outerWay); + pol.innerWays.addAll(innerWays); + pol.relation = r; + + result.add(pol); + } + + //add remaining ways, not in relations + for (Way way : selectedWays) { + if (processedOuterWays.contains(way) || processedInnerWays.contains(way)) { + continue; + } + + result.add(new Multipolygon(way)); + } + return result; } - /** - * Joins a list of ways (using CombineWayAction and ReverseWayAction if necessary to quiet the former) - * @param ArrayList The list of ways to join - * @return Way The newly created way - */ - private Way joinWays(ArrayList ways) { - if(ways.size() < 2) - return ways.get(0); - - // This will turn ways so all of them point in the same direction and CombineAction won't bug - // the user about this. - Way a = null; - for (Way b : ways) { - if(a == null) { - a = b; - continue; - } - if(a.getNode(0).equals(b.getNode(0)) || - a.getNode(a.getNodesCount()-1).equals(b.getNode(b.getNodesCount()-1))) { - Main.main.getCurrentDataSet().setSelected(b); - new ReverseWayAction().actionPerformed(null); - cmdsCount++; - } - a = b; - } - if ((a = new CombineWayAction().combineWays(ways)) != null) { - cmdsCount++; - } - return a; - } - - /** - * Finds all ways that may be part of a multipolygon relation and removes them from the given list. - * It will automatically combine "good" ways - * @param Collection The list of inner ways to check - * @param Way The newly created outer way - * @return ArrayList The List of newly created inner ways - */ - private ArrayList fixMultipolygons(Collection uninterestingWays, Way outerWay, boolean selfintersect) { - Collection innerNodes = getNodesFromWays(uninterestingWays); - Collection outerNodes = outerWay.getNodes(); - - // The newly created inner ways. uninterestingWays is passed by reference and therefore modified in-place - ArrayList newInnerWays = new ArrayList(); - - // Now we need to find all inner ways that contain a remaining node, but no outer nodes - // Remaining nodes are those that contain to more than one way. All nodes that belong to an - // inner multigon part will have at least two ways, so we can use this to find which ways do - // belong to the multigon. - ArrayList possibleWays = new ArrayList(); - wayIterator: for(Way w : uninterestingWays) { - boolean hasInnerNodes = false; - for(Node n : w.getNodes()) { - if(outerNodes.contains(n)) { - if(!selfintersect) { // allow outer point for self intersection - continue wayIterator; - } - } - else if(!hasInnerNodes && innerNodes.contains(n)) { - hasInnerNodes = true; - } - } - if(!hasInnerNodes || w.getNodesCount() < 2) { - continue; - } - possibleWays.add(w); - } - - // This removes unnecessary ways that might have been added. - removeAlmostAlikeWays(possibleWays); - - // loop twice - // in k == 0 prefer ways which allow no Y-joining (i.e. which have only 1 solution) - for(int k = 0; k < 2; ++k) - { - // Join all ways that have one start/ending node in common - Way joined = null; - outerIterator: do { - removePartlyUnconnectedWays(possibleWays); - joined = null; - for(Way w1 : possibleWays) { - if(w1.isClosed()) { - if(!wayIsCollapsed(w1)) { - uninterestingWays.remove(w1); - newInnerWays.add(w1); - } - joined = w1; - possibleWays.remove(w1); - continue outerIterator; - } - ArrayList secondary = new ArrayList(); - for(Way w2 : possibleWays) { - int i = 0; - // w2 cannot be closed, otherwise it would have been removed above - if(w1.equals(w2)) { - continue; - } - if(w2.isFirstLastNode(w1.firstNode())) { - ++i; - } - if(w2.isFirstLastNode(w1.lastNode())) { - ++i; - } - if(i == 2) // this way closes w1 - take it! - { - if(secondary.size() > 0) { - secondary.clear(); - } - secondary.add(w2); - break; - } - else if(i > 0) { - secondary.add(w2); - } - } - if(k == 0 ? secondary.size() == 1 : secondary.size() > 0) - { - ArrayList joinThem = new ArrayList(); - joinThem.add(w1); - joinThem.add(secondary.get(0)); - // Although we joined the ways, we cannot simply assume that they are closed - if((joined = joinWays(joinThem)) != null) - { - uninterestingWays.removeAll(joinThem); - possibleWays.removeAll(joinThem); - - //List nodes = joined.getNodes(); - // check if we added too much - /*for(int i = 1; i < nodes.size()-2; ++i) - { - if(nodes.get(i) == nodes.get(nodes.size()-1)) - System.out.println("Joining of ways produced unexpecteded result\n"); - }*/ - uninterestingWays.add(joined); - possibleWays.add(joined); - continue outerIterator; - } - } - } - } while(joined != null); - } - return newInnerWays; - } - - /** - * Removes almost alike ways (= ways that are on top of each other for all nodes) - * @param ArrayList the ways to remove almost-duplicates from - */ - private void removeAlmostAlikeWays(ArrayList ways) { - Collection removables = new ArrayList(); - outer: for(int i=0; i < ways.size(); i++) { - Way a = ways.get(i); - for(int j=i+1; j < ways.size(); j++) { - Way b = ways.get(j); - List revNodes = new ArrayList(b.getNodes()); - Collections.reverse(revNodes); - if(a.getNodes().equals(b.getNodes()) || a.getNodes().equals(revNodes)) { - removables.add(a); - continue outer; - } - } - } - ways.removeAll(removables); - } - - /** - * Removes ways from the given list whose starting or ending node doesn't - * connect to other ways from the same list (it's like removing spikes). - * @param ArrayList The list of ways to remove "spikes" from - */ - private void removePartlyUnconnectedWays(ArrayList ways) { - List removables = new ArrayList(); - for(Way a : ways) { - if(a.isClosed()) { - continue; - } - boolean connectedStart = false; - boolean connectedEnd = false; - for(Way b : ways) { - if(a.equals(b)) { - continue; - } - if(b.isFirstLastNode(a.firstNode())) { - connectedStart = true; - } - if(b.isFirstLastNode(a.lastNode())) { - connectedEnd = true; - } - } - if(!connectedStart || !connectedEnd) { - removables.add(a); - } - } - ways.removeAll(removables); - } - - /** - * Checks if a way is collapsed (i.e. looks like <---->) - * @param Way A *closed* way to check if it is collapsed - * @return boolean If the closed way is collapsed or not - */ - private boolean wayIsCollapsed(Way w) { - if(w.getNodesCount() <= 3) return true; - - // If a way contains more than one node twice, it must be collapsed (only start/end node may be the same) - Way x = new Way(w); - int count = 0; - for(Node n : w.getNodes()) { - x.removeNode(n); - if(x.containsNode(n)) { - count++; - } - if(count == 2) return true; - } - return false; - } + + /** + * This method filters the list of relations that form the multipolygons. + * @param relations + * @param polygons + * @return + */ + private List filterOwnMultipolygonRelations(Collection relations, List polygons) { + + List relationsToRemove = new ArrayList(); + + for (Multipolygon m : polygons) { + if (m.relation != null) { + relationsToRemove.add(m.relation); + } + } + + List result = new ArrayList(); + + result.addAll(relations); + result.removeAll(relationsToRemove); + return result; + } + /** @@ -1145,9 +1631,9 @@ */ private void addOwnMultigonRelation(Collection inner, Way outer, ArrayList rels) { - if(inner.size() == 0) return; + if (inner.size() == 0) return; // Create new multipolygon relation and add all inner ways to it Relation newRel = new Relation(); newRel.put("type", "multipolygon"); - for(Way w : inner) { + for (Way w : inner) { newRel.addMember(new RelationMember("inner", w)); } @@ -1161,4 +1647,41 @@ } + + /** + * Removes a given OsmPrimitive from all relations + * @param OsmPrimitive Element to remove from all relations + * @return ArrayList List of relations with roles the primitives was part of + */ + private ArrayList removeFromAllRelations(OsmPrimitive osm) { + ArrayList result = new ArrayList(); + + for (Relation r : Main.main.getCurrentDataSet().getRelations()) { + if (r.isDeleted()) { + continue; + } + for (RelationMember rm : r.getMembers()) { + if (rm.getMember() != osm) { + continue; + } + + Relation newRel = new Relation(r); + List members = newRel.getMembers(); + members.remove(rm); + newRel.setMembers(members); + + cmds.add(new ChangeCommand(r, newRel)); + RelationRole saverel = new RelationRole(r, rm.getRole()); + if (!result.contains(saverel)) { + result.add(saverel); + } + break; + } + } + + commitCommands(marktr("Removed Element from Relations")); + return result; + } + + /** * Adds the previously removed relations again to the outer way. If there are multiple multipolygon @@ -1170,6 +1693,6 @@ private void fixRelations(ArrayList rels, Way outer) { ArrayList multiouters = new ArrayList(); - for(RelationRole r : rels) { - if( r.rel.get("type") != null && + for (RelationRole r : rels) { + if (r.rel.get("type") != null && r.rel.get("type").equalsIgnoreCase("multipolygon") && r.role.equalsIgnoreCase("outer") @@ -1185,5 +1708,5 @@ Relation newRel = null; - switch(multiouters.size()) { + switch (multiouters.size()) { case 0: return; @@ -1197,8 +1720,8 @@ // Create a new relation with all previous members and (Way)outer as outer. newRel = new Relation(); - for(RelationRole r : multiouters) { + for (RelationRole r : multiouters) { // Add members - for(RelationMember rm : r.rel.getMembers()) - if(!newRel.getMembers().contains(rm)) { + for (RelationMember rm : r.rel.getMembers()) + if (!newRel.getMembers().contains(rm)) { newRel.addMember(rm); } @@ -1219,5 +1742,5 @@ */ private void stripTags(Collection ways) { - for(Way w: ways) { + for (Way w : ways) { stripTags(w); } @@ -1229,5 +1752,6 @@ */ private void stripTags(Way x) { - if(x.getKeys() == null) return; + if (x.getKeys() == null) + return; Way y = new Way(x); for (String key : x.keySet()) { @@ -1246,9 +1770,9 @@ cmds.clear(); int i = Math.max(ur.commands.size() - cmdsCount, 0); - for(; i < ur.commands.size(); i++) { + for (; i < ur.commands.size(); i++) { cmds.add(ur.commands.get(i)); } - for(i = 0; i < cmds.size(); i++) { + for (i = 0; i < cmds.size(); i++) { ur.undo(); }