Index: /applications/editors/josm/plugins/multipoly/src/multipoly/GeometryFunctions.java =================================================================== --- /applications/editors/josm/plugins/multipoly/src/multipoly/GeometryFunctions.java (revision 23818) +++ /applications/editors/josm/plugins/multipoly/src/multipoly/GeometryFunctions.java (revision 23819) @@ -15,176 +15,207 @@ */ public class GeometryFunctions { - public enum Intersection {INSIDE, OUTSIDE, CROSSING, EQUAL} - - /** - * Finds the intersection of two lines of inifinite 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; - } - - /** - * Calcualtes 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 instersect. - * @param first - * @param second - * @return Inside if second is inside first, Outside, if second is outside first, Crossing, if they cross. - */ - public static Intersection polygonIntersection(List outside, List inside) { - Set outsideNodes = new HashSet(outside); - - boolean nodesInside = false; - boolean nodesOutside = false; - - for (Node insideNode : inside) { - if (!outsideNodes.contains(insideNode)) { - if (nodeInsidePolygon(insideNode, outside)) { - nodesInside = true; - } - else { - nodesOutside = true; - } - } - } - - if (nodesInside) { - if (nodesOutside){ - return Intersection.CROSSING; - } - else { - return Intersection.INSIDE; - } - } - else { - if (nodesOutside){ - return Intersection.OUTSIDE; - } - else { - return Intersection.EQUAL; - } - } - } - - /** - * 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() < 2) - 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; - } + public enum PolygonIntersection {FIRST_INSIDE_SECOND, SECOND_INSIDE_FIRST, OUTSIDE, CROSSING} + + /** + * 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. + * @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() < 2) + 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; + } Index: /applications/editors/josm/plugins/multipoly/src/multipoly/Multipolygon.java =================================================================== --- /applications/editors/josm/plugins/multipoly/src/multipoly/Multipolygon.java (revision 23818) +++ /applications/editors/josm/plugins/multipoly/src/multipoly/Multipolygon.java (revision 23819) @@ -10,5 +10,5 @@ import java.util.Set; -import multipoly.GeometryFunctions.Intersection; +import multipoly.GeometryFunctions.PolygonIntersection; import org.openstreetmap.josm.data.osm.Node; @@ -16,93 +16,93 @@ import org.openstreetmap.josm.tools.MultiMap; -public class Multipolygon { - - /** - * Represents one polygon that consists of multiple ways. +public class Multipolygon { + + /** + * Represents one polygon that consists of multiple ways. * @author Viesturs * */ public static class JoinedPolygon { - public final List ways; - public final List reversed; - public final List nodes; - - public JoinedPolygon(List ways, List reversed) { - this.ways = ways; - this.reversed = reversed; - this.nodes = this.getNodes(); - } - - /** - * Creates a polygon form single way. - * @param way - */ - public JoinedPolygon(Way way) { - this.ways = Collections.singletonList(way); - this.reversed = Collections.singletonList(Boolean.FALSE); - this.nodes = this.getNodes(); - } - - - /** - * Builds a list of nodes for this polygon. First node is not duplicated as last node. - * @return - */ - private List getNodes() { - List nodes = new ArrayList(); - - for(int waypos = 0; waypos < this.ways.size(); waypos ++) { - Way way = this.ways.get(waypos); - boolean reversed = this.reversed.get(waypos).booleanValue(); - - if (!reversed){ - for (int pos = 0; pos < way.getNodesCount() - 1; pos++) { - nodes.add(way.getNode(pos)); - } - } - else { - for (int pos = way.getNodesCount() - 1; pos > 0; pos--) { - nodes.add(way.getNode(pos)); - } - } - } - - return nodes; - } - } - - - /** - * Helper storage class for finding findOuterWays - * @author viesturs - */ - static class PolygonLevel { - public final int level; //nesting level , even for outer, odd for inner polygons. - public final JoinedPolygon outerWay; - - public List innerWays; - - public PolygonLevel(JoinedPolygon _pol, int _level) { - this.outerWay = _pol; - this.level = _level; - this.innerWays = new ArrayList(); - } - } - - + public final List ways; + public final List reversed; + public final List nodes; + + public JoinedPolygon(List ways, List reversed) { + this.ways = ways; + this.reversed = reversed; + this.nodes = this.getNodes(); + } + + /** + * Creates a polygon form single way. + * @param way + */ + public JoinedPolygon(Way way) { + this.ways = Collections.singletonList(way); + this.reversed = Collections.singletonList(Boolean.FALSE); + this.nodes = this.getNodes(); + } + + + /** + * Builds a list of nodes for this polygon. First node is not duplicated as last node. + * @return + */ + private List getNodes() { + List nodes = new ArrayList(); + + for(int waypos = 0; waypos < this.ways.size(); waypos ++) { + Way way = this.ways.get(waypos); + boolean reversed = this.reversed.get(waypos).booleanValue(); + + if (!reversed){ + for (int pos = 0; pos < way.getNodesCount() - 1; pos++) { + nodes.add(way.getNode(pos)); + } + } + else { + for (int pos = way.getNodesCount() - 1; pos > 0; pos--) { + nodes.add(way.getNode(pos)); + } + } + } + + return nodes; + } + } + + + /** + * Helper storage class for finding findOuterWays + * @author viesturs + */ + static class PolygonLevel { + public final int level; //nesting level , even for outer, odd for inner polygons. + public final JoinedPolygon outerWay; + + public List innerWays; + + public PolygonLevel(JoinedPolygon _pol, int _level) { + this.outerWay = _pol; + this.level = _level; + this.innerWays = new ArrayList(); + } + } + + public List outerWays; public List innerWays; - - + + public Multipolygon(List outerWays, List innerWays){ this.outerWays = outerWays; this.innerWays = innerWays; } - + public Multipolygon(){ this.outerWays = new ArrayList(0); this.innerWays = new ArrayList(0); } - + /** * Splits ways into inner and outer JoinedWays. Sets innerWays and outerWays to the result. @@ -111,15 +111,15 @@ */ public String makeFromWays(Collection ways){ - List joinedWays = new ArrayList(); - + List joinedWays = new ArrayList(); + //collect ways connecting to each node. MultiMap nodesWithConnectedWays = new MultiMap(); Set usedWays = new HashSet(); - + for(Way w: ways) { if (w.getNodesCount() < 2) { return tr("Cannot add a way with only {0} nodes.", w.getNodesCount()); } - + if (w.isClosed()) { //closed way, add as is. @@ -133,5 +133,5 @@ } } - + //process unclosed ways for(Way startWay: ways) { @@ -139,5 +139,5 @@ continue; } - + Node startNode = startWay.firstNode(); List collectedWays = new ArrayList(); @@ -145,42 +145,42 @@ Way curWay = startWay; Node prevNode = startNode; - + //find polygon ways while (true) { - boolean curWayReverse = prevNode == curWay.lastNode(); - Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode(); + boolean curWayReverse = prevNode == curWay.lastNode(); + Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode(); //add cur way to the list collectedWays.add(curWay); collectedWaysReverse.add(Boolean.valueOf(curWayReverse)); - + if (nextNode == startNode) { //way finished break; } - + //find next way Collection adjacentWays = nodesWithConnectedWays.get(nextNode); - + if (adjacentWays.size() != 2) { return tr("Each node must connect exactly 2 ways"); } - + Way nextWay = null; for(Way way: adjacentWays){ if (way != curWay){ - nextWay = way; - } - } - + nextWay = way; + } + } + //move to the next way - curWay = nextWay; + curWay = nextWay; prevNode = nextNode; } - - usedWays.addAll(collectedWays); - joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse)); - } - + + usedWays.addAll(collectedWays); + joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse)); + } + //analyze witch way is inside witch outside. return makeFromPolygons(joinedWays); @@ -193,92 +193,91 @@ */ private String makeFromPolygons(List polygons) { - List list = findOuterWaysRecursive(0, polygons); - - if (list == null){ - return tr("There is an intersection between ways."); - } + List list = findOuterWaysRecursive(0, polygons); + + if (list == null){ + return tr("There is an intersection between ways."); + } this.outerWays = new ArrayList(0); this.innerWays = new ArrayList(0); - - //take every other level - for (PolygonLevel pol : list) { - if (pol.level % 2 == 0) { - this.outerWays.add(pol.outerWay); - } - else { - this.innerWays.add(pol.outerWay); - } - } - - return null; - } - - /** - * Collects outer way and corresponding inner ways from all boundaries. - * @param boundaryWays - * @return the outermostWay, or null if intersection found. - */ - private List findOuterWaysRecursive(int level, Collection boundaryWays) { - - //TODO: bad performance for deep nesting... - List result = new ArrayList(); - - for (JoinedPolygon outerWay : boundaryWays) { - - boolean outerGood = true; - List innerCandidates = new ArrayList(); - - for (JoinedPolygon innerWay : boundaryWays) { - if (innerWay == outerWay) { - continue; - } - - Intersection innerInside = GeometryFunctions.polygonIntersection(outerWay.nodes, innerWay.nodes); - Intersection outerInside = GeometryFunctions.polygonIntersection(innerWay.nodes, outerWay.nodes); - - if (outerInside == Intersection.INSIDE) { - outerGood = false; // outer is inside another polygon - break; - } else if (innerInside == Intersection.INSIDE) { - innerCandidates.add(innerWay); - } - else if (innerInside == Intersection.CROSSING) - { - //ways intersect - return null; - } - } - - if (!outerGood) { - continue; - } - - //add new outer polygon - PolygonLevel pol = new PolygonLevel(outerWay, level); - - //process inner ways - if (innerCandidates.size() > 0) { - List innerList = this.findOuterWaysRecursive(level + 1, innerCandidates); - if (innerList == null) { - return null; //intersection found - } - - result.addAll(innerList); - - for (PolygonLevel pl : innerList) { - if (pl.level == level + 1) { - pol.innerWays.add(pl.outerWay); - } - } - } - - result.add(pol); - } - - return result; - } - - - + + //take every other level + for (PolygonLevel pol : list) { + if (pol.level % 2 == 0) { + this.outerWays.add(pol.outerWay); + } + else { + this.innerWays.add(pol.outerWay); + } + } + + return null; + } + + /** + * Collects outer way and corresponding inner ways from all boundaries. + * @param boundaryWays + * @return the outermostWay, or null if intersection found. + */ + private List findOuterWaysRecursive(int level, Collection boundaryWays) { + + //TODO: bad performance for deep nesting... + List result = new ArrayList(); + + for (JoinedPolygon outerWay : boundaryWays) { + + boolean outerGood = true; + List innerCandidates = new ArrayList(); + + for (JoinedPolygon innerWay : boundaryWays) { + if (innerWay == outerWay) { + continue; + } + + PolygonIntersection intersection = GeometryFunctions.polygonIntersection(outerWay.nodes, innerWay.nodes); + + if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) { + outerGood = false; // outer is inside another polygon + break; + } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) { + innerCandidates.add(innerWay); + } + else if (intersection == PolygonIntersection.CROSSING) + { + //ways intersect + return null; + } + } + + if (!outerGood) { + continue; + } + + //add new outer polygon + PolygonLevel pol = new PolygonLevel(outerWay, level); + + //process inner ways + if (innerCandidates.size() > 0) { + List innerList = this.findOuterWaysRecursive(level + 1, innerCandidates); + if (innerList == null) { + return null; //intersection found + } + + result.addAll(innerList); + + for (PolygonLevel pl : innerList) { + if (pl.level == level + 1) { + pol.innerWays.add(pl.outerWay); + } + } + } + + result.add(pol); + } + + return result; + } + + + }