I have found that some multipolygons use nested inner polygons.
Example:
* A forest (outer) with a lake (inner) that has an island (inner) which
is not a forest. (example:
http://www.openstreetmap.org/browse/relation/331402)
By definition of the multipolygon relation
(http://wiki.openstreetmap.org/wiki/Relation:multipolygon) one has to
create two mps. But I see that it is a nice simplification lots of
mappers are using.
Attached patch handles this situation.
The inner and outer roles are now used as follows:
* the outmost polygon must have role=outer (or role=<empty>)
* all outmost polygons with role=inner are not used (a warning is issued)
* all inside polygons with role=inner use their own tagging
* all inside polygons with role=outer use the mp tagging if available or
their own tagging if the mp is not tagged
* all inside polygons with role=<empty> are categorized automatically as
outer/inner depending on the nest level
* all inside polygons with role=outer without a direct ambient inner
polygon are dropped with a warning message (outer in outer polygon)
Most of the renderers do not support inner in inner polygons but I think
it is a very reasonable extension of the multipolygon handling.
This patch also improves the error messages. I haven't seen any more
"are not processed due to an unknown reason" messages and I look forward
that the community will also not be able to generate any more ... ;-)
WanMil
There have been different opinions about this patch.
There is one controversal point:
Should mkgmap allow nested inner polygons?
From my point of view: YES. Because it does not harm in any way. The
nested inner polygons I analysed were all reasonable. Ok, they are not
100% compliant to the specification but this is common to lots of others
things in (anarchic) OSM.
At the moment I see two possible changes:
1. Issue a warning for any nested inner polygon but process it anyhow.
2. Reject nested inner polygons (and issue a warning). What a pity but
they are not 100% compliant.
Please let me know what's the opinion of mkgmap community and committers
because I want the improvements of error messages to be committed.
WanMil
The patch improves the handling of roles and warning messages in
multipolygon.
- A reasonable warning message for nested outer and nested inner
polygons is given
- nested inner polygons are processed anyhow
WanMil
Index: src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(revision 1598)
+++ src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(working copy)
@@ -497,14 +497,19 @@
}
private ArrayList<PolygonStatus> getPolygonStatus(BitSet
outmostPolygons,
- boolean outer) {
+ String defaultRole) {
ArrayList<PolygonStatus> polygonStatusList = new
ArrayList<PolygonStatus>();
for (int polyIndex = outmostPolygons.nextSetBit(0); polyIndex
>= 0; polyIndex = outmostPolygons
.nextSetBit(polyIndex + 1)) {
// polyIndex is the polygon that is not contained by
any other
// polygon
JoinedWay polygon = polygons.get(polyIndex);
- polygonStatusList.add(new PolygonStatus(outer,
polyIndex, polygon));
+ String role = getRole(polygon);
+ // if the role is not explicitly set use the default
role
+ if (role == null || "".equals(role)) {
+ role = defaultRole;
+ }
+ polygonStatusList.add(new
PolygonStatus("outer".equals(role), polyIndex, polygon));
}
return polygonStatusList;
}
@@ -513,6 +518,7 @@
* Process the ways in this relation. Joins way with the role "outer"
Adds
* ways with the role "inner" to the way with the role "outer"
*/
+ @Override
public void processElements() {
log.info("Processing multipolygon", toBrowseURL());
@@ -533,17 +539,18 @@
bboxArea = new Area(new Rectangle(bbox.getMinLong(), bbox
.getMinLat(), bbox.getMaxLong() - bbox.getMinLong(),
bbox.getMaxLat() - bbox.getMinLat()));
-
+
+ // join all single ways to polygons, try to close ways and
remove non closed ways
polygons = joinWays(allWays);
closeWays(polygons);
removeUnclosedWays(polygons);
- // now we have closed ways == polygons only
+ // now only closed ways are left => polygons only
// check if we have at least one polygon left
if (polygons.isEmpty()) {
// do nothing
- log.warn("Multipolygon " + toBrowseURL()
+ log.info("Multipolygon " + toBrowseURL()
+ " does not contain a closed
polygon.");
cleanup();
return;
@@ -561,21 +568,29 @@
// the intersectingPolygons marks all intersecting/overlapping
polygons
intersectingPolygons = new HashSet<JoinedWay>();
+
+ // check which polygons lie inside which other polygon
createContainsMatrix(polygons);
+ // unfinishedPolygons marks which polygons are not yet processed
BitSet unfinishedPolygons = new BitSet(polygons.size());
unfinishedPolygons.set(0, polygons.size());
// create bitsets which polygons belong to the outer and to the
inner role
BitSet innerPolygons = new BitSet();
+ BitSet taggedInnerPolygons = new BitSet();
BitSet outerPolygons = new BitSet();
+ BitSet taggedOuterPolygons = new BitSet();
+
int wi = 0;
for (Way w : polygons) {
String role = getRole(w);
if ("inner".equals(role)) {
innerPolygons.set(wi);
+ taggedInnerPolygons.set(wi);
} else if ("outer".equals(role)) {
outerPolygons.set(wi);
+ taggedOuterPolygons.set(wi);
} else {
// unknown role => it could be both
innerPolygons.set(wi);
@@ -586,26 +601,39 @@
if (outerPolygons.isEmpty()) {
log.warn("Multipolygon", toBrowseURL(),
- "does not contain any way tagged with
role=outer.");
+ "does not contain any way tagged with
role=outer or empty role.");
cleanup();
return;
}
Queue<PolygonStatus> polygonWorkingQueue = new
LinkedBlockingQueue<PolygonStatus>();
+ BitSet nestedOuterPolygons = new BitSet();
+ BitSet nestedInnerPolygons = new BitSet();
- BitSet outmostPolygons =
findOutmostPolygons(unfinishedPolygons, outerPolygons);
- if (outmostPolygons.isEmpty()) {
- // WanMil: do not process these polygons
- // this would probably cause wrong mps. Issue a warning
later in the
- // code
+ BitSet outmostPolygons ;
+ BitSet outmostInnerPolygons = new BitSet();
+ boolean outmostInnerFound = false;
+ do {
+ outmostInnerFound = false;
+ outmostPolygons =
findOutmostPolygons(unfinishedPolygons);
- // // there's no outmost outer polygon
- // // maybe this is a tile problem
- // // try to continue with the inner polygons
- // outmostPolygons =
findOutmostPolygons(unfinishedPolygons, innerPolygons);
- //
polygonWorkingQueue.addAll(getPolygonStatus(outmostPolygons, false));
- } else {
-
polygonWorkingQueue.addAll(getPolygonStatus(outmostPolygons, true));
+ if (outmostPolygons.intersects(taggedInnerPolygons)) {
+ outmostInnerPolygons.or(outmostPolygons);
+ outmostInnerPolygons.and(taggedInnerPolygons);
+
+ if (log.isDebugEnabled())
+ log.debug("wrong inner polygons: " +
outmostInnerPolygons);
+ // do not process polygons tagged with
role=inner but which are
+ // not
+ // contained by any other polygon
+ unfinishedPolygons.andNot(outmostInnerPolygons);
+ outmostPolygons.andNot(outmostInnerPolygons);
+ outmostInnerFound = true;
+ }
+ } while (outmostInnerFound);
+
+ if (outmostPolygons.isEmpty() == false) {
+
polygonWorkingQueue.addAll(getPolygonStatus(outmostPolygons, "outer"));
}
while (polygonWorkingQueue.isEmpty() == false) {
@@ -613,11 +641,6 @@
// the polygon is not contained by any other unfinished
polygon
PolygonStatus currentPolygon =
polygonWorkingQueue.poll();
- // QA: check that all ways carry the role "outer/inner"
and
- // issue warnings
- checkRoles(currentPolygon.polygon.getOriginalWays(),
- (currentPolygon.outer ? "outer" : "inner"));
-
// this polygon is now processed and should not be used
by any
// further step
unfinishedPolygons.clear(currentPolygon.index);
@@ -632,13 +655,44 @@
// get the holes
// these are all polygons that are in the main polygon
// and that are not contained by any other polygon
- BitSet holeIndexes =
findOutmostPolygons(polygonContains,
- (currentPolygon.outer ? innerPolygons :
outerPolygons));
+ boolean holesOk = true;
+ BitSet holeIndexes;
+ do {
+ holeIndexes =
findOutmostPolygons(polygonContains);
+ holesOk = true;
+ if (currentPolygon.outer) {
+ // for role=outer only role=inner is
allowed
+ if
(holeIndexes.intersects(taggedOuterPolygons)) {
+ BitSet addOuterNestedPolygons =
new BitSet();
+
addOuterNestedPolygons.or(holeIndexes);
+
addOuterNestedPolygons.and(taggedOuterPolygons);
+
nestedOuterPolygons.or(addOuterNestedPolygons);
+
holeIndexes.andNot(addOuterNestedPolygons);
+ // do not process them
+
unfinishedPolygons.andNot(addOuterNestedPolygons);
+
polygonContains.andNot(addOuterNestedPolygons);
+
+ // recalculate the holes again
to get all inner polygons
+ // in the nested outer polygons
+ holesOk = false;
+ }
+ } else {
+ // for role=inner both role=inner and
role=outer is supported
+ // although inner in inner is not
officially allowed
+ if
(holeIndexes.intersects(taggedInnerPolygons)) {
+ // process inner in inner but
issue a warning later
+ BitSet addInnerNestedPolygons =
new BitSet();
+
addInnerNestedPolygons.or(holeIndexes);
+
addInnerNestedPolygons.and(taggedInnerPolygons);
+
nestedInnerPolygons.or(addInnerNestedPolygons);
+ }
+ }
+ } while (holesOk == false);
- ArrayList<PolygonStatus> holes =
getPolygonStatus(holeIndexes,
- !currentPolygon.outer);
+ ArrayList<PolygonStatus> holes =
getPolygonStatus(holeIndexes,
+ (currentPolygon.outer ? "inner" : "outer"));
- // these polygons must all be checked for inner polygons
+ // these polygons must all be checked for holes
polygonWorkingQueue.addAll(holes);
// check if the polygon has tags and therefore should
be processed
@@ -646,20 +700,15 @@
||
hasPolygonTags(currentPolygon.polygon);
if (processPolygon) {
- List<Way> singularOuterPolygons;
- if (holes.isEmpty()) {
- singularOuterPolygons = Collections
- .singletonList((Way)
new JoinedWay(currentPolygon.polygon));
- } else {
- List<Way> innerWays = new
ArrayList<Way>(holes.size());
- for (PolygonStatus polygonHoleStatus :
holes) {
-
innerWays.add(polygonHoleStatus.polygon);
- }
- singularOuterPolygons =
cutOutInnerPolygons(currentPolygon.polygon,
- innerWays);
+ List<Way> innerWays = new
ArrayList<Way>(holes.size());
+ for (PolygonStatus polygonHoleStatus : holes) {
+
innerWays.add(polygonHoleStatus.polygon);
}
-
+
+ List<Way> singularOuterPolygons =
cutOutInnerPolygons(
+ currentPolygon.polygon, innerWays);
+
if
(currentPolygon.polygon.getOriginalWays().size() == 1) {
// the original way was a closed
polygon which
// has been replaced by the new cutted
polygon
@@ -694,11 +743,15 @@
}
}
}
-
- if (log.isLoggable(Level.WARNING) &&
unfinishedPolygons.isEmpty() == false) {
+
+ if (log.isLoggable(Level.WARNING) &&
+
(outmostInnerPolygons.cardinality()+unfinishedPolygons.cardinality()+nestedOuterPolygons.cardinality()+nestedInnerPolygons.cardinality()
>= 1)) {
log.warn("Multipolygon", toBrowseURL(), "contains
errors.");
runIntersectionCheck(unfinishedPolygons);
+ runOutmostInnerPolygonCheck(outmostInnerPolygons);
+ runNestedOuterPolygonCheck(nestedOuterPolygons);
+ runNestedInnerPolygonCheck(nestedInnerPolygons);
runWrongInnerPolygonCheck(unfinishedPolygons,
innerPolygons);
// we have at least one polygon that could not be
processed
@@ -745,6 +798,36 @@
}
}
+ private void runNestedOuterPolygonCheck(BitSet nestedOuterPolygons) {
+ // just print out warnings
+ // the check has been done before
+ for (int wiIndex = nestedOuterPolygons.nextSetBit(0); wiIndex
>= 0; wiIndex = nestedOuterPolygons
+ .nextSetBit(wiIndex + 1)) {
+ Way outerWay = polygons.get(wiIndex);
+ log.warn("Polygon", outerWay, "carries role outer
but lies inside an outer polygon. Potentially its role should be inner.");
+ }
+ }
+
+ private void runNestedInnerPolygonCheck(BitSet nestedInnerPolygons) {
+ // just print out warnings
+ // the check has been done before
+ for (int wiIndex = nestedInnerPolygons.nextSetBit(0); wiIndex
>= 0; wiIndex = nestedInnerPolygons
+ .nextSetBit(wiIndex + 1)) {
+ Way innerWay = polygons.get(wiIndex);
+ log.warn("Polygon", innerWay, "carries role",
getRole(innerWay), "but lies inside an inner polygon. Potentially its role
should be outer.");
+ }
+ }
+
+ private void runOutmostInnerPolygonCheck(BitSet outmostInnerPolygons) {
+ // just print out warnings
+ // the check has been done before
+ for (int wiIndex = outmostInnerPolygons.nextSetBit(0); wiIndex
>= 0; wiIndex = outmostInnerPolygons
+ .nextSetBit(wiIndex + 1)) {
+ Way innerWay = polygons.get(wiIndex);
+ log.warn("Polygon", innerWay, "carries role",
getRole(innerWay), "but is not inside any other polygon. Potentially it does
not belong to this multipolygon.");
+ }
+ }
+
private void runWrongInnerPolygonCheck(BitSet unfinishedPolygons,
BitSet innerPolygons) {
// find all unfinished inner polygons that are not contained by
any
@@ -858,7 +941,7 @@
// use the java.awt.geom.Area class because it's a quick
// implementation of what's needed
-
+
// this list contains all non overlapping and singular areas
// of the outerPolygon
Queue<AreaCutData> areasToCut = new LinkedList<AreaCutData>();
@@ -1176,29 +1259,6 @@
}
/**
- * This is a QA method. All ways of the given wayList are checked if
they
- * they carry the checkRole. If not a warning is logged.
- *
- * @param wayList
- * @param checkRole
- */
- private void checkRoles(List<Way> wayList, String checkRole) {
- // QA: check that all ways carry the role "inner" and issue
warnings
- for (Way tempWay : wayList) {
- String realRole = getRole(tempWay);
- if (checkRole.equals(realRole) == false &&
"".equals(realRole) == false) {
- if (tempWay instanceof JoinedWay) {
- log.warn("Polygon composed of ways",
((JoinedWay) tempWay).getOriginalIds(), "carries role", realRole,
- "but should carry role",
checkRole);
- } else {
- log.warn("Way", tempWay.getId(),
"carries role", realRole,
- "but should carry role",
checkRole);
- }
- }
- }
- }
-
- /**
* Creates a matrix which polygon contains which polygon. A polygon
does not
* contain itself.
*
@@ -1649,6 +1709,7 @@
updateBounds(point);
}
+ @Override
public void addPoint(Coord point) {
super.addPoint(point);
updateBounds(point);
@@ -1749,14 +1810,7 @@
}
}
- public List<Long> getOriginalIds() {
- ArrayList<Long> idList = new
ArrayList<Long>(getOriginalWays().size());
- for (Way w : getOriginalWays()) {
- idList.add(w.getId());
- }
- return idList;
- }
-
+ @Override
public String toString() {
StringBuilder sb = new StringBuilder(200);
sb.append(getId());
@@ -1864,6 +1918,7 @@
return this.areas.size();
}
+ @Override
public int compareTo(CutPoint o) {
if (this == o) {
return 0;
@@ -1876,6 +1931,7 @@
return
(stopPoint-startPoint)-(o.stopPoint-o.startPoint);
}
+ @Override
public String toString() {
return axis +" "+getNumberOfAreas()+" "+startPoint+"
"+stopPoint+" "+getCutPoint();
}
@@ -1928,6 +1984,7 @@
this.axis = axis;
}
+ @Override
public int compare(Area o1, Area o2) {
if (o1 == o2) {
return 0;
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
