The patch changes the way how subdivisions are splitted.
1.: The LineMergeFilter, the LineSplitterFilter and the
PolygonSplitterFilter runs now before subdivions are built. This avoids
the problem that single lines/polygons are bigger than allowed in one
subdivision.
ToDo: The filters parameters use very small values (e.g. 250 points for
lines) which is only needed after a subdivision has been built. So maybe
it is good to run these filters twice. First with subdivision limits
before creating subdivisions and second after splitting each subdivision
with lower RGN(?) limits.
2.: Subdivisions are no longer split in equal bounds sizes but into
rather equal item sizes.
ToDo: At the moment a too large subdivision is split into 4
subdivisions. This algorithm might be improved to compute it
dynamically. Also points, lines and shapes should have a different
weight in the split algorithm.
This patch is a very early patch but if fixes the "Area (xxx,yyy) to
(zzz,qqq) contains ... but can't be split further" messages.
At the moment I am thinking about how to continue:
Maybe it is reasonable to run an initial filter (filters that are not
resolution dependant) set just before starting the subdivision creation.
[This is what the patch already does.]
The result of this filter set will not be changed afterwards and is used
as input of each subdivision creation step.
For each resolution the subdivisions of the previous resolution are
copied but the contents are removed. Then the resolution dependant
filter sets are applied (DP filter, SizeFilter, etc.) and the results
are assigned to the subdivisions. As a last step too big subdivisions
are splitted. [This swaps the current processing.]
Possible problems:
A line l in resolution 15 is subdivision A.
l is splitted into 3 parts l1 to l3 in resolution 18. Is it necessary
that l1 to l3 are assigned to child subdivisions of A or is it possible
that e.g. l3 is assigned to a child B1 of subdivision B because the
splitted line l3 fits better to B1?
Are there any routing problems?
I have found the thread
http://www.mail-archive.com/[email protected]/msg07335.html
which indicates that my idea does not work.
WanMil
Index: src/uk/me/parabola/mkgmap/filters/PolygonSizeSplitterFilter.java
===================================================================
--- src/uk/me/parabola/mkgmap/filters/PolygonSizeSplitterFilter.java (revision 1805)
+++ src/uk/me/parabola/mkgmap/filters/PolygonSizeSplitterFilter.java (working copy)
@@ -97,7 +97,7 @@
if (shape.getType() == 0x4a)
return true;
Area bounds = shape.getBounds();
- return bounds.getMaxDimention() < maxSize
+ return bounds.getMaxDimension() < maxSize
&& bounds.getWidth() < 0x7fff
&& bounds.getHeight() < 0x7fff
;
Index: src/uk/me/parabola/mkgmap/filters/SizeFilter.java
===================================================================
--- src/uk/me/parabola/mkgmap/filters/SizeFilter.java (revision 1805)
+++ src/uk/me/parabola/mkgmap/filters/SizeFilter.java (working copy)
@@ -44,7 +44,7 @@
MapLine line = (MapLine) element;
// Drop things that are too small to get displayed
- if (line.getBounds().getMaxDimention() < minSize)
+ if (line.getBounds().getMaxDimension() < minSize)
return;
next.doFilter(line);
Index: src/uk/me/parabola/mkgmap/filters/LineSizeSplitterFilter.java
===================================================================
--- src/uk/me/parabola/mkgmap/filters/LineSizeSplitterFilter.java (revision 1805)
+++ src/uk/me/parabola/mkgmap/filters/LineSizeSplitterFilter.java (working copy)
@@ -68,14 +68,14 @@
MapLine line = (MapLine) element;
- if (line.getBounds().getMaxDimention() < maxSize) {
+ if (line.getBounds().getMaxDimension() < maxSize) {
next.doFilter(element);
return;
}
if(line instanceof MapRoad) {
MapRoad road = ((MapRoad)line);
- log.error("Way " + road.getRoadDef() + " has a max dimension of " + line.getBounds().getMaxDimention() + " and is about to be split (routing will be broken)");
+ log.error("Way " + road.getRoadDef() + " has a max dimension of " + line.getBounds().getMaxDimension() + " and is about to be split (routing will be broken)");
}
List<Coord> points = line.getPoints();
Index: src/uk/me/parabola/mkgmap/build/MapBuilder.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapBuilder.java (revision 1805)
+++ src/uk/me/parabola/mkgmap/build/MapBuilder.java (working copy)
@@ -22,6 +22,7 @@
import java.util.HashMap;
import java.util.List;
+import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.Exit;
import uk.me.parabola.imgfmt.app.Label;
@@ -524,6 +525,143 @@
}
}
+ private static class FilteredSource implements MapDataSource {
+
+ private final MapDataSource org;
+ private final List<MapLine> lines;
+ private final List<MapShape> shapes;
+
+ public FilteredSource(MapDataSource org) {
+ this.org = org;
+ this.lines = new ArrayList<MapLine>();
+ this.shapes = new ArrayList<MapShape>();
+ }
+
+ @Override
+ public Area getBounds() {
+ return org.getBounds();
+ }
+
+ @Override
+ public List<MapPoint> getPoints() {
+ return org.getPoints();
+ }
+
+ @Override
+ public List<MapLine> getLines() {
+ return lines;
+ }
+
+ public void addLine(MapLine line) {
+ lines.add(line);
+ }
+
+ @Override
+ public List<MapShape> getShapes() {
+ return shapes;
+ }
+
+ public void addShape(MapShape shape) {
+ shapes.add(shape);
+ }
+
+ @Override
+ public RoadNetwork getRoadNetwork() {
+ return org.getRoadNetwork();
+ }
+
+ @Override
+ public List<Overview> getOverviews() {
+ return org.getOverviews();
+ }
+
+// @Override
+// public void config(EnhancedProperties props) {
+// org.config(props);
+// }
+//
+// @Override
+// public boolean isFileSupported(String name) {
+// return org.isFileSupported(name);
+// }
+//
+// @Override
+// public void load(String name) throws FileNotFoundException,
+// FormatException {
+// org.load(name);
+// }
+//
+// @Override
+// public LevelInfo[] mapLevels() {
+// return org.mapLevels();
+// }
+//
+// @Override
+// public String[] copyrightMessages() {
+// return org.copyrightMessages();
+// }
+ }
+
+ private static class ElementPreAddFilter extends BaseFilter implements MapFilter {
+ private final FilteredSource source;
+
+ public ElementPreAddFilter(FilteredSource source) {
+ this.source= source;
+ }
+
+ public void doFilter(MapElement element, MapFilterChain next) {
+ if (element instanceof MapShape) {
+ source.addShape((MapShape) element);
+ } else if (element instanceof MapLine) {
+ source.addLine((MapLine) element);
+ } else {
+ log.error("Unsupported element type "+element.getClass());
+ }
+ }
+ }
+
+ private MapDataSource runPreFilters(MapDataSource src, Zoom zoom) {
+ // Run line filters
+
+ FilteredSource filteredSrc = new FilteredSource(src);
+
+ int res = zoom.getResolution();
+
+ FilterConfig config = new FilterConfig();
+ config.setResolution(res);
+
+ List<MapLine> lines = src.getLines();
+
+ if (mergeLines && res < 24) {
+ LineMergeFilter merger = new LineMergeFilter();
+ lines = merger.merge(lines);
+ }
+
+ LayerFilterChain lineFilters = new LayerFilterChain(config);
+ lineFilters.addFilter(new LineSplitterFilter());
+ lineFilters.addFilter(new RemoveEmpty());
+ lineFilters.addFilter(new ElementPreAddFilter(filteredSrc));
+ for (MapLine line : lines) {
+ lineFilters.startFilter(line);
+ }
+
+
+ LayerFilterChain shapeFilters = new LayerFilterChain(config);
+ shapeFilters.addFilter(new PolygonSplitterFilter());
+ shapeFilters.addFilter(new RemoveEmpty());
+ shapeFilters.addFilter(new ElementPreAddFilter(filteredSrc));
+ for (MapShape shape : src.getShapes()) {
+ shapeFilters.startFilter(shape);
+ }
+
+ log.info("After pre filtering at resolution",res);
+ log.info("Lines:",src.getLines().size(), filteredSrc.getLines().size());
+ log.info("Shapes:",src.getShapes().size(), filteredSrc.getShapes().size());
+
+ return filteredSrc;
+ }
+
+
/**
* Drive the map generation by stepping through the levels, generating the
* subdivisions for the level and filling in the map elements that should
@@ -542,15 +680,14 @@
LevelInfo levelInfo = levels[0];
// If there is already a top level zoom, then we shouldn't add our own
- Subdivision topdiv;
+ Zoom topZoom;
if (levelInfo.isTop()) {
// There is already a top level definition. So use the values from it and
// then remove it from the levels definition.
levels = Arrays.copyOfRange(levels, 1, levels.length);
- Zoom zoom = map.createZoom(levelInfo.getLevel(), levelInfo.getBits());
- topdiv = makeTopArea(src, map, zoom);
+ topZoom = map.createZoom(levelInfo.getLevel(), levelInfo.getBits());
} else {
// We have to automatically create the definition for the top zoom level.
int maxBits = getMaxBits(src);
@@ -560,12 +697,15 @@
maxBits = levelInfo.getBits() - 1;
// Create the empty top level
- Zoom zoom = map.createZoom(levelInfo.getLevel() + 1, maxBits);
- topdiv = makeTopArea(src, map, zoom);
+ topZoom = map.createZoom(levelInfo.getLevel() + 1, maxBits);
}
+ MapDataSource filteredSrc = runPreFilters(src, topZoom);
+
+ Subdivision topdiv = makeTopArea(filteredSrc, map, topZoom);
+
// We start with one map data source.
- List<SourceSubdiv> srcList = Collections.singletonList(new SourceSubdiv(src, topdiv));
+ List<SourceSubdiv> srcList = Collections.singletonList(new SourceSubdiv(filteredSrc, topdiv));
// Now the levels filled with features.
for (LevelInfo linfo : levels) {
@@ -875,14 +1015,6 @@
FilterConfig config = new FilterConfig();
config.setResolution(res);
-
- //TODO: Maybe this is the wrong place to do merging.
- // Maybe more efficient if merging before creating subdivisions.
- if (mergeLines && res < 24) {
- LineMergeFilter merger = new LineMergeFilter();
- lines = merger.merge(lines);
- }
-
LayerFilterChain filters = new LayerFilterChain(config);
if (enableLineCleanFilters && (res < 24)) {
filters.addFilter(new PreserveHorizontalAndVerticalLinesFilter());
@@ -932,7 +1064,6 @@
if(reducePointError > 0)
filters.addFilter(new DouglasPeuckerFilter(reducePointError));
}
- filters.addFilter(new PolygonSplitterFilter());
filters.addFilter(new RemoveEmpty());
filters.addFilter(new ShapeAddFilter(div, map));
@@ -969,7 +1100,7 @@
* whole map.
*/
private int getMaxBits(MapDataSource src) {
- int topshift = Integer.numberOfLeadingZeros(src.getBounds().getMaxDimention());
+ int topshift = Integer.numberOfLeadingZeros(src.getBounds().getMaxDimension());
int minShift = Math.max(CLEAR_TOP_BITS - topshift, 0);
return 24 - minShift;
}
Index: src/uk/me/parabola/mkgmap/build/MapArea.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapArea.java (revision 1805)
+++ src/uk/me/parabola/mkgmap/build/MapArea.java (working copy)
@@ -17,9 +17,12 @@
package uk.me.parabola.mkgmap.build;
import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.List;
import uk.me.parabola.imgfmt.app.Area;
+import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.trergn.Overview;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.filters.FilterConfig;
@@ -34,6 +37,7 @@
import uk.me.parabola.mkgmap.general.MapPoint;
import uk.me.parabola.mkgmap.general.MapShape;
import uk.me.parabola.mkgmap.general.RoadNetwork;
+import uk.me.parabola.util.GpxCreator;
/**
* A sub area of the map. We have to divide the map up into areas to meet the
@@ -194,21 +198,147 @@
addToBounds(area);
}
+
+ private final class LatitudeComparator implements Comparator<Coord> {
+
+ @Override
+ public int compare(Coord o1, Coord o2) {
+ if (o1 == o2) {
+ return 0;
+ }
+ if (o1.getLatitude() == o2.getLatitude()) {
+ return o1.getLongitude() - o2.getLongitude();
+ } else {
+ return o1.getLatitude() - o2.getLatitude();
+ }
+ }
+
+ }
+
+ public MapArea[] splitDynamically(int nLong, int nLat, int resolution) {
+ log.info("Split dynamically",nLong,nLat,resolution);
+
+ List<Coord> coordList = new ArrayList<Coord>(points.size()+lines.size()+shapes.size());
+
+ for (MapPoint p : this.points) {
+ coordList.add(p.getLocation());
+ }
+
+ for (MapLine l : this.lines) {
+ // Drop any zero sized lines.
+ if (l.getBounds().getMaxDimension() <= 0)
+ continue;
+
+ coordList.add(l.getLocation());
+ }
+
+ for (MapShape e : this.shapes) {
+ coordList.add(e.getLocation());
+ }
+
+ if (coordList.size() < nLong) {
+ log.info("Cannot split into",nLong,"longitude parts because there is only",coordList.size(),"element");
+ nLong = coordList.size();
+ }
+ if (coordList.size() < nLat) {
+ log.info("Cannot split into",nLat,"latitude parts because there is only",coordList.size(),"element");
+ nLat = coordList.size();
+ }
+
+ // sort it in longitude order - this is the sort order of the Coord class
+ Collections.sort(coordList);
+ log.info("Sorted long list:", coordList);
+ ArrayList<Integer> longSplitPoints = new ArrayList<Integer>(nLong);
+ for (int n = 0; n < nLong; n++) {
+ int pos = (int)((double)(n+1)/nLong*coordList.size())-1;
+ log.info("n",n,"nLong",nLong,"size",coordList.size(),"pos",pos);
+ longSplitPoints.add(coordList.get(pos).getLongitude());
+ }
+ log.info("Split long points:", longSplitPoints);
+
+ // sort in latitude order
+ Collections.sort(coordList, new LatitudeComparator());
+ log.info("Sorted lat list:", coordList);
+ ArrayList<Integer> latSplitPoints = new ArrayList<Integer>(nLat);
+ for (int n = 0; n < nLat; n++) {
+ int pos = (int)((double)(n+1)/nLat*coordList.size())-1;
+ log.info("n",n,"nLat",nLat,"size",coordList.size(),"pos",pos);
+ latSplitPoints.add(coordList.get(pos).getLatitude());
+ }
+ log.info("Split lat points:", latSplitPoints);
+
+ MapArea[] areas = new MapArea[nLat*nLong];
+ int iArea = 0;
+ int latStart = minLat;
+ for (Integer lat : latSplitPoints) {
+ int longStart = minLon;
+ for (Integer lon : longSplitPoints) {
+ areas[iArea] = new MapArea(new Area(latStart,
+ longStart, lat, lon), resolution);
+ iArea++;
+ longStart = lon;
+ }
+ latStart = lat;
+ }
+
+ // Now sprinkle each map element into the correct map area.
+ for (MapPoint p : this.points) {
+ int pLat = Collections.binarySearch(latSplitPoints, p.getLocation().getLatitude());
+ int pLong = Collections.binarySearch(longSplitPoints, p.getLocation().getLongitude());
+ if (pLat < 0) {
+ pLat = (pLat+1)*-1;
+ }
+ if (pLong < 0) {
+ pLong = (pLong+1)*-1;
+ }
+ areas[pLat*nLong+pLong].addPoint(p);
+ }
+
+ for (MapLine l : this.lines) {
+ // Drop any zero sized lines.
+ if (l.getBounds().getMaxDimension() <= 0)
+ continue;
+ int pLat = Collections.binarySearch(latSplitPoints, l.getLocation().getLatitude());
+ int pLong = Collections.binarySearch(longSplitPoints, l.getLocation().getLongitude());
+ if (pLat < 0) {
+ pLat = (pLat+1)*-1;
+ }
+ if (pLong < 0) {
+ pLong = (pLong+1)*-1;
+ }
+ areas[pLat*nLong+pLong].addLine(l);
+ }
+
+ for (MapShape e : this.shapes) {
+ int pLat = Collections.binarySearch(latSplitPoints, e.getLocation().getLatitude());
+ int pLong = Collections.binarySearch(longSplitPoints, e.getLocation().getLongitude());
+ if (pLat < 0) {
+ pLat = (pLat+1)*-1;
+ }
+ if (pLong < 0) {
+ pLong = (pLong+1)*-1;
+ }
+ areas[pLat*nLong+pLong].addShape(e);
+ }
+
+ return areas;
+ }
+
/**
* Split this area into several pieces. All the map elements are reallocated
* to the appropriate subarea. Usually this instance would now be thrown
* away and the new sub areas used instead.
*
- * @param nx The number of pieces in the x (longitude) direction.
- * @param ny The number of pieces in the y direction.
+ * @param nLong The number of pieces in the x (longitude) direction.
+ * @param nLat The number of pieces in the y direction.
* @param resolution The resolution of the level.
* @return An array of the new MapArea's.
*/
- public MapArea[] split(int nx, int ny, int resolution) {
- Area[] areas = bounds.split(nx, ny);
- MapArea[] mapAreas = new MapArea[nx * ny];
- log.info("Splitting area " + bounds + " into " + nx + "x" + ny + " pieces at resolution " + resolution);
- for (int i = 0; i < nx * ny; i++) {
+ public MapArea[] split(int nLong, int nLat, int resolution) {
+ Area[] areas = bounds.split(nLong, nLat);
+ MapArea[] mapAreas = new MapArea[nLong * nLat];
+ log.info("Splitting area", bounds, "into",nLong + "x" + nLat , "pieces at resolution", resolution);
+ for (int i = 0; i < nLong * nLat; i++) {
mapAreas[i] = new MapArea(areas[i], resolution);
if (log.isDebugEnabled())
log.debug("area before", mapAreas[i].getBounds());
@@ -221,21 +351,21 @@
// Now sprinkle each map element into the correct map area.
for (MapPoint p : this.points) {
- MapArea area1 = pickArea(mapAreas, p, xbase, ybase, nx, ny, dx, dy);
+ MapArea area1 = pickArea(mapAreas, p, xbase, ybase, nLong, nLat, dx, dy);
area1.addPoint(p);
}
for (MapLine l : this.lines) {
// Drop any zero sized lines.
- if (l.getBounds().getMaxDimention() <= 0)
+ if (l.getBounds().getMaxDimension() <= 0)
continue;
- MapArea area1 = pickArea(mapAreas, l, xbase, ybase, nx, ny, dx, dy);
+ MapArea area1 = pickArea(mapAreas, l, xbase, ybase, nLong, nLat, dx, dy);
area1.addLine(l);
}
for (MapShape e : this.shapes) {
- MapArea area1 = pickArea(mapAreas, e, xbase, ybase, nx, ny, dx, dy);
+ MapArea area1 = pickArea(mapAreas, e, xbase, ybase, nLong, nLat, dx, dy);
area1.addShape(e);
}
@@ -469,6 +599,9 @@
addSize(l, l.hasExtendedType()? XT_LINE_KIND : LINE_KIND);
}
+
+ private final Coord xCoord = new Coord(2714271,1029713);
+ private int xs = 0;
/**
* Add a single shape to this map area.
*
@@ -478,6 +611,12 @@
shapes.add(s);
addToBounds(s.getBounds());
addSize(s, s.hasExtendedType()? XT_SHAPE_KIND : SHAPE_KIND);
+
+ if (s.getLocation().equals(xCoord)) {
+ log.error("Shape "+s);
+ GpxCreator.createGpx(GpxCreator.getGpxBaseName()+(++xs), s.getPoints());
+ }
+
}
/**
Index: src/uk/me/parabola/mkgmap/build/MapSplitter.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapSplitter.java (revision 1805)
+++ src/uk/me/parabola/mkgmap/build/MapSplitter.java (working copy)
@@ -23,6 +23,7 @@
import uk.me.parabola.imgfmt.app.trergn.Zoom;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.general.MapDataSource;
+import uk.me.parabola.util.GpxCreator;
/**
* The map must be split into subdivisions. To do this we start off with
@@ -104,6 +105,8 @@
return alist.toArray(results);
}
+ private static int mi = 0;
+
/**
* Adds map areas to a list. If an area has too many features, then it
* is split into 4 and this routine is called recursively to add the new
@@ -119,13 +122,18 @@
Area bounds = area.getBounds();
int[] sizes = area.getEstimatedSizes();
if(log.isInfoEnabled()) {
- String padding = depth + " ";
+ String padding = depth + " ";
log.info(padding.substring(0, (depth + 1) * 2) +
bounds.getWidth() + "x" + bounds.getHeight() +
", res = " + res +
", points = " + area.getNumPoints() + "/" + sizes[MapArea.POINT_KIND] +
", lines = " + area.getNumLines() + "/" + sizes[MapArea.LINE_KIND] +
- ", shapes = " + area.getNumShapes() + "/" + sizes[MapArea.SHAPE_KIND]);
+ ", shapes = " + area.getNumShapes() + "/" + sizes[MapArea.SHAPE_KIND]+
+ ", xtpoint = " + sizes[MapArea.XT_POINT_KIND]+
+ ", xtlines = " + sizes[MapArea.XT_LINE_KIND]+
+ ", xtshapes = " + sizes[MapArea.XT_SHAPE_KIND]
+
+ );
}
if (area.getNumLines() > MAX_NUM_LINES ||
@@ -136,22 +144,24 @@
sizes[MapArea.XT_POINT_KIND] > MAX_XT_POINTS_SIZE ||
sizes[MapArea.XT_LINE_KIND] > MAX_XT_LINES_SIZE ||
sizes[MapArea.XT_SHAPE_KIND] > MAX_XT_SHAPES_SIZE) {
- if (area.getBounds().getMaxDimention() > 10) {
+ if (area.getBounds().getMaxDimension() > 10) {
if (log.isDebugEnabled())
log.debug("splitting area", area);
MapArea[] sublist;
- if(bounds.getWidth() > bounds.getHeight())
- sublist = area.split(2, 1, res);
- else
- sublist = area.split(1, 2, res);
+// if(bounds.getWidth() > bounds.getHeight())
+// sublist = area.splitDynamically(2, 1, res);
+// else
+ sublist = area.splitDynamically(2, 2, res);
addAreasToList(sublist, alist, depth + 1);
continue;
} else {
+ String base = GpxCreator.getGpxBaseName();
+ GpxCreator.createAreaGpx(base+(++mi), area.getBounds());
log.error("Area too small to split at " + area.getBounds().getCenter().toOSMURL() + " (reduce the density of points, length of lines, etc.)");
}
}
- log.debug("adding area unsplit", ",has points" + area.hasPoints());
+ log.debug("adding area unsplit, has points", area.hasPoints());
MapArea[] sublist = area.split(1, 1, res);
assert sublist.length == 1: sublist.length;
Index: src/uk/me/parabola/imgfmt/app/Area.java
===================================================================
--- src/uk/me/parabola/imgfmt/app/Area.java (revision 1809)
+++ src/uk/me/parabola/imgfmt/app/Area.java (working copy)
@@ -148,7 +148,7 @@
*
* @return The largest dimension in map units.
*/
- public int getMaxDimention() {
+ public int getMaxDimension() {
return Math.max(getWidth(), getHeight());
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
