Index: /applications/editors/josm/plugins/multipoly/src/multipoly/GeometryFunctions.java =================================================================== --- /applications/editors/josm/plugins/multipoly/src/multipoly/GeometryFunctions.java (revision 23771) +++ /applications/editors/josm/plugins/multipoly/src/multipoly/GeometryFunctions.java (revision 23771) @@ -0,0 +1,191 @@ +// License: GPL. Copyright 2019 by Viesturs Zarins +package multipoly; + +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.openstreetmap.josm.data.coor.EastNorth; +import org.openstreetmap.josm.data.osm.Node; + +/** + * This class contains a collection of useful geometry functions. + * @author viesturs + * + */ +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; + } + + +} Index: /applications/editors/josm/plugins/multipoly/src/multipoly/MultipolyAction.java =================================================================== --- /applications/editors/josm/plugins/multipoly/src/multipoly/MultipolyAction.java (revision 23770) +++ /applications/editors/josm/plugins/multipoly/src/multipoly/MultipolyAction.java (revision 23771) @@ -6,11 +6,10 @@ import java.awt.event.ActionEvent; import java.awt.event.KeyEvent; -import java.util.ArrayList; import java.util.Collection; -import java.util.HashSet; -import java.util.LinkedList; -import java.util.List; +import java.util.Collections; import javax.swing.JOptionPane; + +import multipoly.Multipolygon.JoinedPolygon; import org.openstreetmap.josm.Main; @@ -19,11 +18,10 @@ import org.openstreetmap.josm.command.Command; import org.openstreetmap.josm.command.SequenceCommand; -import org.openstreetmap.josm.data.coor.EastNorth; -import org.openstreetmap.josm.data.osm.Node; import org.openstreetmap.josm.data.osm.OsmPrimitive; import org.openstreetmap.josm.data.osm.Relation; import org.openstreetmap.josm.data.osm.RelationMember; import org.openstreetmap.josm.data.osm.Way; -import org.openstreetmap.josm.tools.Pair; +import org.openstreetmap.josm.gui.dialogs.relation.RelationEditor; +import org.openstreetmap.josm.gui.layer.OsmDataLayer; import org.openstreetmap.josm.tools.Shortcut; @@ -60,80 +58,11 @@ */ public void actionPerformed(ActionEvent e) { - - // Get all ways in some type=multipolygon relation - HashSet relationsInMulti = new HashSet(); - for (Relation r : Main.main.getCurrentDataSet().getRelations()) { - if (!r.isUsable()) - continue; - if (r.get("type") != "multipolygon") - continue; - for (RelationMember rm : r.getMembers()) { - OsmPrimitive m = rm.getMember(); - if (m instanceof Way) { - relationsInMulti.add(m); - } - } - } - - // List of selected ways - List selectedWays = new ArrayList(); - // Area of largest way (in square degrees) - double maxarea = 0; - // Which way is the largest one (outer) - Way maxWay = null; - - // For every selected way - for (OsmPrimitive osm : Main.main.getCurrentDataSet().getSelected()) { - if (osm instanceof Way) { - Way way = (Way) osm; - // Check if way is already in another multipolygon - if (relationsInMulti.contains(osm)) { - JOptionPane - .showMessageDialog( - Main.parent, - tr("One of the selected ways is already part of another multipolygon.")); - return; - } - EastNorth first = null, last = null; - // Boundingbox of way - double minx = 9999, miny = 9999, maxx = -9999, maxy = -9999; - for (Pair seg : way.getNodePairs(false)) { - if (first == null) - first = seg.a.getEastNorth(); - last = seg.b.getEastNorth(); - double x = seg.a.getEastNorth().east(); - double y = seg.a.getEastNorth().north(); - if (x < minx) - minx = x; - if (y < miny) - miny = y; - if (x > maxx) - maxx = x; - if (y > maxy) - maxy = y; - } - // Check if first and last node are the same - if (!first.equals(last)) { - JOptionPane - .showMessageDialog( - Main.parent, - tr("Multipolygon must consist only of closed ways.")); - return; - } - // Determine area - double area = (maxx - minx) * (maxy - miny); - selectedWays.add(way); - if (area > maxarea) { - maxarea = area; - maxWay = way; - } - } - } - - if (Main.map == null) { + if (Main.main.getEditLayer() == null) { JOptionPane.showMessageDialog(Main.parent, tr("No data loaded.")); return; } - + + Collection selectedWays = Main.main.getCurrentDataSet().getSelectedWays(); + if (selectedWays.size() < 2) { JOptionPane.showMessageDialog(Main.parent, @@ -141,27 +70,23 @@ return; } + + Multipolygon polygon = this.analyzeWays(selectedWays); + + if (polygon == null) { + return; //could not make multipolygon. + } + + Relation relation = this.createRelation(polygon); - Collection cmds = new LinkedList(); - // Create new relation - Relation rel = new Relation(); - rel.put("type", "multipolygon"); - // Add ways to it - for (int i = 0; i < selectedWays.size(); i++) { - Way s = selectedWays.get(i); - String xrole = "inner"; - if (s == maxWay) - xrole = "outer"; - RelationMember rm = new RelationMember(xrole, s); - rel.addMember(rm); - } - // Add relation - cmds.add(new AddCommand(rel)); - // Commit - Main.main.undoRedo.add(new SequenceCommand(tr("Create multipolygon"), - cmds)); - Main.map.repaint(); - } + //open relation edit window + RelationEditor editor = RelationEditor.getEditor( + Main.main.getEditLayer(), + relation, + null); + + editor.setVisible(true); + } - /** Enable this action only if something is selected */ + /** Enable this action only if something is selected */ @Override protected void updateEnabledState() { @@ -179,3 +104,49 @@ setEnabled(selection != null && !selection.isEmpty()); } + + + /** + * This method analyzes ways and creates multipolygon. + * @param selectedWays + * @return null, if there was a problem with the ways. + */ + private Multipolygon analyzeWays(Collection selectedWays) { + + Multipolygon pol = new Multipolygon(); + String error = pol.makeFromWays(selectedWays); + + if (error != null) { + JOptionPane.showMessageDialog(Main.parent, error); + return null; + } + else { + return pol; + } + } + + + /** + * Builds a relation from polygon ways. + * @param pol + * @return + */ + private Relation createRelation(Multipolygon pol){ + // Create new relation + Relation rel = new Relation(); + rel.put("type", "multipolygon"); + // Add ways to it + for(JoinedPolygon jway: pol.outerWays){ + for(Way way: jway.ways){ + rel.addMember(new RelationMember("outer", way)); + } + } + + for(JoinedPolygon jway: pol.innerWays){ + for(Way way: jway.ways){ + rel.addMember(new RelationMember("inner", way)); + } + } + + return rel; + } } Index: /applications/editors/josm/plugins/multipoly/src/multipoly/Multipolygon.java =================================================================== --- /applications/editors/josm/plugins/multipoly/src/multipoly/Multipolygon.java (revision 23771) +++ /applications/editors/josm/plugins/multipoly/src/multipoly/Multipolygon.java (revision 23771) @@ -0,0 +1,284 @@ +package multipoly; + +import static org.openstreetmap.josm.tools.I18n.tr; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import multipoly.GeometryFunctions.Intersection; + +import org.openstreetmap.josm.data.osm.Node; +import org.openstreetmap.josm.data.osm.Way; +import org.openstreetmap.josm.tools.MultiMap; + +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 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. + * TODO: Currently cannot process touching polygons. See code in JoinAreasAction. + * @return error description if the ways cannot be split. Null if all fine. + */ + public String makeFromWays(Collection ways){ + 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. + JoinedPolygon jw = new JoinedPolygon(w); + joinedWays.add(jw); + usedWays.add(w); + } + else { + nodesWithConnectedWays.put(w.lastNode(), w); + nodesWithConnectedWays.put(w.firstNode(), w); + } + } + + //process unclosed ways + for(Way startWay: ways) { + if (usedWays.contains(startWay)){ + continue; + } + + Node startNode = startWay.firstNode(); + List collectedWays = new ArrayList(); + List collectedWaysReverse = new ArrayList(); + Way curWay = startWay; + Node prevNode = startNode; + + //find polygon ways + while (true) { + 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; + } + } + + //move to the next way + curWay = nextWay; + prevNode = nextNode; + } + + usedWays.addAll(collectedWays); + joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse)); + } + + //analyze witch way is inside witch outside. + return makeFromPolygons(joinedWays); + } + + /** + * This method analyzes witch ways are inner and witch outer. Sets innerWays and outerWays to the result. + * @param joinedWays + * @return error description if the ways cannot be split. Null if all fine. + */ + private String makeFromPolygons(List polygons) { + 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 + { + //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; + } + + + +}