Index: trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java =================================================================== --- trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 3647) +++ trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 3650) @@ -48,4 +48,5 @@ import org.openstreetmap.josm.tools.Shortcut; + /** * Join Areas (i.e. closed ways and multipolygons) @@ -402,5 +403,5 @@ //find intersection points - ArrayList nodes = Geometry.addIntersections(allStartingWays, true, cmds); + Set nodes = Geometry.addIntersections(allStartingWays, true, cmds); return nodes.size() > 0; } @@ -438,5 +439,5 @@ //find intersection points - ArrayList nodes = Geometry.addIntersections(allStartingWays, false, cmds); + Set nodes = Geometry.addIntersections(allStartingWays, false, cmds); //no intersections, return. @@ -474,6 +475,9 @@ List preparedPolygons = findPolygons(bounadries); + //assemble final polygons List polygons = new ArrayList(); + Set relationsToDelete = new LinkedHashSet(); + for (AssembledMultipolygon pol : preparedPolygons) { @@ -485,5 +489,5 @@ //add back the original relations, merged with our new multipolygon relation - fixRelations(relations, resultPol.outerWay, ownMultipolygonRelation); + fixRelations(relations, resultPol.outerWay, ownMultipolygonRelation, relationsToDelete); //strip tags from inner ways @@ -495,4 +499,10 @@ commitCommands(marktr("Assemble new polygons")); + + for(Relation rel: relationsToDelete) { + cmds.add(new DeleteCommand(rel)); + } + + commitCommands(marktr("Delete relations")); // Delete the discarded inner ways @@ -828,5 +838,5 @@ * @return list of split ways (or original ways if no splitting is done). */ - private ArrayList splitWayOnNodes(Way way, Collection nodes) { + private ArrayList splitWayOnNodes(Way way, Set nodes) { ArrayList result = new ArrayList(); @@ -1095,6 +1105,7 @@ public static boolean wayInsideWay(AssembledPolygon inside, AssembledPolygon outside) { Set outsideNodes = new HashSet(outside.getNodes()); - - for (Node insideNode : inside.getNodes()) { + List insideNodes = inside.getNodes(); + + for (Node insideNode : insideNodes) { if (!outsideNodes.contains(insideNode)) @@ -1364,6 +1375,7 @@ * @param ArrayList List of relations with roles the (original) ways were part of * @param Way The newly created outer area/way - */ - private void fixRelations(ArrayList rels, Way outer, RelationRole ownMultipol) { + * @param relationsToDelete - set of relations to delete. + */ + private void fixRelations(ArrayList rels, Way outer, RelationRole ownMultipol, Set relationsToDelete) { ArrayList multiouters = new ArrayList(); @@ -1410,5 +1422,5 @@ } // Delete old relation - cmds.add(new DeleteCommand(r.rel)); + relationsToDelete.add(r.rel); } newRel.addMember(new RelationMember("outer", outer)); Index: trunk/src/org/openstreetmap/josm/actions/mapmode/ExtrudeAction.java =================================================================== --- trunk/src/org/openstreetmap/josm/actions/mapmode/ExtrudeAction.java (revision 3647) +++ trunk/src/org/openstreetmap/josm/actions/mapmode/ExtrudeAction.java (revision 3650) @@ -41,4 +41,5 @@ import org.openstreetmap.josm.gui.layer.MapViewPaintable; import org.openstreetmap.josm.gui.layer.OsmDataLayer; +import org.openstreetmap.josm.tools.Geometry; import org.openstreetmap.josm.tools.ImageProvider; import org.openstreetmap.josm.tools.Shortcut; @@ -306,5 +307,5 @@ //find if the new points overlap existing segments (in case of 90 degree angles) Node prevNode = getPreviousNode(selectedSegment.lowerIndex); - boolean nodeOverlapsSegment = prevNode != null && segmentsParralel(initialN1en, prevNode.getEastNorth(), initialN1en, newN1en); + boolean nodeOverlapsSegment = prevNode != null && Geometry.segmentsParralel(initialN1en, prevNode.getEastNorth(), initialN1en, newN1en); boolean hasOtherWays = this.hasNodeOtherWays(selectedSegment.getFirstNode(), selectedSegment.way); @@ -323,5 +324,5 @@ //find if the new points overlap existing segments (in case of 90 degree angles) Node nextNode = getNextNode(selectedSegment.lowerIndex + 1); - nodeOverlapsSegment = nextNode != null && segmentsParralel(initialN2en, nextNode.getEastNorth(), initialN2en, newN2en); + nodeOverlapsSegment = nextNode != null && Geometry.segmentsParralel(initialN2en, nextNode.getEastNorth(), initialN2en, newN2en); hasOtherWays = hasNodeOtherWays(selectedSegment.getSecondNode(), selectedSegment.way); @@ -387,5 +388,5 @@ private static EastNorth calculateSegmentOffset(EastNorth segmentP1, EastNorth segmentP2, EastNorth moveDirection, EastNorth targetPos) { - EastNorth intersectionPoint = getLineLineIntersection(segmentP1, segmentP2, targetPos, + EastNorth intersectionPoint = Geometry.getLineLineIntersection(segmentP1, segmentP2, targetPos, new EastNorth(targetPos.getX() + moveDirection.getX(), targetPos.getY() + moveDirection.getY())); @@ -395,42 +396,7 @@ //return distance form base to target position return new EastNorth(targetPos.getX() - intersectionPoint.getX(), - targetPos.getY() - intersectionPoint.getY()); - } - - /** - * Finds the intersection of two lines of infinite length. - * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise - */ - public static EastNorth getLineLineIntersection(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) { - // Convert line from (point, point) form to ax+by=c - double a1 = p2.getY() - p1.getY(); - double b1 = p1.getX() - p2.getX(); - double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY(); - - double a2 = p4.getY() - p3.getY(); - double b2 = p3.getX() - p4.getX(); - double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY(); - - // Solve the equations - double det = a1 * b2 - a2 * b1; - if (det == 0) - return null; // Lines are parallel - - return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det); - } - - private static boolean segmentsParralel(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) { - - // Convert line from (point, point) form to ax+by=c - double a1 = p2.getY() - p1.getY(); - double b1 = p1.getX() - p2.getX(); - - double a2 = p4.getY() - p3.getY(); - double b2 = p3.getX() - p4.getX(); - - // Solve the equations - double det = a1 * b2 - a2 * b1; - return Math.abs(det) < 1e-13; - } + targetPos.getY() - intersectionPoint.getY()); + } + /** Index: trunk/src/org/openstreetmap/josm/data/osm/NodePositionComparator.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/osm/NodePositionComparator.java (revision 3647) +++ trunk/src/org/openstreetmap/josm/data/osm/NodePositionComparator.java (revision 3650) @@ -12,4 +12,8 @@ @Override public int compare(Node n1, Node n2) { + + if (n1.getCoor().equalsEpsilon(n2.getCoor())) + return 0; + double dLat = n1.getCoor().lat() - n2.getCoor().lat(); if (dLat > 0) Index: trunk/src/org/openstreetmap/josm/tools/Geometry.java =================================================================== --- trunk/src/org/openstreetmap/josm/tools/Geometry.java (revision 3647) +++ trunk/src/org/openstreetmap/josm/tools/Geometry.java (revision 3650) @@ -5,7 +5,9 @@ import java.util.ArrayList; import java.util.Comparator; +import java.util.HashSet; import java.util.LinkedHashSet; import java.util.List; import java.util.Set; + import org.openstreetmap.josm.Main; import org.openstreetmap.josm.command.AddCommand; @@ -13,5 +15,5 @@ import org.openstreetmap.josm.command.Command; import org.openstreetmap.josm.data.coor.EastNorth; -import org.openstreetmap.josm.data.coor.LatLon; +import org.openstreetmap.josm.data.osm.BBox; import org.openstreetmap.josm.data.osm.Node; import org.openstreetmap.josm.data.osm.NodePositionComparator; @@ -24,4 +26,6 @@ */ public class Geometry { + public enum PolygonIntersection {FIRST_INSIDE_SECOND, SECOND_INSIDE_FIRST, OUTSIDE, CROSSING} + /** * Will find all intersection and add nodes there for list of given ways. Handles self-intersections too. @@ -31,151 +35,138 @@ * Prerequisite: no two nodes have the same coordinates. */ - public static ArrayList addIntersections(List ways, boolean test, List cmds) { - //TODO: this is a bit slow - O( (number of nodes)^2 + numberOfIntersections * numberOfNodes ) + public static Set addIntersections(List ways, boolean test, List cmds) { //stupid java, cannot instantiate array of generic classes.. @SuppressWarnings("unchecked") ArrayList[] newNodes = new ArrayList[ways.size()]; + BBox[] wayBounds = new BBox[ways.size()]; boolean[] changedWays = new boolean[ways.size()]; Set intersectionNodes = new LinkedHashSet(); + //copy node arrays for local usage. for (int pos = 0; pos < ways.size(); pos ++) { newNodes[pos] = new ArrayList(ways.get(pos).getNodes()); + wayBounds[pos] = getNodesBounds(newNodes[pos]); changedWays[pos] = false; } - //iterate over all segment pairs and introduce the intersections - + //iterate over all way 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; + WayLoop: for (int seg1Way = 0; seg1Way < ways.size(); seg1Way ++) { + for (int seg2Way = seg1Way; seg2Way < ways.size(); seg2Way ++) { + + //do not waste time on bounds that do not intersect + if (!wayBounds[seg1Way].intersects(wayBounds[seg2Way])) { + continue; } - } - - - //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; + + ArrayList way1Nodes = newNodes[seg1Way]; + ArrayList way2Nodes = newNodes[seg2Way]; + + //iterate over primary segmemt + for (int seg1Pos = 0; seg1Pos + 1 < way1Nodes.size(); seg1Pos ++) { + + //iterate over secondary segment + int seg2Start = seg1Way != seg2Way ? 0: seg1Pos + 2;//skip the adjacent segment + + for (int seg2Pos = seg2Start; seg2Pos + 1< way2Nodes.size(); seg2Pos ++) { + + //need to get them again every time, because other segments may be changed + Node seg1Node1 = way1Nodes.get(seg1Pos); + Node seg1Node2 = way1Nodes.get(seg1Pos + 1); + Node seg2Node1 = way2Nodes.get(seg2Pos); + Node seg2Node2 = way2Nodes.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 == way2Nodes.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) { + EastNorth intersection = getSegmentSegmentIntersection( + seg1Node1.getEastNorth(), seg1Node2.getEastNorth(), + seg2Node1.getEastNorth(), seg2Node2.getEastNorth()); + + if (intersection != null) { + if (test) { + intersectionNodes.add(seg2Node1); + return intersectionNodes; + } + + Node newNode = new Node(Main.proj.eastNorth2latlon(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) { + way1Nodes.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) { + way2Nodes.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 intersectionNodes; } } - - //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 ++) { @@ -191,36 +182,16 @@ } - return new ArrayList(intersectionNodes); - } - - /** - * Finds the intersection of two lines - * @return LatLon null if no intersection was found, the LatLon coordinates of the intersection otherwise - */ - static private LatLon getLineLineIntersection( - double x1, double y1, double x2, double y2, - double x3, double y3, double x4, double y4) { - - if (!Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4)) return null; - - // Convert line from (point, point) form to ax+by=c - double a1 = y2 - y1; - double b1 = x1 - x2; - double c1 = x2*y1 - x1*y2; - - double a2 = y4 - y3; - double b2 = x3 - x4; - double c2 = x4*y3 - x3*y4; - - // Solve the equations - double det = a1*b2 - a2*b1; - if (det == 0) return null; // Lines are parallel - - return Main.proj.eastNorth2latlon(new EastNorth( - (b1*c2 - b2*c1)/det, - (a2*c1 -a1*c2)/det - )); - } - + return intersectionNodes; + } + + private static BBox getNodesBounds(ArrayList nodes) { + + BBox bounds = new BBox(nodes.get(0)); + for(Node n: nodes) { + bounds.add(n.getCoor()); + } + return bounds; + } + /** * Tests if given point is to the right side of path consisting of 3 points. @@ -259,4 +230,187 @@ /** + * Finds the intersection of two line segments + * @return EastNorth null if no intersection was found, the EastNorth coordinates of the intersection otherwise + */ + public static EastNorth getSegmentSegmentIntersection( + EastNorth p1, EastNorth p2, + EastNorth p3, EastNorth p4) { + double x1 = p1.getX(); + double y1 = p1.getY(); + double x2 = p2.getX(); + double y2 = p2.getY(); + double x3 = p3.getX(); + double y3 = p3.getY(); + double x4 = p4.getX(); + double y4 = p4.getY(); + + //TODO: do this locally. + if (!Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4)) return null; + + // Convert line from (point, point) form to ax+by=c + double a1 = y2 - y1; + double b1 = x1 - x2; + double c1 = x2*y1 - x1*y2; + + double a2 = y4 - y3; + double b2 = x3 - x4; + double c2 = x4*y3 - x3*y4; + + // Solve the equations + double det = a1*b2 - a2*b1; + if (det == 0) return null; // Lines are parallel + + double x = (b1*c2 - b2*c1)/det; + double y = (a2*c1 -a1*c2)/det; + + return new EastNorth(x, y); + } + + /** + * Finds the intersection of two lines of infinite length. + * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise + */ + public static EastNorth getLineLineIntersection(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) { + + // Convert line from (point, point) form to ax+by=c + double a1 = p2.getY() - p1.getY(); + double b1 = p1.getX() - p2.getX(); + double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY(); + + double a2 = p4.getY() - p3.getY(); + double b2 = p3.getX() - p4.getX(); + double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY(); + + // Solve the equations + double det = a1 * b2 - a2 * b1; + if (det == 0) + return null; // Lines are parallel + + return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det); + } + + public static boolean segmentsParralel(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) { + // Convert line from (point, point) form to ax+by=c + double a1 = p2.getY() - p1.getY(); + double b1 = p1.getX() - p2.getX(); + + double a2 = p4.getY() - p3.getY(); + double b2 = p3.getX() - p4.getX(); + + // Solve the equations + double det = a1 * b2 - a2 * b1; + return Math.abs(det) < 1e-13; + } + + /** + * Calculates closest point to a line segment. + * @param segmentP1 + * @param segmentP2 + * @param point + * @return segmentP1 if it is the closest point, segmentP2 if it is the closest point, + * a new point if closest point is between segmentP1 and segmentP2. + */ + public static EastNorth closestPointToSegment(EastNorth segmentP1, EastNorth segmentP2, EastNorth point) { + + double ldx = segmentP2.getX() - segmentP1.getX(); + double ldy = segmentP2.getY() - segmentP1.getY(); + + if (ldx == 0 && ldy == 0) //segment zero length + return segmentP1; + + double pdx = point.getX() - segmentP1.getX(); + double pdy = point.getY() - segmentP1.getY(); + + double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy); + + if (offset <= 0) + return segmentP1; + else if (offset >= 1) + return segmentP2; + else + return new EastNorth(segmentP1.getX() + ldx * offset, segmentP1.getY() + ldy * offset); + } + + /** + * 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(EastNorth commonNode, EastNorth firstNode, EastNorth secondNode) { + double dy1 = (firstNode.getY() - commonNode.getY()); + double dy2 = (secondNode.getY() - commonNode.getY()); + double dx1 = (firstNode.getX() - commonNode.getX()); + double dx2 = (secondNode.getX() - commonNode.getX()); + + return dy1 * dx2 - dx1 * dy2 > 0; + } + + /** + * Tests if two polygons intersect. + * @param first + * @param second + * @return intersection kind + * TODO: test segments, not only points + * TODO: is O(N*M), should use sweep for better performance. + */ + public static PolygonIntersection polygonIntersection(List first, List second) { + Set firstSet = new HashSet(first); + Set secondSet = new HashSet(second); + + int nodesInsideSecond = 0; + int nodesOutsideSecond = 0; + int nodesInsideFirst = 0; + int nodesOutsideFirst = 0; + + for (Node insideNode : first) { + if (secondSet.contains(insideNode)) { + continue; + //ignore touching nodes. + } + + if (nodeInsidePolygon(insideNode, second)) { + nodesInsideSecond ++; + } + else { + nodesOutsideSecond ++; + } + } + + for (Node insideNode : second) { + if (firstSet.contains(insideNode)) { + continue; + //ignore touching nodes. + } + + if (nodeInsidePolygon(insideNode, first)) { + nodesInsideFirst ++; + } + else { + nodesOutsideFirst ++; + } + } + + if (nodesInsideFirst == 0) { + if (nodesInsideSecond == 0){ + if (nodesOutsideFirst + nodesInsideSecond > 0) + return PolygonIntersection.OUTSIDE; + else + //all nodes common + return PolygonIntersection.CROSSING; + } else + return PolygonIntersection.FIRST_INSIDE_SECOND; + } + else + { + if (nodesInsideSecond == 0) + return PolygonIntersection.SECOND_INSIDE_FIRST; + else + return PolygonIntersection.CROSSING; + } + } + + /** * 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. @@ -265,5 +419,5 @@ */ public static boolean nodeInsidePolygon(Node point, List polygonNodes) { - if (polygonNodes.size() < 3) + if (polygonNodes.size() < 2) return false;