The patch fixes a NullPointerException (thanks Felix!) which sometimes
happened with the first patch.
@Marko: I don't know any reason, why this multipolygon patch should
trigger your exception. The stacktrace shows that you use a modified
Main.java which seems to trigger the Exception.
WanMil
Index: src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(revision 1584)
+++ src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(working copy)
@@ -7,15 +7,19 @@
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
+import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
+import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
+import java.util.TreeSet;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.logging.Level;
@@ -623,15 +627,20 @@
||
hasPolygonTags(currentPolygon.polygon);
if (processPolygon) {
-
- List<Way> innerWays = new
ArrayList<Way>(holes.size());
+ 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);
- }
-
- List<Way> singularOuterPolygons =
cutOutInnerPolygons(
- currentPolygon.polygon, innerWays);
+ }
+ 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
@@ -673,14 +682,15 @@
runIntersectionCheck(unfinishedPolygons);
runWrongInnerPolygonCheck(unfinishedPolygons,
innerPolygons);
- // we have at least one ring that could not be processed
+ // we have at least one polygon that could not be
processed
// Probably we have intersecting or overlapping polygons
// one possible reason is if the relation overlaps the
tile
// bounds
// => issue a warning
List<JoinedWay> lostWays =
getWaysFromPolygonList(unfinishedPolygons);
for (JoinedWay w : lostWays) {
- log.warn("Polygon", w, "is not processed due to
an unknown reason.");
+ log.warn("Polygon", w.getId(),
+ "is not processed due to an unknown
reason.");
logWayURLs(Level.WARNING, "-", w);
}
}
@@ -688,8 +698,7 @@
cleanup();
}
-
- private void runIntersectionCheck(BitSet unfinishedRings) {
+ private void runIntersectionCheck(BitSet unfinishedPolys) {
if (intersectingPolygons.isEmpty()) {
// nothing to do
return;
@@ -700,7 +709,7 @@
boolean oneOufOfBbox = false;
for (JoinedWay polygon : intersectingPolygons) {
int pi = polygons.indexOf(polygon);
- unfinishedRings.clear(pi);
+ unfinishedPolys.clear(pi);
boolean outOfBbox = false;
for (Coord c : polygon.getPoints()) {
@@ -720,7 +729,7 @@
private void runWrongInnerPolygonCheck(BitSet unfinishedPolygons,
BitSet innerPolygons) {
- // find all unfinished inner rings that are not contained by any
+ // find all unfinished inner polygons that are not contained by
any
BitSet wrongInnerPolygons =
findOutmostPolygons(unfinishedPolygons, innerPolygons);
if (log.isDebugEnabled()) {
log.debug("unfinished", unfinishedPolygons);
@@ -766,6 +775,47 @@
polygons = null;
}
+ private CutPoint calcNextCutPoint(AreaCutData areaData) {
+ if (areaData.innerAreas == null ||
areaData.innerAreas.isEmpty()) {
+ return null;
+ }
+
+ if (areaData.innerAreas.size() == 1) {
+ // make it short if there is only one inner area
+ Rectangle outerBounds = areaData.outerArea.getBounds();
+ CoordinateAxis axis = (outerBounds.width <
outerBounds.height ? CoordinateAxis.LONGITUDE : CoordinateAxis.LATITUDE);
+ CutPoint oneCutPoint = new CutPoint(axis);
+ oneCutPoint.addArea(areaData.innerAreas.get(0));
+ return oneCutPoint;
+ }
+
+ ArrayList<Area> innerStart = new ArrayList<Area>(
+ areaData.innerAreas);
+
+ ArrayList<CutPoint> bestCutPoints = new
ArrayList<CutPoint>(CoordinateAxis.values().length);
+
+ for (CoordinateAxis axis : CoordinateAxis.values()) {
+ CutPoint bestCutPoint = new CutPoint(axis);
+ CutPoint currentCutPoint = new CutPoint(axis);
+
+ Collections.sort(innerStart, (axis ==
CoordinateAxis.LONGITUDE ? COMP_LONG_START: COMP_LAT_START));
+
+ Iterator<Area> startIter = innerStart.iterator();
+ while (startIter.hasNext()) {
+ Area nextStart = startIter.next();
+ currentCutPoint.addArea(nextStart);
+
+ if (currentCutPoint.compareTo(bestCutPoint) >
0) {
+ bestCutPoint =
currentCutPoint.duplicate();
+ }
+ }
+ bestCutPoints.add(bestCutPoint);
+ }
+
+ return Collections.max(bestCutPoints);
+
+ }
+
/**
* Cut out all inner polygons from the outer polygon. This will divide
the outer
* polygon in several polygons.
@@ -778,97 +828,154 @@
* polygons
*/
private List<Way> cutOutInnerPolygons(Way outerPolygon, List<Way>
innerPolygons) {
- // we use the java.awt.geom.Area class because it's a quick
- // implementation of what we need
+ if (innerPolygons.isEmpty()) {
+ return Collections.singletonList((Way)new
JoinedWay(outerPolygon));
+ }
+
+ // 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
- List<Area> outerAreas = new ArrayList<Area>();
-
+ Queue<AreaCutData> areasToCut = new LinkedList<AreaCutData>();
+ Collection<Area> finishedAreas = new
ArrayList<Area>(innerPolygons.size());
+
// 1st create an Area object of the outerPolygon and put it to
the list
- List<Area> oa = createAreas(outerPolygon);
-
+ List<Area> outerAreas = createAreas(outerPolygon);
+ // clip with bounding box
Area bboxArea = new Area(new Rectangle(bbox.getMinLong(), bbox
.getMinLat(), bbox.getMaxLong() - bbox.getMinLong(),
bbox.getMaxLat() - bbox.getMinLat()));
-
- for (Area outerArea : oa) {
- // clip all areas to the bounding box
+ for (Area outerArea : outerAreas) {
outerArea.intersect(bboxArea);
- outerAreas.add(outerArea);
}
- List<Area> innerAreas = new ArrayList<Area>();
+ // create the inner areas
+ List<Area> innerAreas = new
ArrayList<Area>(innerPolygons.size()+2);
for (Way innerPolygon : innerPolygons) {
innerAreas.addAll(createAreas(innerPolygon));
}
- // go through all innerPolygons (holes) and cut them from the
outerPolygon
- for (Area innerArea : innerAreas) {
-
- List<Area> outerAfterThisStep = new ArrayList<Area>();
+ // initialize the cut data queue
+ if (outerAreas.size() == 1) {
+ if (innerAreas.isEmpty()) {
+ // this is a multipolygon without any inner
areas
+ finishedAreas.add(outerAreas.get(0));
+ } else {
+ AreaCutData initialCutData = new AreaCutData();
+ initialCutData.outerArea = outerAreas.get(0);
+ initialCutData.innerAreas = innerAreas;
+ areasToCut.add(initialCutData);
+ }
+ } else {
for (Area outerArea : outerAreas) {
- // check if this outerArea is probably
intersected by the inner
- // area to save computation time in case it is
not
- if
(outerArea.getBounds().intersects(innerArea.getBounds()) == false) {
- outerAfterThisStep.add(outerArea);
- continue;
+ AreaCutData initialCutData = new AreaCutData();
+ initialCutData.outerArea = outerArea;
+ initialCutData.innerAreas = new
ArrayList<Area>(innerAreas
+ .size());
+ for (Area innerArea : innerAreas) {
+ if (outerArea.getBounds().intersects(
+ innerArea.getBounds())) {
+
initialCutData.innerAreas.add(innerArea);
+ }
}
-
- // cut the hole
- outerArea.subtract(innerArea);
- if (outerArea.isEmpty()) {
- // this outer area space can be
abandoned
- } else if (outerArea.isSingular()) {
- // the area is singular
- // => no further splits necessary
- outerAfterThisStep.add(outerArea);
+
+ if (initialCutData.innerAreas.isEmpty()) {
+ // this should not happen
+ // usually this will be the outer sea
polygon containing errors
+ finishedAreas.add(outerArea);
} else {
- // 1st cut in two halfs in the middle
of the inner area
+ areasToCut.add(initialCutData);
+ }
+ }
+ }
- // Cut the bounding box into two
rectangles
- Rectangle r1;
- Rectangle r2;
+ while (areasToCut.isEmpty() == false) {
+ AreaCutData areaCutData = areasToCut.poll();
+ CutPoint cutPoint = calcNextCutPoint(areaCutData);
+
+ if (cutPoint == null) {
+ finishedAreas.add(areaCutData.outerArea);
+ continue;
+ }
+
+ assert cutPoint.getNumberOfAreas() > 0 : "Number of cut
areas == 0 in mp "+getId();
+
+ // cut out the holes
+ for (Area cutArea : cutPoint.getAreas()) {
+ areaCutData.outerArea.subtract(cutArea);
+ }
+
+ if (areaCutData.outerArea.isEmpty()) {
+ // this outer area space can be abandoned
+ continue;
+ }
+
+ // the inner areas of the cut point have been processed
+ // they are no longer needed
+ areaCutData.innerAreas.removeAll(cutPoint.getAreas());
- // Get the bounds of this polygon
- Rectangle innerBounds =
innerArea.getBounds();
- Rectangle outerBounds =
outerArea.getBounds();
- if (outerBounds.width >
outerBounds.height) {
- int cutWidth = (innerBounds.x -
outerBounds.x)
- +
innerBounds.width / 2;
- r1 = new
Rectangle(outerBounds.x, outerBounds.y,
- cutWidth,
outerBounds.height);
- r2 = new
Rectangle(outerBounds.x + cutWidth,
- outerBounds.y,
outerBounds.width - cutWidth,
-
outerBounds.height);
- } else {
- int cutHeight = (innerBounds.y
- outerBounds.y)
- +
innerBounds.height / 2;
- r1 = new
Rectangle(outerBounds.x, outerBounds.y,
-
outerBounds.width, cutHeight);
- r2 = new
Rectangle(outerBounds.x, outerBounds.y
- + cutHeight,
outerBounds.width,
-
outerBounds.height - cutHeight);
- }
+ if (areaCutData.outerArea.isSingular()) {
+ // the area is singular
+ // => no further splits necessary
+ if (areaCutData.innerAreas.isEmpty()) {
+ // this area is finished and needs no
further cutting
+
finishedAreas.add(areaCutData.outerArea);
+ } else {
+ // readd this area to further processing
+ areasToCut.add(areaCutData);
+ }
+ } else {
+ // we need to cut the area into two halfs to
get singular areas
+ Rectangle r1 =
cutPoint.getCutRectangleForArea(areaCutData.outerArea, true);
+ Rectangle r2 =
cutPoint.getCutRectangleForArea(areaCutData.outerArea, false);
- // Now find the intersection of these
two boxes with the
- // original polygon. This will make two
new areas, and each
- // area will be one (or more) polygons.
- Area a1 = outerArea;
- Area a2 = (Area) a1.clone();
- a1.intersect(new Area(r1));
- a2.intersect(new Area(r2));
+ // Now find the intersection of these two boxes
with the
+ // original polygon. This will make two new
areas, and each
+ // area will be one (or more) polygons.
+ Area a1 = areaCutData.outerArea;
+ Area a2 = (Area) a1.clone();
+ a1.intersect(new Area(r1));
+ a2.intersect(new Area(r2));
-
outerAfterThisStep.addAll(areaToSingularAreas(a1));
-
outerAfterThisStep.addAll(areaToSingularAreas(a2));
+ if (areaCutData.innerAreas.isEmpty()) {
+
finishedAreas.addAll(areaToSingularAreas(a1));
+
finishedAreas.addAll(areaToSingularAreas(a2));
+ } else {
+ ArrayList<Area> cuttedAreas = new
ArrayList<Area>();
+
cuttedAreas.addAll(areaToSingularAreas(a1));
+
cuttedAreas.addAll(areaToSingularAreas(a2));
+
+ for (Area nextOuterArea : cuttedAreas) {
+ ArrayList<Area> nextInnerAreas
= null;
+ // go through all remaining
inner areas and check if they
+ // must be further processed
with the nextOuterArea
+ for (Area nonProcessedInner :
areaCutData.innerAreas) {
+ if
(nextOuterArea.intersects(nonProcessedInner.getBounds2D())) {
+ if
(nextInnerAreas == null) {
+
nextInnerAreas = new ArrayList<Area>();
+ }
+
nextInnerAreas.add(nonProcessedInner);
+ }
+ }
+
+ if (nextInnerAreas == null ||
nextInnerAreas.isEmpty()) {
+
finishedAreas.add(nextOuterArea);
+ } else {
+ AreaCutData outCutData
= new AreaCutData();
+ outCutData.outerArea =
nextOuterArea;
+ outCutData.innerAreas=
nextInnerAreas;
+
areasToCut.add(outCutData);
+ }
+ }
}
}
- outerAreas = outerAfterThisStep;
+
}
-
+
// convert the java.awt.geom.Area back to the mkgmap way
- List<Way> cutOuterPolygon = new
ArrayList<Way>(outerAreas.size());
- for (Area area : outerAreas) {
+ List<Way> cutOuterPolygon = new
ArrayList<Way>(finishedAreas.size());
+ for (Area area : finishedAreas) {
Way w = singularAreaToWay(area,
FakeIdGenerator.makeFakeId());
if (w != null) {
w.copyTags(outerPolygon);
@@ -978,7 +1085,7 @@
"intersects itself and the tile bounds.
Maybe the polygon is not completely contained in the tile.");
log.info("The polygon is composed of");
logWayURLs(Level.INFO, "-", w);
- }
+ }
}
return areaList;
}
@@ -1159,7 +1266,7 @@
}
/**
- * Checks if the polygon with polygonIndex1 contains the ring with
polygonIndex2.
+ * Checks if the polygon with polygonIndex1 contains the polygon with
polygonIndex2.
*
* @return true if polygon(polygonIndex1) contains
polygon(polygonIndex2)
*/
@@ -1205,16 +1312,16 @@
}
} else if (bbox.contains(px)) {
// we have to check if the point is on one line
of the polygon1
-
+
if (locatedOnLine(px, polygon1.getPoints()) ==
false) {
// there's one point that is not in
polygon1 but inside the
// bounding box => polygon1 does not
contain polygon2
allOnLine = false;
return false;
- }
+ }
}
}
-
+
if (allOnLine) {
onePointContained = false;
// all points of polygon2 lie on lines of polygon1
@@ -1253,7 +1360,7 @@
// no point of polygon2 is in polygon1 => polygon1 does
not contain polygon2
return false;
}
-
+
Iterator<Coord> it1 = polygon1.getPoints().iterator();
Coord p1_1 = it1.next();
Coord p1_2 = null;
@@ -1319,7 +1426,7 @@
boolean intersects = intersectionPossible
&& linesCutEachOther(p1_1, p1_2, p2_1,
p2_2);
-
+
if (intersects) {
if ((polygon1.isClosedArtificially() &&
it1.hasNext() == false)
||
(polygon2.isClosedArtificially() && it2.hasNext() == false)) {
@@ -1399,8 +1506,8 @@
p.getLongitude(), p.getLatitude());
if (dist <= OVERLAP_TOLERANCE_DISTANCE) {
- log.debug("Point", p, "is located on
line between", cp1, "and",
- cp2, ". Distance:", dist);
+ log.debug("Point", p, "is located on
line between", cp1,
+ "and", cp2, ". Distance:",
dist);
return true;
}
} finally {
@@ -1621,7 +1728,7 @@
}
}
}
-
+
public List<Long> getOriginalIds() {
ArrayList<Long> idList = new
ArrayList<Long>(getOriginalWays().size());
for (Way w : getOriginalWays()) {
@@ -1665,4 +1772,167 @@
this.polygon = polygon;
}
}
+
+ private static class AreaCutData {
+ Area outerArea;
+ List<Area> innerAreas;
+ }
+
+ private static class CutPoint implements Comparable<CutPoint>{
+ int startPoint = Integer.MAX_VALUE;
+ int stopPoint = Integer.MIN_VALUE;
+ TreeSet<Area> areas;
+ private final CoordinateAxis axis;
+
+ public CutPoint(CoordinateAxis axis) {
+ this.axis = axis;
+ this.areas = new TreeSet<Area>(
+ (axis == CoordinateAxis.LONGITUDE ?
COMP_LONG_STOP : COMP_LAT_STOP));
+ }
+
+ public CutPoint duplicate() {
+ CutPoint newCutPoint = new CutPoint(this.axis);
+ newCutPoint.areas.addAll(areas);
+ newCutPoint.startPoint = startPoint;
+ newCutPoint.stopPoint = stopPoint;
+ return newCutPoint;
+ }
+
+ public int getCutPoint() {
+ return startPoint + (stopPoint - startPoint) / 2;
+ }
+
+ public Rectangle getCutRectangleForArea(Area toCut, boolean
firstRect) {
+ Rectangle areaRect = toCut.getBounds();
+ if (axis == CoordinateAxis.LONGITUDE) {
+ int newWidth = getCutPoint()-areaRect.x;
+ if (firstRect) {
+ return new Rectangle(areaRect.x,
areaRect.y, newWidth, areaRect.height);
+ } else {
+ return new
Rectangle(areaRect.x+newWidth, areaRect.y, areaRect.width-newWidth,
areaRect.height);
+ }
+ } else {
+ int newHeight = getCutPoint()-areaRect.y;
+ if (firstRect) {
+ return new Rectangle(areaRect.x,
areaRect.y, areaRect.width, newHeight);
+ } else {
+ return new Rectangle(areaRect.x,
areaRect.y+newHeight, areaRect.width, areaRect.height-newHeight);
+ }
+ }
+ }
+
+ public Collection<Area> getAreas() {
+ return areas;
+ }
+
+ public void addArea(Area area) {
+ // remove all areas that do not overlap with the new
area
+ while (areas.isEmpty() == false
+ && axis.getStop(areas.first()) < axis
+ .getStart(area)) {
+ // remove the first area
+ areas.pollFirst();
+ }
+
+ areas.add(area);
+ startPoint = axis.getStart(Collections.max(areas,
+ (axis == CoordinateAxis.LONGITUDE ?
COMP_LONG_START
+ : COMP_LAT_START)));
+ stopPoint = axis.getStop(areas.first());
+ }
+
+ public int getNumberOfAreas() {
+ return this.areas.size();
+ }
+
+ @Override
+ public int compareTo(CutPoint o) {
+ if (this == o) {
+ return 0;
+ }
+ int ndiff = getNumberOfAreas()-o.getNumberOfAreas();
+ if (ndiff != 0) {
+ return ndiff;
+ }
+ // prefer the larger area that is splitted
+ return
(stopPoint-startPoint)-(o.stopPoint-o.startPoint);
+ }
+
+ @Override
+ public String toString() {
+ return axis +" "+getNumberOfAreas()+" "+startPoint+"
"+stopPoint+" "+getCutPoint();
+ }
+
+ }
+
+ private static enum CoordinateAxis {
+ LATITUDE(false), LONGITUDE(true);
+
+ private CoordinateAxis(boolean useX) {
+ this.useX = useX;
+ }
+
+ private final boolean useX;
+
+ public int getStart(Area area) {
+ return getStart(area.getBounds());
+ }
+
+ public int getStart(Rectangle rect) {
+ return (useX ? rect.x : rect.y);
+ }
+
+ public int getStop(Area area) {
+ return getStop(area.getBounds());
+ }
+
+ public int getStop(Rectangle rect) {
+ return (useX ? rect.x + rect.width : rect.y +
rect.height);
+ }
+
+ }
+
+ private static final AreaComparator COMP_LONG_START = new
AreaComparator(
+ true, CoordinateAxis.LONGITUDE);
+ private static final AreaComparator COMP_LONG_STOP = new AreaComparator(
+ false, CoordinateAxis.LONGITUDE);
+ private static final AreaComparator COMP_LAT_START = new AreaComparator(
+ true, CoordinateAxis.LATITUDE);
+ private static final AreaComparator COMP_LAT_STOP = new AreaComparator(
+ false, CoordinateAxis.LATITUDE);
+
+ private static class AreaComparator implements Comparator<Area> {
+
+ private final CoordinateAxis axis;
+ private final boolean startPoint;
+
+ public AreaComparator(boolean startPoint, CoordinateAxis axis) {
+ this.startPoint = startPoint;
+ this.axis = axis;
+ }
+
+ @Override
+ public int compare(Area o1, Area o2) {
+ if (o1 == o2) {
+ return 0;
+ }
+
+ if (startPoint) {
+ int cmp = axis.getStart(o1) - axis.getStart(o2);
+ if (cmp == 0) {
+ return axis.getStop(o1) -
axis.getStop(o2);
+ } else {
+ return cmp;
+ }
+ } else {
+ int cmp = axis.getStop(o1) - axis.getStop(o2);
+ if (cmp == 0) {
+ return axis.getStart(o1) -
axis.getStart(o2);
+ } else {
+ return cmp;
+ }
+ }
+ }
+
+ }
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
