source: josm/trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/relations/Multipolygon.java@ 9017

Last change on this file since 9017 was 9017, checked in by bastiK, 8 years ago

mapcss: fix partial fill for incomplete multipolygons (see #12104)
  • Property svn:eol-style set to native
File size: 22.6 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.osm.visitor.paint.relations;
3
4import java.awt.geom.Path2D;
5import java.awt.geom.Path2D.Double;
6import java.awt.geom.PathIterator;
7import java.awt.geom.Rectangle2D;
8import java.util.ArrayList;
9import java.util.Collection;
10import java.util.Collections;
11import java.util.HashSet;
12import java.util.Iterator;
13import java.util.List;
14import java.util.Set;
15
16import org.openstreetmap.josm.Main;
17import org.openstreetmap.josm.data.Preferences.PreferenceChangeEvent;
18import org.openstreetmap.josm.data.Preferences.PreferenceChangedListener;
19import org.openstreetmap.josm.data.coor.EastNorth;
20import org.openstreetmap.josm.data.osm.DataSet;
21import org.openstreetmap.josm.data.osm.Node;
22import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
23import org.openstreetmap.josm.data.osm.Relation;
24import org.openstreetmap.josm.data.osm.RelationMember;
25import org.openstreetmap.josm.data.osm.Way;
26import org.openstreetmap.josm.data.osm.event.NodeMovedEvent;
27import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent;
28import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection;
29
30/**
31 * Multipolygon data used to represent complex areas, see <a href="https://wiki.openstreetmap.org/wiki/Relation:multipolygon">wiki</a>.
32 * @since 2788
33 */
34public class Multipolygon {
35
36 /** preference key for a collection of roles which indicate that the respective member belongs to an
37 * <em>outer</em> polygon. Default is <tt>outer</tt>.
38 */
39 public static final String PREF_KEY_OUTER_ROLES = "mappaint.multipolygon.outer.roles";
40
41 /** preference key for collection of role prefixes which indicate that the respective
42 * member belongs to an <em>outer</em> polygon. Default is empty.
43 */
44 public static final String PREF_KEY_OUTER_ROLE_PREFIXES = "mappaint.multipolygon.outer.role-prefixes";
45
46 /** preference key for a collection of roles which indicate that the respective member belongs to an
47 * <em>inner</em> polygon. Default is <tt>inner</tt>.
48 */
49 public static final String PREF_KEY_INNER_ROLES = "mappaint.multipolygon.inner.roles";
50
51 /** preference key for collection of role prefixes which indicate that the respective
52 * member belongs to an <em>inner</em> polygon. Default is empty.
53 */
54 public static final String PREF_KEY_INNER_ROLE_PREFIXES = "mappaint.multipolygon.inner.role-prefixes";
55
56 /**
57 * <p>Kind of strategy object which is responsible for deciding whether a given
58 * member role indicates that the member belongs to an <em>outer</em> or an
59 * <em>inner</em> polygon.</p>
60 *
61 * <p>The decision is taken based on preference settings, see the four preference keys
62 * above.</p>
63 */
64 private static class MultipolygonRoleMatcher implements PreferenceChangedListener {
65 private final List<String> outerExactRoles = new ArrayList<>();
66 private final List<String> outerRolePrefixes = new ArrayList<>();
67 private final List<String> innerExactRoles = new ArrayList<>();
68 private final List<String> innerRolePrefixes = new ArrayList<>();
69
70 private void initDefaults() {
71 outerExactRoles.clear();
72 outerRolePrefixes.clear();
73 innerExactRoles.clear();
74 innerRolePrefixes.clear();
75 outerExactRoles.add("outer");
76 innerExactRoles.add("inner");
77 }
78
79 private static void setNormalized(Collection<String> literals, List<String> target) {
80 target.clear();
81 for (String l: literals) {
82 if (l == null) {
83 continue;
84 }
85 l = l.trim();
86 if (!target.contains(l)) {
87 target.add(l);
88 }
89 }
90 }
91
92 private void initFromPreferences() {
93 initDefaults();
94 if (Main.pref == null) return;
95 Collection<String> literals;
96 literals = Main.pref.getCollection(PREF_KEY_OUTER_ROLES);
97 if (literals != null && !literals.isEmpty()) {
98 setNormalized(literals, outerExactRoles);
99 }
100 literals = Main.pref.getCollection(PREF_KEY_OUTER_ROLE_PREFIXES);
101 if (literals != null && !literals.isEmpty()) {
102 setNormalized(literals, outerRolePrefixes);
103 }
104 literals = Main.pref.getCollection(PREF_KEY_INNER_ROLES);
105 if (literals != null && !literals.isEmpty()) {
106 setNormalized(literals, innerExactRoles);
107 }
108 literals = Main.pref.getCollection(PREF_KEY_INNER_ROLE_PREFIXES);
109 if (literals != null && !literals.isEmpty()) {
110 setNormalized(literals, innerRolePrefixes);
111 }
112 }
113
114 @Override
115 public void preferenceChanged(PreferenceChangeEvent evt) {
116 if (PREF_KEY_INNER_ROLE_PREFIXES.equals(evt.getKey()) ||
117 PREF_KEY_INNER_ROLES.equals(evt.getKey()) ||
118 PREF_KEY_OUTER_ROLE_PREFIXES.equals(evt.getKey()) ||
119 PREF_KEY_OUTER_ROLES.equals(evt.getKey())) {
120 initFromPreferences();
121 }
122 }
123
124 public boolean isOuterRole(String role) {
125 if (role == null) return false;
126 for (String candidate: outerExactRoles) {
127 if (role.equals(candidate)) return true;
128 }
129 for (String candidate: outerRolePrefixes) {
130 if (role.startsWith(candidate)) return true;
131 }
132 return false;
133 }
134
135 public boolean isInnerRole(String role) {
136 if (role == null) return false;
137 for (String candidate: innerExactRoles) {
138 if (role.equals(candidate)) return true;
139 }
140 for (String candidate: innerRolePrefixes) {
141 if (role.startsWith(candidate)) return true;
142 }
143 return false;
144 }
145 }
146
147 /*
148 * Init a private global matcher object which will listen to preference changes.
149 */
150 private static MultipolygonRoleMatcher roleMatcher;
151
152 private static synchronized MultipolygonRoleMatcher getMultipolygonRoleMatcher() {
153 if (roleMatcher == null) {
154 roleMatcher = new MultipolygonRoleMatcher();
155 if (Main.pref != null) {
156 roleMatcher.initFromPreferences();
157 Main.pref.addPreferenceChangeListener(roleMatcher);
158 }
159 }
160 return roleMatcher;
161 }
162
163 public static class JoinedWay {
164 private final List<Node> nodes;
165 private final Collection<Long> wayIds;
166 private final boolean selected;
167
168 public JoinedWay(List<Node> nodes, Collection<Long> wayIds, boolean selected) {
169 this.nodes = nodes;
170 this.wayIds = wayIds;
171 this.selected = selected;
172 }
173
174 public List<Node> getNodes() {
175 return nodes;
176 }
177
178 public Collection<Long> getWayIds() {
179 return wayIds;
180 }
181
182 public boolean isSelected() {
183 return selected;
184 }
185
186 public boolean isClosed() {
187 return nodes.isEmpty() || nodes.get(nodes.size() - 1).equals(nodes.get(0));
188 }
189 }
190
191 public static class PolyData {
192 public enum Intersection {INSIDE, OUTSIDE, CROSSING}
193
194 private final Path2D.Double poly;
195 public boolean selected;
196 private Rectangle2D bounds;
197 private final Collection<Long> wayIds;
198 private final List<Node> nodes;
199 private final List<PolyData> inners;
200
201 public PolyData(Way closedWay) {
202 this(closedWay.getNodes(), closedWay.isSelected(), Collections.singleton(closedWay.getUniqueId()));
203 }
204
205 public PolyData(JoinedWay joinedWay) {
206 this(joinedWay.getNodes(), joinedWay.isSelected(), joinedWay.getWayIds());
207 }
208
209 private PolyData(List<Node> nodes, boolean selected, Collection<Long> wayIds) {
210 this.wayIds = Collections.unmodifiableCollection(wayIds);
211 this.nodes = new ArrayList<>(nodes);
212 this.selected = selected;
213 this.inners = new ArrayList<>();
214 this.poly = new Path2D.Double();
215 this.poly.setWindingRule(Path2D.WIND_EVEN_ODD);
216 buildPoly();
217 }
218
219 private void buildPoly() {
220 boolean initial = true;
221 for (Node n : nodes) {
222 EastNorth p = n.getEastNorth();
223 if (p != null) {
224 if (initial) {
225 poly.moveTo(p.getX(), p.getY());
226 initial = false;
227 } else {
228 poly.lineTo(p.getX(), p.getY());
229 }
230 }
231 }
232 for (PolyData inner : inners) {
233 appendInner(inner.poly);
234 }
235 }
236
237 public PolyData(PolyData copy) {
238 this.selected = copy.selected;
239 this.poly = (Double) copy.poly.clone();
240 this.wayIds = Collections.unmodifiableCollection(copy.wayIds);
241 this.nodes = new ArrayList<>(copy.nodes);
242 this.inners = new ArrayList<>(copy.inners);
243 }
244
245 public Intersection contains(Path2D.Double p) {
246 int contains = 0;
247 int total = 0;
248 double[] coords = new double[6];
249 for (PathIterator it = p.getPathIterator(null); !it.isDone(); it.next()) {
250 switch (it.currentSegment(coords)) {
251 case PathIterator.SEG_MOVETO:
252 case PathIterator.SEG_LINETO:
253 if (poly.contains(coords[0], coords[1])) {
254 contains++;
255 }
256 total++;
257 }
258 }
259 if (contains == total) return Intersection.INSIDE;
260 if (contains == 0) return Intersection.OUTSIDE;
261 return Intersection.CROSSING;
262 }
263
264 public void addInner(PolyData inner) {
265 inners.add(inner);
266 appendInner(inner.poly);
267 }
268
269 private void appendInner(Path2D.Double inner) {
270 poly.append(inner.getPathIterator(null), false);
271 }
272
273 public Path2D.Double get() {
274 return poly;
275 }
276
277 public Rectangle2D getBounds() {
278 if (bounds == null) {
279 bounds = poly.getBounds2D();
280 }
281 return bounds;
282 }
283
284 public Collection<Long> getWayIds() {
285 return wayIds;
286 }
287
288 public List<Node> getNodes() {
289 return nodes;
290 }
291
292 private void resetNodes(DataSet dataSet) {
293 if (!nodes.isEmpty()) {
294 DataSet ds = dataSet;
295 // Find DataSet (can be null for several nodes when undoing nodes creation, see #7162)
296 for (Iterator<Node> it = nodes.iterator(); it.hasNext() && ds == null;) {
297 ds = it.next().getDataSet();
298 }
299 nodes.clear();
300 if (ds == null) {
301 // DataSet still not found. This should not happen, but a warning does no harm
302 Main.warn("DataSet not found while resetting nodes in Multipolygon. " +
303 "This should not happen, you may report it to JOSM developers.");
304 } else if (wayIds.size() == 1) {
305 Way w = (Way) ds.getPrimitiveById(wayIds.iterator().next(), OsmPrimitiveType.WAY);
306 nodes.addAll(w.getNodes());
307 } else if (!wayIds.isEmpty()) {
308 List<Way> waysToJoin = new ArrayList<>();
309 for (Long wayId : wayIds) {
310 Way w = (Way) ds.getPrimitiveById(wayId, OsmPrimitiveType.WAY);
311 if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge)
312 waysToJoin.add(w);
313 }
314 }
315 if (!waysToJoin.isEmpty()) {
316 nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes());
317 }
318 }
319 resetPoly();
320 }
321 }
322
323 private void resetPoly() {
324 poly.reset();
325 buildPoly();
326 bounds = null;
327 }
328
329 public void nodeMoved(NodeMovedEvent event) {
330 final Node n = event.getNode();
331 boolean innerChanged = false;
332 for (PolyData inner : inners) {
333 if (inner.nodes.contains(n)) {
334 inner.resetPoly();
335 innerChanged = true;
336 }
337 }
338 if (nodes.contains(n) || innerChanged) {
339 resetPoly();
340 }
341 }
342
343 public void wayNodesChanged(WayNodesChangedEvent event) {
344 final Long wayId = event.getChangedWay().getUniqueId();
345 boolean innerChanged = false;
346 for (PolyData inner : inners) {
347 if (inner.wayIds.contains(wayId)) {
348 inner.resetNodes(event.getDataset());
349 innerChanged = true;
350 }
351 }
352 if (wayIds.contains(wayId) || innerChanged) {
353 resetNodes(event.getDataset());
354 }
355 }
356 }
357
358 private final List<Way> innerWays = new ArrayList<>();
359 private final List<Way> outerWays = new ArrayList<>();
360 private final List<PolyData> combinedPolygons = new ArrayList<>();
361 private final List<Node> openEnds = new ArrayList<>();
362
363 private boolean incomplete;
364
365 public Multipolygon(Relation r) {
366 load(r);
367 }
368
369 private void load(Relation r) {
370 MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher();
371
372 // Fill inner and outer list with valid ways
373 for (RelationMember m : r.getMembers()) {
374 if (m.getMember().isIncomplete()) {
375 this.incomplete = true;
376 } else if (m.getMember().isDrawable()) {
377 if (m.isWay()) {
378 Way w = m.getWay();
379
380 if (w.getNodesCount() < 2) {
381 continue;
382 }
383
384 if (matcher.isInnerRole(m.getRole())) {
385 innerWays.add(w);
386 } else if (matcher.isOuterRole(m.getRole())) {
387 outerWays.add(w);
388 } else if (!m.hasRole()) {
389 outerWays.add(w);
390 } // Remaining roles ignored
391 } // Non ways ignored
392 }
393 }
394
395 final List<PolyData> innerPolygons = new ArrayList<>();
396 final List<PolyData> outerPolygons = new ArrayList<>();
397 createPolygons(innerWays, innerPolygons);
398 createPolygons(outerWays, outerPolygons);
399 if (!outerPolygons.isEmpty()) {
400 addInnerToOuters(innerPolygons, outerPolygons);
401 }
402 }
403
404 public final boolean isIncomplete() {
405 return incomplete;
406 }
407
408 private void createPolygons(List<Way> ways, List<PolyData> result) {
409 List<Way> waysToJoin = new ArrayList<>();
410 for (Way way: ways) {
411 if (way.isClosed()) {
412 result.add(new PolyData(way));
413 } else {
414 waysToJoin.add(way);
415 }
416 }
417
418 for (JoinedWay jw: joinWays(waysToJoin)) {
419 result.add(new PolyData(jw));
420 if (!jw.isClosed()) {
421 openEnds.add(jw.getNodes().get(0));
422 openEnds.add(jw.getNodes().get(jw.getNodes().size() - 1));
423 }
424 }
425 }
426
427 public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin) {
428 final Collection<JoinedWay> result = new ArrayList<>();
429 final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]);
430 int left = waysToJoin.size();
431 while (left > 0) {
432 Way w = null;
433 boolean selected = false;
434 List<Node> nodes = null;
435 Set<Long> wayIds = new HashSet<>();
436 boolean joined = true;
437 while (joined && left > 0) {
438 joined = false;
439 for (int i = 0; i < joinArray.length && left != 0; ++i) {
440 if (joinArray[i] != null) {
441 Way c = joinArray[i];
442 if (c.getNodesCount() == 0) {
443 continue;
444 }
445 if (w == null) {
446 w = c;
447 selected = w.isSelected();
448 joinArray[i] = null;
449 --left;
450 } else {
451 int mode = 0;
452 int cl = c.getNodesCount()-1;
453 int nl;
454 if (nodes == null) {
455 nl = w.getNodesCount()-1;
456 if (w.getNode(nl) == c.getNode(0)) {
457 mode = 21;
458 } else if (w.getNode(nl) == c.getNode(cl)) {
459 mode = 22;
460 } else if (w.getNode(0) == c.getNode(0)) {
461 mode = 11;
462 } else if (w.getNode(0) == c.getNode(cl)) {
463 mode = 12;
464 }
465 } else {
466 nl = nodes.size()-1;
467 if (nodes.get(nl) == c.getNode(0)) {
468 mode = 21;
469 } else if (nodes.get(0) == c.getNode(cl)) {
470 mode = 12;
471 } else if (nodes.get(0) == c.getNode(0)) {
472 mode = 11;
473 } else if (nodes.get(nl) == c.getNode(cl)) {
474 mode = 22;
475 }
476 }
477 if (mode != 0) {
478 joinArray[i] = null;
479 joined = true;
480 if (c.isSelected()) {
481 selected = true;
482 }
483 --left;
484 if (nodes == null) {
485 nodes = w.getNodes();
486 wayIds.add(w.getUniqueId());
487 }
488 nodes.remove((mode == 21 || mode == 22) ? nl : 0);
489 if (mode == 21) {
490 nodes.addAll(c.getNodes());
491 } else if (mode == 12) {
492 nodes.addAll(0, c.getNodes());
493 } else if (mode == 22) {
494 for (Node node : c.getNodes()) {
495 nodes.add(nl, node);
496 }
497 } else /* mode == 11 */ {
498 for (Node node : c.getNodes()) {
499 nodes.add(0, node);
500 }
501 }
502 wayIds.add(c.getUniqueId());
503 }
504 }
505 }
506 }
507 }
508
509 if (nodes == null && w != null) {
510 nodes = w.getNodes();
511 wayIds.add(w.getUniqueId());
512 }
513
514 result.add(new JoinedWay(nodes, wayIds, selected));
515 }
516
517 return result;
518 }
519
520 public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) {
521
522 // First try to test only bbox, use precise testing only if we don't get unique result
523 Rectangle2D innerBox = inner.getBounds();
524 PolyData insidePolygon = null;
525 PolyData intersectingPolygon = null;
526 int insideCount = 0;
527 int intersectingCount = 0;
528
529 for (PolyData outer: outerPolygons) {
530 if (outer.getBounds().contains(innerBox)) {
531 insidePolygon = outer;
532 insideCount++;
533 } else if (outer.getBounds().intersects(innerBox)) {
534 intersectingPolygon = outer;
535 intersectingCount++;
536 }
537 }
538
539 if (insideCount == 1)
540 return insidePolygon;
541 else if (intersectingCount == 1)
542 return intersectingPolygon;
543
544 PolyData result = null;
545 for (PolyData combined : outerPolygons) {
546 if (combined.contains(inner.poly) != Intersection.OUTSIDE) {
547 if (result == null || result.contains(combined.poly) == Intersection.INSIDE) {
548 result = combined;
549 }
550 }
551 }
552 return result;
553 }
554
555 private void addInnerToOuters(List<PolyData> innerPolygons, List<PolyData> outerPolygons) {
556
557 if (innerPolygons.isEmpty()) {
558 combinedPolygons.addAll(outerPolygons);
559 } else if (outerPolygons.size() == 1) {
560 PolyData combinedOuter = new PolyData(outerPolygons.get(0));
561 for (PolyData inner: innerPolygons) {
562 combinedOuter.addInner(inner);
563 }
564 combinedPolygons.add(combinedOuter);
565 } else {
566 for (PolyData outer: outerPolygons) {
567 combinedPolygons.add(new PolyData(outer));
568 }
569
570 for (PolyData pdInner: innerPolygons) {
571 PolyData o = findOuterPolygon(pdInner, combinedPolygons);
572 if (o == null) {
573 o = outerPolygons.get(0);
574 }
575 o.addInner(pdInner);
576 }
577 }
578 }
579
580 /**
581 * Replies the list of outer ways.
582 * @return the list of outer ways
583 */
584 public List<Way> getOuterWays() {
585 return outerWays;
586 }
587
588 /**
589 * Replies the list of inner ways.
590 * @return the list of inner ways
591 */
592 public List<Way> getInnerWays() {
593 return innerWays;
594 }
595
596 public List<PolyData> getCombinedPolygons() {
597 return combinedPolygons;
598 }
599
600 public List<PolyData> getInnerPolygons() {
601 final List<PolyData> innerPolygons = new ArrayList<>();
602 createPolygons(innerWays, innerPolygons);
603 return innerPolygons;
604 }
605
606 public List<PolyData> getOuterPolygons() {
607 final List<PolyData> outerPolygons = new ArrayList<>();
608 createPolygons(outerWays, outerPolygons);
609 return outerPolygons;
610 }
611
612 /**
613 * Returns the start and end node of non-closed rings.
614 * @return the start and end node of non-closed rings.
615 */
616 public List<Node> getOpenEnds() {
617 return openEnds;
618 }
619}
Note: See TracBrowser for help on using the repository browser.