Index: trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java =================================================================== --- trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 3635) +++ trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 3636) @@ -2,7 +2,4 @@ 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; @@ -12,9 +9,7 @@ import java.awt.event.KeyEvent; import java.awt.geom.Area; -import java.awt.geom.Line2D; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; -import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; @@ -39,7 +34,7 @@ import org.openstreetmap.josm.data.UndoRedoHandler; import org.openstreetmap.josm.data.coor.EastNorth; -import org.openstreetmap.josm.data.coor.LatLon; import org.openstreetmap.josm.data.osm.DataSet; import org.openstreetmap.josm.data.osm.Node; +import org.openstreetmap.josm.data.osm.NodePositionComparator; import org.openstreetmap.josm.data.osm.OsmPrimitive; import org.openstreetmap.josm.data.osm.Relation; @@ -48,7 +43,12 @@ import org.openstreetmap.josm.data.osm.Way; import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog; +import org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil; +import org.openstreetmap.josm.tools.Geometry; import org.openstreetmap.josm.tools.Pair; import org.openstreetmap.josm.tools.Shortcut; +/** + * Join Areas (i.e. closed ways and multipolygons) + */ public class JoinAreasAction extends JosmAction { // This will be used to commit commands and unite them into one large command sequence at the end @@ -110,5 +110,5 @@ //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 static class WayInPolygon { public final Way way; public boolean insideToTheRight; @@ -137,5 +137,5 @@ * */ - private static class AssembledPolygon { + public static class AssembledPolygon { public List ways; @@ -164,5 +164,4 @@ } - public static class AssembledMultipolygon { public AssembledPolygon outerWay; @@ -209,5 +208,5 @@ public WayInPolygon startNewWay() { - if (availableWays.size() == 0) { + if (availableWays.isEmpty()) { lastWay = null; } else { @@ -247,5 +246,5 @@ //this is the path we came from - ignore it. } - else if (bestWay == null || (isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) { + else if (bestWay == null || (Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) { //the new way is better bestWay = way; @@ -262,5 +261,5 @@ //this is the path we came from - ignore it. } - else if (bestWay == null || (isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) { + else if (bestWay == null || (Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) { //the new way is better bestWay = way; @@ -291,29 +290,4 @@ /** - * 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 @@ -328,5 +302,4 @@ } } - // Adds the menu entry, Shortcuts, etc. @@ -415,5 +388,4 @@ } - /** * Tests if the areas have some intersections to join. @@ -430,5 +402,5 @@ //find intersection points - ArrayList nodes = addIntersections(allStartingWays, true); + ArrayList nodes = Geometry.addIntersections(allStartingWays, true, cmds); return nodes.size() > 0; } @@ -466,8 +438,9 @@ //find intersection points - ArrayList nodes = addIntersections(allStartingWays, false); + ArrayList nodes = Geometry.addIntersections(allStartingWays, false, cmds); //no intersections, return. - if (nodes.size() == 0) return result; + if (nodes.isEmpty()) + return result; commitCommands(marktr("Added node on all intersections")); @@ -529,5 +502,4 @@ } - makeCommitsOneAction(marktr("Joined overlapping areas")); @@ -563,8 +535,8 @@ TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways); TagCollection completeWayTags = new TagCollection(wayTags); - combineTigerTags(completeWayTags); - normalizeTagCollectionBeforeEditing(completeWayTags, ways); + TagConflictResolutionUtil.combineTigerTags(completeWayTags); + TagConflictResolutionUtil.normalizeTagCollectionBeforeEditing(completeWayTags, ways); TagCollection tagsToEdit = new TagCollection(completeWayTags); - completeTagCollectionForEditing(tagsToEdit); + TagConflictResolutionUtil.completeTagCollectionForEditing(tagsToEdit); CombinePrimitiveResolverDialog dialog = CombinePrimitiveResolverDialog.getInstance(); @@ -596,5 +568,4 @@ } - /** * This method removes duplicate points (if any) from the input way. @@ -659,207 +630,4 @@ 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); - } - - /** - * 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 - )); - } - - /** @@ -884,5 +652,4 @@ } - /** * This method analyzes the way and assigns each part what direction polygon "inside" is. @@ -950,5 +717,5 @@ Node nextNode = way.getNode(1); - if (topWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { + if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { //the new way is better topWay = way; @@ -962,5 +729,5 @@ Node nextNode = way.getNode(way.getNodesCount() - 2); - if (topWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { + if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { //the new way is better topWay = way; @@ -976,5 +743,5 @@ //there will be no parallel segments in the middle of way, so all fine. - wayClockwise = angleIsClockwise(prev, topNode, next); + wayClockwise = Geometry.angleIsClockwise(prev, topNode, next); } @@ -999,5 +766,4 @@ break; } - //find intersecting segments @@ -1037,6 +803,6 @@ Node wayBNode = wayB.getNode(1); - boolean wayAToTheRight = isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode); - boolean wayBToTheRight = isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode); + boolean wayAToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode); + boolean wayBToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode); if (wayAToTheRight != wayBToTheRight) { @@ -1084,7 +850,7 @@ } - - /** - * Simple chunking version. Does not care about circular ways and result being proper, we will glue it all back together later on. + /** + * 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. @@ -1185,6 +951,4 @@ return result; } - - /** @@ -1285,5 +1049,4 @@ } - /** * This method checks if polygons have several touching parts and splits them in several polygons. @@ -1323,42 +1086,4 @@ return newPolygons; } - - - /** - * 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 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; - } - /** @@ -1375,5 +1100,5 @@ if (!outsideNodes.contains(insideNode)) //simply test the one node - return nodeInsidePolygon(insideNode, outside.getNodes()); + return Geometry.nodeInsidePolygon(insideNode, outside.getNodes()); } @@ -1381,51 +1106,4 @@ return false; } - - /** - * 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(Node point, List polygonNodes) { - 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; - } - - //order points so p1.lat <= p2.lat; - if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) { - p1 = oldPoint; - p2 = newPoint; - } else { - p1 = newPoint; - p2 = oldPoint; - } - - //test if the line is crossed and if so invert the inside flag. - 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; - } - - oldPoint = newPoint; - } - - return inside; - } - /** @@ -1443,5 +1121,4 @@ return result; } - /** @@ -1473,5 +1150,4 @@ } - /** * Joins a list of ways (using CombineWayAction and ReverseWayAction as specified in WayInPath) @@ -1506,5 +1182,4 @@ return result.a; } - /** @@ -1604,5 +1279,4 @@ } - /** * This method filters the list of relations that form the multipolygons. @@ -1627,5 +1301,4 @@ return result; } - /** @@ -1650,5 +1323,4 @@ } - /** * Removes a given OsmPrimitive from all relations @@ -1685,5 +1357,4 @@ return result; } - /** Index: trunk/src/org/openstreetmap/josm/data/osm/NodePositionComparator.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/osm/NodePositionComparator.java (revision 3636) +++ trunk/src/org/openstreetmap/josm/data/osm/NodePositionComparator.java (revision 3636) @@ -0,0 +1,24 @@ +// License: GPL. For details, see LICENSE file. +package org.openstreetmap.josm.data.osm; + +import java.util.Comparator; + +/** + * Provides some node order , based on coordinates, nodes with equal coordinates are equal. + * + * @author viesturs + */ +public class NodePositionComparator implements Comparator { + @Override + public int compare(Node n1, Node n2) { + double dLat = n1.getCoor().lat() - n2.getCoor().lat(); + if (dLat > 0) + return 1; + if (dLat < 0) + return -1; + double dLon = n1.getCoor().lon() - n2.getCoor().lon(); + if (dLon == 0) + return 0; + return dLon > 0 ? 1 : -1; + } +} Index: trunk/src/org/openstreetmap/josm/tools/Geometry.java =================================================================== --- trunk/src/org/openstreetmap/josm/tools/Geometry.java (revision 3636) +++ trunk/src/org/openstreetmap/josm/tools/Geometry.java (revision 3636) @@ -0,0 +1,304 @@ +// License: GPL. For details, see LICENSE file. +package org.openstreetmap.josm.tools; + +import java.awt.geom.Line2D; +import java.util.ArrayList; +import java.util.Comparator; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Set; +import org.openstreetmap.josm.Main; +import org.openstreetmap.josm.command.AddCommand; +import org.openstreetmap.josm.command.ChangeCommand; +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.Node; +import org.openstreetmap.josm.data.osm.NodePositionComparator; +import org.openstreetmap.josm.data.osm.Way; + +/** + * Some tools for geometry related tasks. + * + * @author viesturs + */ +public class Geometry { + /** + * 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. + */ + public static ArrayList addIntersections(List ways, boolean test, List cmds) { + //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); + } + + /** + * 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 + )); + } + + /** + * 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 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 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. + */ + public static boolean nodeInsidePolygon(Node point, List polygonNodes) { + 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; + } + + //order points so p1.lat <= p2.lat; + if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) { + p1 = oldPoint; + p2 = newPoint; + } else { + p1 = newPoint; + p2 = oldPoint; + } + + //test if the line is crossed and if so invert the inside flag. + 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; + } + + oldPoint = newPoint; + } + + return inside; + } +}