Index: /trunk/src/org/openstreetmap/josm/actions/CreateMultipolygonAction.java =================================================================== --- /trunk/src/org/openstreetmap/josm/actions/CreateMultipolygonAction.java (revision 15159) +++ /trunk/src/org/openstreetmap/josm/actions/CreateMultipolygonAction.java (revision 15160) @@ -3,4 +3,5 @@ import static org.openstreetmap.josm.tools.I18n.tr; +import static org.openstreetmap.josm.tools.I18n.trn; import java.awt.event.ActionEvent; @@ -12,4 +13,6 @@ import java.util.HashMap; import java.util.HashSet; +import java.util.Iterator; +import java.util.LinkedHashSet; import java.util.List; import java.util.Map; @@ -29,6 +32,4 @@ import org.openstreetmap.josm.data.UndoRedoHandler; import org.openstreetmap.josm.data.osm.DataSet; -import org.openstreetmap.josm.data.osm.MultipolygonBuilder; -import org.openstreetmap.josm.data.osm.MultipolygonBuilder.JoinedPolygon; import org.openstreetmap.josm.data.osm.OsmPrimitive; import org.openstreetmap.josm.data.osm.OsmUtils; @@ -36,4 +37,6 @@ import org.openstreetmap.josm.data.osm.RelationMember; import org.openstreetmap.josm.data.osm.Way; +import org.openstreetmap.josm.data.validation.TestError; +import org.openstreetmap.josm.data.validation.tests.MultipolygonTest; import org.openstreetmap.josm.gui.MainApplication; import org.openstreetmap.josm.gui.Notification; @@ -205,5 +208,5 @@ * @param selectedWays selected ways * @param selectedMultipolygonRelation selected multipolygon relation - * @return pair of old and new multipolygon relation + * @return pair of old and new multipolygon relation if a difference was found, else the pair contains the old relation twice */ public static Pair updateMultipolygonRelation(Collection selectedWays, Relation selectedMultipolygonRelation) { @@ -213,10 +216,53 @@ ways.addAll(selectedMultipolygonRelation.getMemberPrimitives(Way.class)); - final MultipolygonBuilder polygon = analyzeWays(ways, true); - if (polygon == null) { - return null; //could not make multipolygon. - } else { - return Pair.create(selectedMultipolygonRelation, createRelation(polygon, selectedMultipolygonRelation)); - } + // even if no way was added the inner/outer roles might be different + MultipolygonTest mpTest = new MultipolygonTest(); + Relation calculated = mpTest.makeFromWays(ways); + if (mpTest.getErrors().isEmpty()) { + return mergeRelationsMembers(selectedMultipolygonRelation, calculated); + } + showErrors(mpTest.getErrors()); + return null; //could not make multipolygon. + } + + /** + * Merge members of multipolygon relation. Maintains the order of the old relation. May change roles, + * removes duplicate and non-way members and adds new members found in {@code calculated}. + * @param old old multipolygon relation + * @param calculated calculated multipolygon relation + * @return pair of old and new multipolygon relation if a difference was found, else the pair contains the old relation twice + */ + private static Pair mergeRelationsMembers(Relation old, Relation calculated) { + Set merged = new LinkedHashSet<>(); + boolean foundDiff = false; + int nonWayMember = 0; + // maintain order of members in updated relation + for (RelationMember oldMem :old.getMembers()) { + if (oldMem.isNode() || oldMem.isRelation()) { + nonWayMember++; + continue; + } + for (RelationMember newMem : calculated.getMembers()) { + if (newMem.getMember().equals(oldMem.getMember())) { + if (!newMem.getRole().equals(oldMem.getRole())) { + foundDiff = true; + } + foundDiff |= !merged.add(newMem); // detect duplicate members in old relation + break; + } + } + } + if (nonWayMember > 0) { + foundDiff = true; + String msg = trn("Non-Way member removed from multipolygon", "Non-Way members removed from multipolygon", nonWayMember); + GuiHelper.runInEDT(() -> new Notification(msg).setIcon(JOptionPane.WARNING_MESSAGE).show()); + } + foundDiff |= merged.addAll(calculated.getMembers()); + if (!foundDiff) { + return Pair.create(old, old); // unchanged + } + Relation toModify = new Relation(old); + toModify.setMembers(new ArrayList<>(merged)); + return Pair.create(old, toModify); } @@ -228,10 +274,27 @@ */ public static Pair createMultipolygonRelation(Collection selectedWays, boolean showNotif) { - - final MultipolygonBuilder polygon = analyzeWays(selectedWays, showNotif); - if (polygon == null) { - return null; //could not make multipolygon. - } else { - return Pair.create(null, createRelation(polygon, null)); + MultipolygonTest mpTest = new MultipolygonTest(); + Relation calculated = mpTest.makeFromWays(selectedWays); + calculated.setMembers(RelationSorter.sortMembersByConnectivity(calculated.getMembers())); + if (mpTest.getErrors().isEmpty()) + return Pair.create(null, calculated); + if (showNotif) { + showErrors(mpTest.getErrors()); + } + return null; //could not make multipolygon. + } + + private static void showErrors(List errors) { + if (!errors.isEmpty()) { + StringBuilder sb = new StringBuilder(); + Set errorMessages = new LinkedHashSet<>(); + errors.forEach(e-> errorMessages.add(e.getMessage())); + Iterator iter = errorMessages.iterator(); + while (iter.hasNext()) { + sb.append(iter.next()); + if (iter.hasNext()) + sb.append('\n'); + } + GuiHelper.runInEDT(() -> new Notification(sb.toString()).setIcon(JOptionPane.INFORMATION_MESSAGE).show()); } } @@ -252,4 +315,5 @@ return null; } + boolean unchanged = rr.a == rr.b; final Relation existingRelation = rr.a; final Relation relation = rr.b; @@ -261,5 +325,20 @@ commandName = getName(false); } else { - list.add(new ChangeCommand(existingRelation, relation)); + if (!unchanged) { + list.add(new ChangeCommand(existingRelation, relation)); + } + if (list.isEmpty()) { + if (unchanged) { + MultipolygonTest mpTest = new MultipolygonTest(); + mpTest.visit(existingRelation); + if (!mpTest.getErrors().isEmpty()) { + showErrors(mpTest.getErrors()); + return null; + } + } + + GuiHelper.runInEDT(() -> new Notification(tr("Nothing changed")).setDuration(Notification.TIME_SHORT).setIcon(JOptionPane.INFORMATION_MESSAGE).show()); + return null; + } commandName = getName(true); } @@ -290,69 +369,4 @@ } - /** - * This method analyzes ways and creates multipolygon. - * @param selectedWays list of selected ways - * @param showNotif if {@code true}, shows a notification if an error occurs - * @return null, if there was a problem with the ways. - */ - private static MultipolygonBuilder analyzeWays(Collection selectedWays, boolean showNotif) { - - MultipolygonBuilder pol = new MultipolygonBuilder(); - final String error = pol.makeFromWays(selectedWays); - - if (error != null) { - if (showNotif) { - GuiHelper.runInEDT(() -> - new Notification(error) - .setIcon(JOptionPane.INFORMATION_MESSAGE) - .show()); - } - return null; - } else { - return pol; - } - } - - /** - * Builds a relation from polygon ways. - * @param pol data storage class containing polygon information - * @param clone relation to clone, can be null - * @return multipolygon relation - */ - private static Relation createRelation(MultipolygonBuilder pol, Relation clone) { - // Create new relation - Relation rel = clone != null ? new Relation(clone) : new Relation(); - rel.put("type", "multipolygon"); - // Add ways to it - for (JoinedPolygon jway:pol.outerWays) { - addMembers(jway, rel, "outer"); - } - - for (JoinedPolygon jway:pol.innerWays) { - addMembers(jway, rel, "inner"); - } - - if (clone == null) { - rel.setMembers(RelationSorter.sortMembersByConnectivity(rel.getMembers())); - } - - return rel; - } - - private static void addMembers(JoinedPolygon polygon, Relation rel, String role) { - final int count = rel.getMembersCount(); - final Set ways = new HashSet<>(polygon.ways); - for (int i = 0; i < count; i++) { - final RelationMember m = rel.getMember(i); - if (ways.contains(m.getMember()) && !role.equals(m.getRole())) { - rel.setMember(i, new RelationMember(role, m.getMember())); - } - } - ways.removeAll(rel.getMemberPrimitivesList()); - for (final Way way : ways) { - rel.addMember(new RelationMember(role, way)); - } - } - private static final List DEFAULT_LINEAR_TAGS = Arrays.asList("barrier", "fence_type", "source"); Index: /trunk/src/org/openstreetmap/josm/data/osm/MultipolygonBuilder.java =================================================================== --- /trunk/src/org/openstreetmap/josm/data/osm/MultipolygonBuilder.java (revision 15159) +++ /trunk/src/org/openstreetmap/josm/data/osm/MultipolygonBuilder.java (revision 15160) @@ -6,28 +6,18 @@ import java.awt.Rectangle; import java.awt.geom.Area; -import java.io.IOException; -import java.io.ObjectInputStream; -import java.io.ObjectOutputStream; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; -import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; -import java.util.concurrent.ForkJoinPool; -import java.util.concurrent.ForkJoinTask; -import java.util.concurrent.RecursiveTask; -import java.util.function.Supplier; import java.util.stream.Collectors; +import org.openstreetmap.josm.data.validation.tests.MultipolygonTest; import org.openstreetmap.josm.tools.CheckParameterUtil; import org.openstreetmap.josm.tools.Geometry; -import org.openstreetmap.josm.tools.Geometry.PolygonIntersection; -import org.openstreetmap.josm.tools.Logging; import org.openstreetmap.josm.tools.MultiMap; import org.openstreetmap.josm.tools.Pair; -import org.openstreetmap.josm.tools.Utils; /** @@ -39,77 +29,20 @@ public class MultipolygonBuilder { - private static final ForkJoinPool THREAD_POOL = newForkJoinPool(); - - private static ForkJoinPool newForkJoinPool() { - try { - return Utils.newForkJoinPool( - "multipolygon_creation.numberOfThreads", "multipolygon-builder-%d", Thread.NORM_PRIORITY); - } catch (SecurityException e) { - Logging.log(Logging.LEVEL_ERROR, "Unable to create new ForkJoinPool", e); - return null; - } - } - - /** - * Helper class to avoid unneeded costly intersection calculations. - * If the intersection between polygons a and b was calculated we also know - * the result of intersection between b and a. The lookup in the hash tables is - * much faster than the intersection calculation. - */ - private static class IntersectionMatrix { - private final Map, PolygonIntersection> results; - - IntersectionMatrix(Collection polygons) { - results = new HashMap<>(Utils.hashMapInitialCapacity(polygons.size() * polygons.size())); - } - - /** - * Compute the reverse result of the intersection test done by {@code Geometry.polygonIntersection(Area a1, Area a2)} - * - * @param intersection the intersection result for polygons a1 and a2 (in that order) - * @return the intersection result for a2 and a1 - */ - private static PolygonIntersection getReverseIntersectionResult(PolygonIntersection intersection) { - switch (intersection) { - case FIRST_INSIDE_SECOND: - return PolygonIntersection.SECOND_INSIDE_FIRST; - case SECOND_INSIDE_FIRST: - return PolygonIntersection.FIRST_INSIDE_SECOND; - default: - return intersection; - } - } - - /** - * Returns the precomputed intersection between two polygons if known. Otherwise perform {@code computation}. - * - * @param a1 first polygon - * @param a2 second polygon - * @param computation the computation to perform when intersection is unknown - * @return the intersection between two polygons - * @see Map#computeIfAbsent - */ - PolygonIntersection computeIfAbsent(JoinedPolygon a1, JoinedPolygon a2, Supplier computation) { - PolygonIntersection intersection = results.get(Pair.create(a1, a2)); - if (intersection == null) { - intersection = computation.get(); - synchronized (results) { - results.put(Pair.create(a1, a2), intersection); - results.put(Pair.create(a2, a1), getReverseIntersectionResult(intersection)); - } - } - return intersection; - } - - } - /** * Represents one polygon that consists of multiple ways. */ public static class JoinedPolygon { + /** list of ways building this polygon */ public final List ways; + /** list of flags that indicate if the nodes of the way in the same position where reversed */ public final List reversed; + /** the nodes of the polygon, first node is not duplicated as last node. */ public final List nodes; + /** the area in east/north space */ public final Area area; + /** the integer bounds, + * @deprecated better use area.getBounds2D() + * */ + @Deprecated public final Rectangle bounds; @@ -140,38 +73,21 @@ */ public List getNodes() { - List nodes = new ArrayList<>(); + List ringNodes = 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) { + + if (!this.reversed.get(waypos)) { for (int pos = 0; pos < way.getNodesCount() - 1; pos++) { - nodes.add(way.getNode(pos)); + ringNodes.add(way.getNode(pos)); } } else { for (int pos = way.getNodesCount() - 1; pos > 0; pos--) { - nodes.add(way.getNode(pos)); + ringNodes.add(way.getNode(pos)); } } } - return nodes; - } - } - - /** - * Helper storage class for finding findOuterWays - */ - static class PolygonLevel { - public final int level; // nesting level, even for outer, odd for inner polygons. - public final JoinedPolygon outerWay; - - public List innerWays; - - PolygonLevel(JoinedPolygon pol, int level) { - this.outerWay = pol; - this.level = level; - this.innerWays = new ArrayList<>(); + return ringNodes; } } @@ -202,17 +118,20 @@ /** * Splits ways into inner and outer JoinedWays. Sets {@link #innerWays} and {@link #outerWays} to the result. - * TODO: Currently cannot process touching polygons. See code in JoinAreasAction. + * Calculation is done in {@link MultipolygonTest#makeFromWays(Collection)} to ensure that the result is a valid multipolygon. * @param ways ways to analyze * @return error description if the ways cannot be split, {@code null} if all fine. */ public String makeFromWays(Collection ways) { - try { - List joinedWays = joinWays(ways); - //analyze witch way is inside witch outside. - return makeFromPolygons(joinedWays); - } catch (JoinedPolygonCreationException ex) { - Logging.debug(ex); - return ex.getMessage(); - } + MultipolygonTest mpTest = new MultipolygonTest(); + Relation calculated = mpTest.makeFromWays(ways); + if (!mpTest.getErrors().isEmpty()) { + return mpTest.getErrors().iterator().next().getMessage(); + } + Pair, List> outerInner = joinWays(calculated); + this.outerWays.clear(); + this.innerWays.clear(); + this.outerWays.addAll(outerInner.a); + this.innerWays.addAll(outerInner.b); + return null; } @@ -328,191 +247,3 @@ return joinedWays; } - - /** - * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result. - * @param polygons polygons to analyze - * @return error description if the ways cannot be split, {@code null} if all fine. - */ - private String makeFromPolygons(List polygons) { - List list = findOuterWaysMultiThread(polygons); - - if (list == null) { - return tr("There is an intersection between ways."); - } - - this.outerWays.clear(); - this.innerWays.clear(); - - //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; - } - - private static Pair> findInnerWaysCandidates(IntersectionMatrix cache, - JoinedPolygon outerWay, Collection boundaryWays) { - boolean outerGood = true; - List innerCandidates = new ArrayList<>(); - - for (JoinedPolygon innerWay : boundaryWays) { - if (innerWay == outerWay) { - continue; - } - - // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection - if (outerWay.bounds.intersects(innerWay.bounds)) { - // Bounds intersection, let's see in detail - final PolygonIntersection intersection = cache.computeIfAbsent(outerWay, innerWay, - () -> Geometry.polygonIntersection(outerWay.area, innerWay.area)); - - 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; - } - } - } - - return new Pair<>(outerGood, innerCandidates); - } - - /** - * Collects outer way and corresponding inner ways from all boundaries. - * @param boundaryWays boundary ways - * @return the outermostWay, or {@code null} if intersection found. - */ - private static List findOuterWaysMultiThread(List boundaryWays) { - final IntersectionMatrix cache = new IntersectionMatrix(boundaryWays); - if (THREAD_POOL != null) { - return THREAD_POOL.invoke(new Worker(cache, boundaryWays, 0, boundaryWays.size(), new ArrayList(), - Math.max(32, boundaryWays.size() / THREAD_POOL.getParallelism() / 3))); - } else { - return new Worker(cache, boundaryWays, 0, boundaryWays.size(), new ArrayList(), 0).computeDirectly(); - } - } - - private static class Worker extends RecursiveTask> { - - // Needed for Findbugs / Coverity because parent class is serializable - private static final long serialVersionUID = 1L; - - private final transient List input; - private final int from; - private final int to; - private final transient List output; - private final int directExecutionTaskSize; - private final IntersectionMatrix cache; - - Worker(IntersectionMatrix cache, List input, int from, int to, List output, int directExecutionTaskSize) { - this.cache = cache; - this.input = input; - this.from = from; - this.to = to; - this.output = output; - this.directExecutionTaskSize = directExecutionTaskSize; - } - - /** - * Collects outer way and corresponding inner ways from all boundaries. - * @param level nesting level - * @param cache cache that tracks previously calculated results - * @param boundaryWays boundary ways - * @return the outermostWay, or {@code null} if intersection found. - */ - private static List findOuterWaysRecursive(int level, IntersectionMatrix cache, List boundaryWays) { - - final List result = new ArrayList<>(); - - for (JoinedPolygon outerWay : boundaryWays) { - if (processOuterWay(level, cache, boundaryWays, result, outerWay) == null) { - return null; - } - } - - return result; - } - - private static List processOuterWay(int level, IntersectionMatrix cache, List boundaryWays, - final List result, JoinedPolygon outerWay) { - Pair> p = findInnerWaysCandidates(cache, outerWay, boundaryWays); - if (p == null) { - // ways intersect - return null; - } - - if (p.a) { - //add new outer polygon - PolygonLevel pol = new PolygonLevel(outerWay, level); - - //process inner ways - if (!p.b.isEmpty()) { - List innerList = findOuterWaysRecursive(level + 1, cache, p.b); - 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; - } - - @Override - protected List compute() { - if (to - from <= directExecutionTaskSize) { - return computeDirectly(); - } else { - final Collection>> tasks = new ArrayList<>(); - for (int fromIndex = from; fromIndex < to; fromIndex += directExecutionTaskSize) { - tasks.add(new Worker(cache, input, fromIndex, Math.min(fromIndex + directExecutionTaskSize, to), - new ArrayList(), directExecutionTaskSize)); - } - for (ForkJoinTask> task : ForkJoinTask.invokeAll(tasks)) { - List res = task.join(); - if (res == null) { - return null; - } - output.addAll(res); - } - return output; - } - } - - List computeDirectly() { - for (int i = from; i < to; i++) { - if (processOuterWay(0, cache, input, output, input.get(i)) == null) { - return null; - } - } - return output; - } - - private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException { - // Needed for Findbugs / Coverity because parent class is serializable - ois.defaultReadObject(); - } - - private void writeObject(ObjectOutputStream oos) throws IOException { - // Needed for Findbugs / Coverity because parent class is serializable - oos.defaultWriteObject(); - } - } } Index: /trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java =================================================================== --- /trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java (revision 15159) +++ /trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java (revision 15160) @@ -79,4 +79,7 @@ private static final int FOUND_OUTSIDE = 2; + /** set when used to build a multipolygon relation */ + private Relation createdRelation; + /** * Constructs a new {@code MultipolygonTest}. @@ -464,7 +467,18 @@ return; } - + if (r == createdRelation) { + List modMembers = new ArrayList<>(); + for (PolygonLevel pol : list) { + final String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner"; + for (long wayId : pol.outerWay.getWayIds()) { + RelationMember member = wayMap.get(wayId); + modMembers.add(new RelationMember(calculatedRole, member.getMember())); + } + } + r.setMembers(modMembers); + return; + } for (PolygonLevel pol : list) { - String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner"; + final String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner"; for (long wayId : pol.outerWay.getWayIds()) { RelationMember member = wayMap.get(wayId); @@ -894,3 +908,30 @@ } } + + /** + * Create a multipolygon relation from the given ways and test it. + * @param ways the collection of ways + * @return a pair of a {@link Multipolygon} instance and the relation. + * @since 15160 + */ + public Relation makeFromWays(Collection ways) { + Relation r = new Relation(); + createdRelation = r; + r.put("type", "multipolygon"); + for (Way w : ways) { + r.addMember(new RelationMember("", w)); + } + errors.clear(); + Multipolygon polygon = null; + boolean hasRepeatedMembers = checkRepeatedWayMembers(r); + if (!hasRepeatedMembers) { + polygon = new Multipolygon(r); + // don't check style consistency here + checkGeometryAndRoles(r, polygon); + } + createdRelation = null; + errors.removeIf(e->e.getSeverity() == Severity.OTHER); + return r; + } + } Index: /trunk/src/org/openstreetmap/josm/tools/Geometry.java =================================================================== --- /trunk/src/org/openstreetmap/josm/tools/Geometry.java (revision 15159) +++ /trunk/src/org/openstreetmap/josm/tools/Geometry.java (revision 15160) @@ -1016,10 +1016,10 @@ for (JoinedPolygon out : outerInner.a) { if (a1 == null - ? nodeInsidePolygon(nodes.get(0), out.getNodes()) + ? nodeInsidePolygon(nodes.get(0), out.nodes) : PolygonIntersection.FIRST_INSIDE_SECOND == polygonIntersection(a1, out.area)) { boolean insideInner = false; // If inside an outer, check it is not inside an inner for (JoinedPolygon in : outerInner.b) { - if (a1 == null ? nodeInsidePolygon(nodes.get(0), in.getNodes()) + if (a1 == null ? nodeInsidePolygon(nodes.get(0), in.nodes) : in.area.getBounds2D().contains(a1.getBounds2D()) && polygonIntersection(a1, in.area) == PolygonIntersection.FIRST_INSIDE_SECOND