Index: /trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java =================================================================== --- /trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java (revision 3444) +++ /trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java (revision 3445) @@ -15,4 +15,6 @@ import java.util.HashMap; import java.util.HashSet; +import java.util.LinkedHashMap; +import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.List; @@ -113,5 +115,7 @@ return null; ways.remove(null); // just in case - remove all null ways from the collection - ways = new HashSet(ways); // remove duplicates + + // remove duplicates, preserving order + ways = new LinkedHashSet(ways); // try to build a new way which includes all the combined @@ -474,7 +478,7 @@ protected void prepare() { - Set undirectedEdges = new HashSet(); - successors = new HashMap>(); - predecessors = new HashMap>(); + Set undirectedEdges = new LinkedHashSet(); + successors = new LinkedHashMap>(); + predecessors = new LinkedHashMap>(); for (NodePair pair: edges) { @@ -489,5 +493,5 @@ public NodeGraph() { - edges = new HashSet(); + edges = new LinkedHashSet(); } @@ -514,5 +518,5 @@ protected Set getTerminalNodes() { - Set ret = new HashSet(); + Set ret = new LinkedHashSet(); for (Node n: getNodes()) { if (isTerminalNode(n)) { @@ -524,5 +528,5 @@ protected Set getNodes(Stack pairs) { - HashSet nodes = new HashSet(); + HashSet nodes = new LinkedHashSet(); for (NodePair pair: pairs) { nodes.add(pair.getA()); @@ -544,5 +548,5 @@ protected Set getNodes() { - Set nodes = new HashSet(); + Set nodes = new LinkedHashSet(); for (NodePair pair: edges) { nodes.add(pair.getA()); Index: /trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java =================================================================== --- /trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 3444) +++ /trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 3445) @@ -7,5 +7,4 @@ import java.awt.GridBagLayout; -import java.awt.Polygon; import java.awt.event.ActionEvent; import java.awt.event.KeyEvent; @@ -16,4 +15,5 @@ import java.util.Collections; import java.util.HashMap; +import java.util.HashSet; import java.util.LinkedList; import java.util.List; @@ -31,4 +31,5 @@ import org.openstreetmap.josm.Main; +import org.openstreetmap.josm.actions.SplitWayAction.SplitWayResult; import org.openstreetmap.josm.command.AddCommand; import org.openstreetmap.josm.command.ChangeCommand; @@ -55,4 +56,19 @@ private int cmdsCount = 0; + /** + * This helper class describes join ares action result. + * @author viesturs + * + */ + 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 @@ -107,4 +123,33 @@ RelationRole otherMember = (RelationRole) other; return otherMember.role.equals(role) && otherMember.rel.equals(rel); + } + } + + /** + * 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 { + public final Way way; + public boolean insideToTheLeft; + + public WayInPath(Way way, boolean insideLeft) { + this.way = way; + this.insideToTheLeft = insideLeft; + } + + @Override + public int hashCode() { + return way.hashCode(); + } + + @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; } } @@ -164,5 +209,11 @@ } - if(joinAreas(ways.getFirst(), ways.getLast())) { + if (checkForTagConflicts(ways.getFirst(), ways.getLast())) { + //do nothing. //FIXME: abort? + } + + JoinAreasResult result = joinAreas(ways.getFirst(), ways.getLast()); + + if (result.hasChanges) { Main.map.mapView.repaint(); DataSet ds = Main.main.getCurrentDataSet(); @@ -177,25 +228,36 @@ * @param Way First way/area * @param Way Second way/area - * @return boolean Whether to display the "no operation" message - */ - private boolean joinAreas(Way a, Way b) { + */ + private JoinAreasResult joinAreas(Way a, Way b) { + + JoinAreasResult result = new JoinAreasResult(); + result.hasChanges = false; + // Fix self-overlapping first or other errors boolean same = a.equals(b); - boolean hadChanges = false; if(!same) { int i = 0; - if(checkForTagConflicts(a, b)) return true; // User aborted, so don't warn again - if(joinAreas(a, a)) { + + //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(joinAreas(b, b)) { + if(resultB.mergeSuccessful) { + b = resultB.outerWay; ++i; } - hadChanges = i > 0; + + result.hasChanges = i > 0; cmdsCount = i; } - ArrayList nodes = addIntersections(a, b); - if(nodes.size() == 0) return hadChanges; + ArrayList nodes = addIntersections(a, b); + + //no intersections, return. + if(nodes.size() == 0) return result; commitCommands(marktr("Added node on all intersections")); @@ -209,17 +271,15 @@ boolean warnAboutRelations = relations.size() > 0; - Collection allWays = splitWaysOnNodes(a, b, nodes); - - // Find all nodes and inner ways save them to a list - Collection allNodes = getNodesFromWays(allWays); - Collection innerWays = findInnerWays(allWays, allNodes); + 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(allWays, innerWays); - if (outerWay == null) - return true; + Way outerWay = joinOuterWays(outerWays); // Fix Multipolygons if there are any - Collection newInnerWays = fixMultipolygons(innerWays, outerWay, same); + List newInnerWays = fixMultipolygons(innerWays, outerWay, same); // Delete the remaining inner ways @@ -235,4 +295,5 @@ stripTags(newInnerWays); + makeCommitsOneAction( same @@ -245,5 +306,9 @@ } - return true; + result.mergeSuccessful = true; + result.outerWay = outerWay; + result.innerWays = newInnerWays; + + return result; } @@ -331,12 +396,10 @@ * @return ArrayList List of new nodes */ - private ArrayList addIntersections(Way a, Way b) { + private ArrayList addIntersections(Way a, Way b) { boolean same = a.equals(b); int nodesSizeA = a.getNodesCount(); int nodesSizeB = b.getNodesCount(); - // We use OsmPrimitive here instead of Node because we later need to split a way at these nodes. - // With OsmPrimitve we can simply add the way and don't have to loop over the nodes - ArrayList nodes = new ArrayList(); + ArrayList nodes = new ArrayList(); ArrayList nodesA = new ArrayList(); ArrayList nodesB = new ArrayList(); @@ -489,38 +552,55 @@ /** - * This is a hacky implementation to make use of the splitWayAction code and - * should be improved. SplitWayAction needs to expose its splitWay function though. - */ - private Collection splitWaysOnNodes(Way a, Way b, Collection nodes) { - ArrayList ways = new ArrayList(); + * This method splits ways 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) { + + ArrayList result = new ArrayList(); + List ways = new ArrayList(); ways.add(a); - if(!a.equals(b)) { - ways.add(b); - } - - List affected = new ArrayList(); - for (Way way : ways) { - nodes.add(way); - Main.main.getCurrentDataSet().setSelected(nodes); - nodes.remove(way); - new SplitWayAction().actionPerformed(null); - cmdsCount++; - affected.addAll(Main.main.getCurrentDataSet().getSelectedWays()); - } - return osmprim2way(affected); - } - - /** - * Converts a list of OsmPrimitives to a list of Ways - * @param Collection The OsmPrimitives list that's needed as a list of Ways - * @return Collection The list as list of Ways - */ - static private Collection osmprim2way(Collection ways) { - Collection result = new ArrayList(); - for(OsmPrimitive w: ways) { - if(w instanceof Way) { - result.add((Way) w); - } - } + ways.add(b); + + for (Way way: ways) { + List> chunks = buildNodeChunks(way, nodes); + 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 ++; + + result.add(split.getOriginalWay()); + result.addAll(split.getNewWays()); + } + + return result; + } + + /** + * Simple chunking version. Does not care about circular ways and result being proper, we will glue it all back together later on. + * @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) + { + List> result = new ArrayList>(); + List curList = new ArrayList(); + + for(Node node: way.getNodes()){ + curList.add(node); + if (curList.size() > 1 && splitNodes.contains(node)){ + result.add(curList); + curList = new ArrayList(); + curList.add(node); + } + } + + if (curList.size() > 1) + { + result.add(curList); + } + return result; } @@ -540,74 +620,249 @@ /** - * Finds all inner ways for a given list of Ways and Nodes from a multigon by constructing a polygon - * for each way, looking for inner nodes that are not part of this way. If a node is found, all ways - * containing this node are added to the list + * 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 - * @param Collection A list of nodes that belong to the multigon - * @return Collection A list of ways that are positioned inside the outer borders of the multigon - */ - private Collection findInnerWays(Collection multigonWays, Collection multigonNodes) { - Collection innerWays = new ArrayList(); - for(Way w: multigonWays) { - Polygon poly = new Polygon(); - for(Node n: (w).getNodes()) { - poly.addPoint(latlonToXY(n.getCoor().lat()), latlonToXY(n.getCoor().lon())); - } - - for(Node n: multigonNodes) { - if(!(w).containsNode(n) && poly.contains(latlonToXY(n.getCoor().lat()), latlonToXY(n.getCoor().lon()))) { - getWaysByNode(innerWays, multigonWays, n); - } - } - } - - return innerWays; - } - - // Polygon only supports int coordinates, so convert them - private int latlonToXY(double val) { - return (int)Math.round(val*1000000); - } - - /** - * Finds all ways that contain the given node. - * @param Collection A list to which matching ways will be added - * @param Collection A list of ways to check - * @param Node The node the ways should be checked against - */ - private void getWaysByNode(Collection innerWays, Collection w, Node n) { - for(Way way : w) { - if(!(way).containsNode(n)) { + * @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; + } + } + + 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. + 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); + } + } + + return result; + } + + /** + * Tests if given point is to the right side of path consisting of 3 points. + * @param lineP1 first point in path + * @param lineP2 second point in path + * @param lineP3 third point in path + * @param testPoint + * @return true if to the right side, false otherwise + */ + public static boolean isToTheRightSideOfLine(Node lineP1, Node lineP2, Node lineP3, Node testPoint) + { + boolean pathBendToRight = angleIsClockwise(lineP1, lineP2, lineP3); + boolean rightOfSeg1 = angleIsClockwise(lineP1, lineP2, testPoint); + boolean rightOfSeg2 = angleIsClockwise(lineP2, lineP3, testPoint); + + if (pathBendToRight) + return rightOfSeg1 && rightOfSeg2; + else + return !(!rightOfSeg1 && !rightOfSeg2); + } + + /** + * This method tests if secondNode is clockwise to first node. + * @param commonNode starting point for both vectors + * @param firstNode first vector end node + * @param secondNode second vector end node + * @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; + } + + /** + * Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner. + * @param polygonNodes list of nodes from polygon path. + * @param point the point to test + * @return true if the point is inside polygon. + * FIXME: this should probably be moved to tools.. + */ + public static boolean nodeInsidePolygon(ArrayList polygonNodes, Node point) + { + if (polygonNodes.size() < 3) + return false; + + boolean inside = false; + Node p1, p2; + + //iterate each side of the polygon, start with the last segment + Node oldPoint = polygonNodes.get(polygonNodes.size() - 1); + + for(Node newPoint: polygonNodes) + { + //skip duplicate points + if (newPoint.equals(oldPoint)) { continue; } - if(!innerWays.contains(way)) { - innerWays.add(way); // Will need this later for multigons - } - } - } - - /** - * Joins the two outer ways and deletes all short ways that can't be part of a multipolygon anyway - * @param Collection The list of all ways that belong to that multigon - * @param Collection The list of inner ways that belong to that multigon + + //order points so p1.lat <= p2.lat; + if (newPoint.getCoor().lat() > oldPoint.getCoor().lat()) + { + p1 = oldPoint; + p2 = newPoint; + } + else + { + p1 = newPoint; + p2 = oldPoint; + } + + //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())) + { + inside = !inside; + } + + oldPoint = newPoint; + } + + return inside; + } + + /** + * Joins the outer ways and deletes all short ways that can't be part of a multipolygon anyway. + * @param Collection The list of outer ways that belong to that multigon. * @return Way The newly created outer way */ - private Way joinOuterWays(Collection multigonWays, Collection innerWays) { - ArrayList join = new ArrayList(); - for(Way w: multigonWays) { - // Skip inner ways - if(innerWays.contains(w)) { - continue; - } - - if(w.getNodesCount() <= 2) { - cmds.add(new DeleteCommand(w)); - } else { - join.add(w); + private Way joinOuterWays(ArrayList outerWays) { + + //leave original orientation, if all paths are reverse. + boolean allReverse = true; + for(WayInPath way: outerWays) { + allReverse &= way.insideToTheLeft; + } + + if (allReverse) { + for(WayInPath way: outerWays){ + way.insideToTheLeft = !way.insideToTheLeft; } } commitCommands(marktr("Join Areas: Remove Short Ways")); - Way joinedWay = joinWays(join); + Way joinedWay = joinOrientedWays(outerWays); if (joinedWay != null) return closeWay(joinedWay); @@ -633,4 +888,36 @@ /** + * Joins a list of ways (using CombineWayAction and ReverseWayAction as specified in WayInPath) + * @param ArrayList The list of ways to join and reverse + * @return Way The newly created way + */ + private Way joinOrientedWays(ArrayList ways) { + if(ways.size() < 2) + return ways.get(0).way; + + // This will turn ways so all of them point in the same direction and CombineAction won't bug + // the user about this. + + List actionWays = new ArrayList(ways.size()); + + for(WayInPath way : ways) { + actionWays.add(way.way); + + if (way.insideToTheLeft) { + Main.main.getCurrentDataSet().setSelected(way.way); + new ReverseWayAction().actionPerformed(null); + cmdsCount++; + } + } + + Way result = new CombineWayAction().combineWays(actionWays); + + if(result != null) { + cmdsCount++; + } + 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 @@ -638,10 +925,11 @@ */ private Way joinWays(ArrayList ways) { - if(ways.size() < 2) return ways.get(0); + 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) { + for (Way b : ways) { if(a == null) { a = b; @@ -656,5 +944,5 @@ a = b; } - if((a = new CombineWayAction().combineWays(ways)) != null) { + if ((a = new CombineWayAction().combineWays(ways)) != null) { cmdsCount++; }