001 // License: GPL. For details, see LICENSE file.
002 package org.openstreetmap.josm.data.osm.visitor.paint.relations;
003
004 import java.awt.geom.Path2D;
005 import java.awt.geom.Path2D.Double;
006 import java.awt.geom.PathIterator;
007 import java.awt.geom.Point2D;
008 import java.awt.geom.Rectangle2D;
009 import java.util.ArrayList;
010 import java.util.Collection;
011 import java.util.Collections;
012 import java.util.HashSet;
013 import java.util.Iterator;
014 import java.util.List;
015 import java.util.Set;
016
017 import org.openstreetmap.josm.Main;
018 import org.openstreetmap.josm.data.Preferences.PreferenceChangeEvent;
019 import org.openstreetmap.josm.data.Preferences.PreferenceChangedListener;
020 import org.openstreetmap.josm.data.osm.DataSet;
021 import org.openstreetmap.josm.data.osm.Node;
022 import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
023 import org.openstreetmap.josm.data.osm.Relation;
024 import org.openstreetmap.josm.data.osm.RelationMember;
025 import org.openstreetmap.josm.data.osm.Way;
026 import org.openstreetmap.josm.data.osm.event.NodeMovedEvent;
027 import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent;
028 import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection;
029
030 public class Multipolygon {
031 /** preference key for a collection of roles which indicate that the respective member belongs to an
032 * <em>outer</em> polygon. Default is <tt>outer</tt>.
033 */
034 static public final String PREF_KEY_OUTER_ROLES = "mappaint.multipolygon.outer.roles";
035 /** preference key for collection of role prefixes which indicate that the respective
036 * member belongs to an <em>outer</em> polygon. Default is empty.
037 */
038 static public final String PREF_KEY_OUTER_ROLE_PREFIXES = "mappaint.multipolygon.outer.role-prefixes";
039 /** preference key for a collection of roles which indicate that the respective member belongs to an
040 * <em>inner</em> polygon. Default is <tt>inner</tt>.
041 */
042 static public final String PREF_KEY_INNER_ROLES = "mappaint.multipolygon.inner.roles";
043 /** preference key for collection of role prefixes which indicate that the respective
044 * member belongs to an <em>inner</em> polygon. Default is empty.
045 */
046 static public final String PREF_KEY_INNER_ROLE_PREFIXES = "mappaint.multipolygon.inner.role-prefixes";
047
048 /**
049 * <p>Kind of strategy object which is responsible for deciding whether a given
050 * member role indicates that the member belongs to an <em>outer</em> or an
051 * <em>inner</em> polygon.</p>
052 *
053 * <p>The decision is taken based on preference settings, see the four preference keys
054 * above.</p>
055 *
056 */
057 private static class MultipolygonRoleMatcher implements PreferenceChangedListener{
058 private final List<String> outerExactRoles = new ArrayList<String>();
059 private final List<String> outerRolePrefixes = new ArrayList<String>();
060 private final List<String> innerExactRoles = new ArrayList<String>();
061 private final List<String> innerRolePrefixes = new ArrayList<String>();
062
063 private void initDefaults() {
064 outerExactRoles.clear();
065 outerRolePrefixes.clear();
066 innerExactRoles.clear();
067 innerRolePrefixes.clear();
068 outerExactRoles.add("outer");
069 innerExactRoles.add("inner");
070 }
071
072 private void setNormalized(Collection<String> literals, List<String> target){
073 target.clear();
074 for(String l: literals) {
075 if (l == null) {
076 continue;
077 }
078 l = l.trim();
079 if (!target.contains(l)) {
080 target.add(l);
081 }
082 }
083 }
084
085 private void initFromPreferences() {
086 initDefaults();
087 if (Main.pref == null) return;
088 Collection<String> literals;
089 literals = Main.pref.getCollection(PREF_KEY_OUTER_ROLES);
090 if (literals != null && !literals.isEmpty()){
091 setNormalized(literals, outerExactRoles);
092 }
093 literals = Main.pref.getCollection(PREF_KEY_OUTER_ROLE_PREFIXES);
094 if (literals != null && !literals.isEmpty()){
095 setNormalized(literals, outerRolePrefixes);
096 }
097 literals = Main.pref.getCollection(PREF_KEY_INNER_ROLES);
098 if (literals != null && !literals.isEmpty()){
099 setNormalized(literals, innerExactRoles);
100 }
101 literals = Main.pref.getCollection(PREF_KEY_INNER_ROLE_PREFIXES);
102 if (literals != null && !literals.isEmpty()){
103 setNormalized(literals, innerRolePrefixes);
104 }
105 }
106
107 @Override
108 public void preferenceChanged(PreferenceChangeEvent evt) {
109 if (PREF_KEY_INNER_ROLE_PREFIXES.equals(evt.getKey()) ||
110 PREF_KEY_INNER_ROLES.equals(evt.getKey()) ||
111 PREF_KEY_OUTER_ROLE_PREFIXES.equals(evt.getKey()) ||
112 PREF_KEY_OUTER_ROLES.equals(evt.getKey())){
113 initFromPreferences();
114 }
115 }
116
117 public boolean isOuterRole(String role){
118 if (role == null) return false;
119 for (String candidate: outerExactRoles) {
120 if (role.equals(candidate)) return true;
121 }
122 for (String candidate: outerRolePrefixes) {
123 if (role.startsWith(candidate)) return true;
124 }
125 return false;
126 }
127
128 public boolean isInnerRole(String role){
129 if (role == null) return false;
130 for (String candidate: innerExactRoles) {
131 if (role.equals(candidate)) return true;
132 }
133 for (String candidate: innerRolePrefixes) {
134 if (role.startsWith(candidate)) return true;
135 }
136 return false;
137 }
138 }
139
140 /*
141 * Init a private global matcher object which will listen to preference
142 * changes.
143 */
144 private static MultipolygonRoleMatcher roleMatcher;
145 private static MultipolygonRoleMatcher getMultipolygonRoleMatcher() {
146 if (roleMatcher == null) {
147 roleMatcher = new MultipolygonRoleMatcher();
148 if (Main.pref != null){
149 roleMatcher.initFromPreferences();
150 Main.pref.addPreferenceChangeListener(roleMatcher);
151 }
152 }
153 return roleMatcher;
154 }
155
156 public static class JoinedWay {
157 private final List<Node> nodes;
158 private final Collection<Long> wayIds;
159 private final boolean selected;
160
161 public JoinedWay(List<Node> nodes, Collection<Long> wayIds, boolean selected) {
162 this.nodes = nodes;
163 this.wayIds = wayIds;
164 this.selected = selected;
165 }
166
167 public List<Node> getNodes() {
168 return nodes;
169 }
170
171 public Collection<Long> getWayIds() {
172 return wayIds;
173 }
174
175 public boolean isSelected() {
176 return selected;
177 }
178
179 public boolean isClosed() {
180 return nodes.isEmpty() || nodes.get(nodes.size() - 1).equals(nodes.get(0));
181 }
182 }
183
184 public static class PolyData {
185 public enum Intersection {INSIDE, OUTSIDE, CROSSING}
186
187 private final Path2D.Double poly;
188 public boolean selected;
189 private Rectangle2D bounds;
190 private final Collection<Long> wayIds;
191 private final List<Node> nodes;
192 private final List<PolyData> inners;
193
194 public PolyData(Way closedWay) {
195 this(closedWay.getNodes(), closedWay.isSelected(), Collections.singleton(closedWay.getUniqueId()));
196 }
197
198 public PolyData(JoinedWay joinedWay) {
199 this(joinedWay.getNodes(), joinedWay.isSelected(), joinedWay.getWayIds());
200 }
201
202 private PolyData(List<Node> nodes, boolean selected, Collection<Long> wayIds) {
203 this.wayIds = Collections.unmodifiableCollection(wayIds);
204 this.nodes = new ArrayList<Node>(nodes);
205 this.selected = selected;
206 this.inners = new ArrayList<Multipolygon.PolyData>();
207 this.poly = new Path2D.Double();
208 this.poly.setWindingRule(Path2D.WIND_EVEN_ODD);
209 buildPoly();
210 }
211
212 private void buildPoly() {
213 boolean initial = true;
214 for (Node n : nodes) {
215 Point2D p = n.getEastNorth();
216 if (p != null) {
217 if (initial) {
218 poly.moveTo(p.getX(), p.getY());
219 initial = false;
220 } else {
221 poly.lineTo(p.getX(), p.getY());
222 }
223 }
224 }
225 if (!initial) { // fix #7593
226 poly.closePath();
227 }
228 for (PolyData inner : inners) {
229 appendInner(inner.poly);
230 }
231 }
232
233 public PolyData(PolyData copy) {
234 this.selected = copy.selected;
235 this.poly = (Double) copy.poly.clone();
236 this.wayIds = Collections.unmodifiableCollection(copy.wayIds);
237 this.nodes = new ArrayList<Node>(copy.nodes);
238 this.inners = new ArrayList<Multipolygon.PolyData>(copy.inners);
239 }
240
241 public Intersection contains(Path2D.Double p) {
242 int contains = 0;
243 int total = 0;
244 double[] coords = new double[6];
245 for (PathIterator it = p.getPathIterator(null); !it.isDone(); it.next()) {
246 switch (it.currentSegment(coords)) {
247 case PathIterator.SEG_MOVETO:
248 case PathIterator.SEG_LINETO:
249 if (poly.contains(coords[0], coords[1])) {
250 contains++;
251 }
252 total++;
253 }
254 }
255 if (contains == total) return Intersection.INSIDE;
256 if (contains == 0) return Intersection.OUTSIDE;
257 return Intersection.CROSSING;
258 }
259
260 public void addInner(PolyData inner) {
261 inners.add(inner);
262 appendInner(inner.poly);
263 }
264
265 private void appendInner(Path2D.Double inner) {
266 poly.append(inner.getPathIterator(null), false);
267 }
268
269 public Path2D.Double get() {
270 return poly;
271 }
272
273 public Rectangle2D getBounds() {
274 if (bounds == null) {
275 bounds = poly.getBounds2D();
276 }
277 return bounds;
278 }
279
280 public Collection<Long> getWayIds() {
281 return wayIds;
282 }
283
284 private void resetNodes(DataSet dataSet) {
285 if (!nodes.isEmpty()) {
286 DataSet ds = dataSet;
287 // Find DataSet (can be null for several nodes when undoing nodes creation, see #7162)
288 for (Iterator<Node> it = nodes.iterator(); it.hasNext() && ds == null; ) {
289 ds = it.next().getDataSet();
290 }
291 nodes.clear();
292 if (ds == null) {
293 // DataSet still not found. This should not happen, but a warning does no harm
294 System.err.println("Warning: DataSet not found while resetting nodes in Multipolygon. This should not happen, you may report it to JOSM developers.");
295 } else if (wayIds.size() == 1) {
296 Way w = (Way) ds.getPrimitiveById(wayIds.iterator().next(), OsmPrimitiveType.WAY);
297 nodes.addAll(w.getNodes());
298 } else {
299 List<Way> waysToJoin = new ArrayList<Way>();
300 for (Iterator<Long> it = wayIds.iterator(); it.hasNext(); ) {
301 Way w = (Way) ds.getPrimitiveById(it.next(), OsmPrimitiveType.WAY);
302 if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge)
303 waysToJoin.add(w);
304 }
305 }
306 nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes());
307 }
308 resetPoly();
309 }
310 }
311
312 private void resetPoly() {
313 poly.reset();
314 buildPoly();
315 bounds = null;
316 }
317
318 public void nodeMoved(NodeMovedEvent event) {
319 final Node n = event.getNode();
320 boolean innerChanged = false;
321 for (PolyData inner : inners) {
322 if (inner.nodes.contains(n)) {
323 inner.resetPoly();
324 innerChanged = true;
325 }
326 }
327 if (nodes.contains(n) || innerChanged) {
328 resetPoly();
329 }
330 }
331
332 public void wayNodesChanged(WayNodesChangedEvent event) {
333 final Long wayId = event.getChangedWay().getUniqueId();
334 boolean innerChanged = false;
335 for (PolyData inner : inners) {
336 if (inner.wayIds.contains(wayId)) {
337 inner.resetNodes(event.getDataset());
338 innerChanged = true;
339 }
340 }
341 if (wayIds.contains(wayId) || innerChanged) {
342 resetNodes(event.getDataset());
343 }
344 }
345 }
346
347 private final List<Way> innerWays = new ArrayList<Way>();
348 private final List<Way> outerWays = new ArrayList<Way>();
349 private final List<PolyData> innerPolygons = new ArrayList<PolyData>();
350 private final List<PolyData> outerPolygons = new ArrayList<PolyData>();
351 private final List<PolyData> combinedPolygons = new ArrayList<PolyData>();
352
353 private boolean incomplete;
354
355 public Multipolygon(Relation r) {
356 load(r);
357 }
358
359 private void load(Relation r) {
360 MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher();
361
362 // Fill inner and outer list with valid ways
363 for (RelationMember m : r.getMembers()) {
364 if (m.getMember().isIncomplete()) {
365 this.incomplete = true;
366 } else if (m.getMember().isDrawable()) {
367 if (m.isWay()) {
368 Way w = m.getWay();
369
370 if (w.getNodesCount() < 2) {
371 continue;
372 }
373
374 if (matcher.isInnerRole(m.getRole())) {
375 innerWays.add(w);
376 } else if (matcher.isOuterRole(m.getRole())) {
377 outerWays.add(w);
378 } else if (!m.hasRole()) {
379 outerWays.add(w);
380 } // Remaining roles ignored
381 } // Non ways ignored
382 }
383 }
384
385 createPolygons(innerWays, innerPolygons);
386 createPolygons(outerWays, outerPolygons);
387 if (!outerPolygons.isEmpty()) {
388 addInnerToOuters();
389 }
390 }
391
392 public final boolean isIncomplete() {
393 return incomplete;
394 }
395
396 private void createPolygons(List<Way> ways, List<PolyData> result) {
397 List<Way> waysToJoin = new ArrayList<Way>();
398 for (Way way: ways) {
399 if (way.isClosed()) {
400 result.add(new PolyData(way));
401 } else {
402 waysToJoin.add(way);
403 }
404 }
405
406 for (JoinedWay jw: joinWays(waysToJoin)) {
407 result.add(new PolyData(jw));
408 }
409 }
410
411 public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin)
412 {
413 final Collection<JoinedWay> result = new ArrayList<JoinedWay>();
414 final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]);
415 int left = waysToJoin.size();
416 while (left > 0) {
417 Way w = null;
418 boolean selected = false;
419 List<Node> nodes = null;
420 Set<Long> wayIds = new HashSet<Long>();
421 boolean joined = true;
422 while (joined && left > 0) {
423 joined = false;
424 for (int i = 0; i < joinArray.length && left != 0; ++i) {
425 if (joinArray[i] != null) {
426 Way c = joinArray[i];
427 if (w == null) {
428 w = c;
429 selected = w.isSelected();
430 joinArray[i] = null;
431 --left;
432 } else {
433 int mode = 0;
434 int cl = c.getNodesCount()-1;
435 int nl;
436 if (nodes == null) {
437 nl = w.getNodesCount()-1;
438 if (w.getNode(nl) == c.getNode(0)) {
439 mode = 21;
440 } else if (w.getNode(nl) == c.getNode(cl)) {
441 mode = 22;
442 } else if (w.getNode(0) == c.getNode(0)) {
443 mode = 11;
444 } else if (w.getNode(0) == c.getNode(cl)) {
445 mode = 12;
446 }
447 } else {
448 nl = nodes.size()-1;
449 if (nodes.get(nl) == c.getNode(0)) {
450 mode = 21;
451 } else if (nodes.get(0) == c.getNode(cl)) {
452 mode = 12;
453 } else if (nodes.get(0) == c.getNode(0)) {
454 mode = 11;
455 } else if (nodes.get(nl) == c.getNode(cl)) {
456 mode = 22;
457 }
458 }
459 if (mode != 0) {
460 joinArray[i] = null;
461 joined = true;
462 if (c.isSelected()) {
463 selected = true;
464 }
465 --left;
466 if (nodes == null) {
467 nodes = w.getNodes();
468 wayIds.add(w.getUniqueId());
469 }
470 nodes.remove((mode == 21 || mode == 22) ? nl : 0);
471 if (mode == 21) {
472 nodes.addAll(c.getNodes());
473 } else if (mode == 12) {
474 nodes.addAll(0, c.getNodes());
475 } else if (mode == 22) {
476 for (Node node : c.getNodes()) {
477 nodes.add(nl, node);
478 }
479 } else /* mode == 11 */ {
480 for (Node node : c.getNodes()) {
481 nodes.add(0, node);
482 }
483 }
484 wayIds.add(c.getUniqueId());
485 }
486 }
487 }
488 } /* for(i = ... */
489 } /* while(joined) */
490
491 if (nodes == null) {
492 nodes = w.getNodes();
493 wayIds.add(w.getUniqueId());
494 }
495
496 result.add(new JoinedWay(nodes, wayIds, selected));
497 } /* while(left != 0) */
498
499 return result;
500 }
501
502 public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) {
503
504 // First try to test only bbox, use precise testing only if we don't get unique result
505 Rectangle2D innerBox = inner.getBounds();
506 PolyData insidePolygon = null;
507 PolyData intersectingPolygon = null;
508 int insideCount = 0;
509 int intersectingCount = 0;
510
511 for (PolyData outer: outerPolygons) {
512 if (outer.getBounds().contains(innerBox)) {
513 insidePolygon = outer;
514 insideCount++;
515 } else if (outer.getBounds().intersects(innerBox)) {
516 intersectingPolygon = outer;
517 intersectingCount++;
518 }
519 }
520
521 if (insideCount == 1)
522 return insidePolygon;
523 else if (intersectingCount == 1)
524 return intersectingPolygon;
525
526 PolyData result = null;
527 for (PolyData combined : outerPolygons) {
528 Intersection c = combined.contains(inner.poly);
529 if (c != Intersection.OUTSIDE)
530 {
531 if (result == null || result.contains(combined.poly) != Intersection.INSIDE) {
532 result = combined;
533 }
534 }
535 }
536 return result;
537 }
538
539 private void addInnerToOuters() {
540
541 if (innerPolygons.isEmpty()) {
542 combinedPolygons.addAll(outerPolygons);
543 } else if (outerPolygons.size() == 1) {
544 PolyData combinedOuter = new PolyData(outerPolygons.get(0));
545 for (PolyData inner: innerPolygons) {
546 combinedOuter.addInner(inner);
547 }
548 combinedPolygons.add(combinedOuter);
549 } else {
550 for (PolyData outer: outerPolygons) {
551 combinedPolygons.add(new PolyData(outer));
552 }
553
554 for (PolyData pdInner: innerPolygons) {
555 PolyData o = findOuterPolygon(pdInner, combinedPolygons);
556 if (o == null) {
557 o = outerPolygons.get(0);
558 }
559 o.addInner(pdInner);
560 }
561 }
562
563 // Clear inner and outer polygons to reduce memory footprint
564 innerPolygons.clear();
565 outerPolygons.clear();
566 }
567
568 public List<Way> getOuterWays() {
569 return outerWays;
570 }
571
572 public List<Way> getInnerWays() {
573 return innerWays;
574 }
575 /*
576 public List<PolyData> getInnerPolygons() {
577 return innerPolygons;
578 }
579
580 public List<PolyData> getOuterPolygons() {
581 return outerPolygons;
582 }
583 */
584 public List<PolyData> getCombinedPolygons() {
585 return combinedPolygons;
586 }
587 }