Attached patch should fix (all?) subdivision splitting problems.
Error like "Area too small to split at ..." cannot occur any more
because the way how subdivisions are split is changed.
I think it's still not the optimal way but there should be no loss in
highly densed areas any more.
This is a first patch not ready to commit because there are some
performance penalties which can be reduced. But I want you to test the
patch before optimization.
WanMil
Index: src/uk/me/parabola/mkgmap/build/MapArea.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapArea.java (revision 2028)
+++ src/uk/me/parabola/mkgmap/build/MapArea.java (working copy)
@@ -188,7 +188,7 @@
* @param area The bounds for this area.
* @param res The minimum resolution for this area.
*/
- private MapArea(Area area, int res) {
+ public MapArea(Area area, int res) {
bounds = area;
areaResolution = res;
addToBounds(area);
@@ -446,6 +446,18 @@
}
}
+
+ public void addElement(MapElement e) {
+ if (e instanceof MapShape) {
+ addShape((MapShape) e);
+ } else if (e instanceof MapLine) {
+ addLine((MapLine) e);
+ } else if (e instanceof MapPoint) {
+ addPoint((MapPoint) e);
+ } else {
+ log.error("Unknown MapElement type "+e.getType());
+ }
+ }
/**
* Add a single point to this area.
Index: src/uk/me/parabola/mkgmap/build/MapSplitter.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapSplitter.java (revision 2028)
+++ src/uk/me/parabola/mkgmap/build/MapSplitter.java (working copy)
@@ -17,12 +17,23 @@
package uk.me.parabola.mkgmap.build;
import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicInteger;
import uk.me.parabola.imgfmt.app.Area;
+import uk.me.parabola.imgfmt.app.Coord;
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.mkgmap.general.MapElement;
+import uk.me.parabola.mkgmap.general.MapShape;
/**
* The map must be split into subdivisions. To do this we start off with
@@ -98,7 +109,7 @@
// in them. For those that do, we further split them. This is done
// recursively until everything fits.
List<MapArea> alist = new ArrayList<MapArea>();
- addAreasToList(areas, alist, 0);
+ addAreasToList(Arrays.asList(areas), alist, 0);
MapArea[] results = new MapArea[alist.size()];
return alist.toArray(results);
@@ -113,12 +124,12 @@
* @param alist The list that will finally contain the complete list of
* map areas.
*/
- private void addAreasToList(MapArea[] areas, List<MapArea> alist, int depth) {
+ private void addAreasToList(List<MapArea> areas, List<MapArea> alist, int depth) {
int res = zoom.getResolution();
for (MapArea area : areas) {
Area bounds = area.getBounds();
- int[] sizes = area.getEstimatedSizes();
if(log.isInfoEnabled()) {
+ int[] sizes = area.getEstimatedSizes();
String padding = depth + " ";
log.info(padding.substring(0, (depth + 1) * 2) +
bounds.getWidth() + "x" + bounds.getHeight() +
@@ -128,26 +139,25 @@
", shapes = " + area.getNumShapes() + "/" + sizes[MapArea.SHAPE_KIND]);
}
- if (area.getNumLines() > MAX_NUM_LINES ||
- area.getNumPoints() > MAX_NUM_POINTS ||
- (sizes[MapArea.POINT_KIND] +
- sizes[MapArea.LINE_KIND] +
- sizes[MapArea.SHAPE_KIND]) > MAX_RGN_SIZE ||
- 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 (isSizeOk(area)==false) {
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);
+ List<MapArea> sublist = split(area, res);
+
addAreasToList(sublist, alist, depth + 1);
continue;
} else {
log.error("Area too small to split at " + area.getBounds().getCenter().toOSMURL() + " (reduce the density of points, length of lines, etc.)");
+ log.error("Bounds: "+area.getBounds().toGarmingString());
+ log.error("Fullbounds: "+area.getFullBounds().toGarmingString());
+ log.error("Points: "+area.getNumPoints());
+ log.error("Lines: "+area.getNumLines());
+ log.error("Shapes: "+area.getNumShapes());
+
+ for (MapShape shape : area.getShapes()) {
+ log.error("P: "+shape.getLocation());
+ }
}
}
@@ -158,6 +168,184 @@
alist.add(sublist[0]);
}
}
+
+
+ private boolean isSizeOk(MapArea area) {
+ int[] sizes = area.getEstimatedSizes();
+ boolean sizeExhausted = area.getNumLines() > MAX_NUM_LINES ||
+ area.getNumPoints() > MAX_NUM_POINTS ||
+ (sizes[MapArea.POINT_KIND] +
+ sizes[MapArea.LINE_KIND] +
+ sizes[MapArea.SHAPE_KIND]) > MAX_RGN_SIZE ||
+ 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;
+ return sizeExhausted==false;
+ }
+
+ private double getAreaFillLevel(MapArea area) {
+ int[] sizes = area.getEstimatedSizes();
+
+ Collection<Double> fracs = new ArrayList<Double>(6);
+
+ fracs.add( (double)area.getNumLines() / MAX_NUM_LINES);
+ fracs.add( (double)area.getNumPoints() / MAX_NUM_POINTS);
+ fracs.add( (double)(sizes[MapArea.POINT_KIND] +
+ sizes[MapArea.LINE_KIND] +
+ sizes[MapArea.SHAPE_KIND])/MAX_RGN_SIZE);
+ fracs.add( (double) sizes[MapArea.XT_POINT_KIND] / MAX_XT_POINTS_SIZE);
+ fracs.add( (double)sizes[MapArea.XT_LINE_KIND] / MAX_XT_LINES_SIZE);
+ fracs.add( (double)sizes[MapArea.XT_SHAPE_KIND] / MAX_XT_SHAPES_SIZE);
+
+ return Collections.max(fracs);
+ }
+
+ private enum Axis {
+ LAT, LON;
+
+ public int getValue(MapElement elem) {
+ return getValue(elem.getLocation());
+ }
+
+ public int getValue(Coord c) {
+ switch (this) {
+ case LAT:
+ return c.getLatitude();
+ case LON:
+ return c.getLongitude();
+ default:
+ throw new Error("Unknown axis type "+this);
+ }
+ }
+
+ /**
+ * Splits the area in two areas at the location of the given element.
+ * @param area the area to split
+ * @param splitPoint the split point
+ * @return a two dimensional array with the splitted areas
+ */
+ public List<Area> splitArea(Area area, int splitPoint) {
+ List<Area> splitted = new ArrayList<Area>(2);
+ switch (this) {
+ case LAT:
+ splitted.add( new Area(area.getMinLat(),area.getMinLong(),splitPoint,area.getMaxLong()));
+ splitted.add( new Area(splitPoint,area.getMinLong(),area.getMaxLat(),area.getMaxLong()));
+ break;
+ case LON:
+ splitted.add( new Area(area.getMinLat(),area.getMinLong(),area.getMaxLat(),splitPoint));
+ splitted.add( new Area(area.getMinLat(),splitPoint,area.getMaxLat(),area.getMaxLong()));
+ break;
+ }
+ return splitted;
+ }
+ }
+
+ // private final static AtomicInteger xsplitId = new AtomicInteger();
+
+ /**
+ * 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 resolution The resolution of the level.
+ * @return An array of the new MapArea's.
+ */
+ public List<MapArea> split(MapArea area, int resolution) {
+ // int splitId = xsplitId.incrementAndGet();
+
+ List<MapElement> elements = new ArrayList<MapElement>();
+ elements.addAll(area.getPoints());
+ elements.addAll(area.getLines());
+ elements.addAll(area.getShapes());
+
+ assert elements.size() > 2;
+
+ List<MapArea> mapAreas = new ArrayList<MapArea>();
+
+ Area bounds = area.getBounds();
+
+// String basename= GpxCreator.getGpxBaseName()+splitId+"_"+resolution+"/";
+// GpxCreator.createAreaGpx(basename+"bounds", bounds);
+
+ final Map<MapElement, Coord> locs = new HashMap<MapElement, Coord>();
+ for (MapElement el : elements) {
+ locs.put(el, el.getLocation());
+ }
+
+ Axis sortAxis = null;
+ while (elements.isEmpty() == false) {
+ final Axis axis;
+ if (bounds.getWidth() >= bounds.getHeight()) {
+ axis = Axis.LON;
+ } else {
+ axis = Axis.LAT;
+ }
+
+ if (axis != sortAxis) {
+ // need to resort the elements because the axis has changed
+ Comparator<MapElement> elementSort = new Comparator<MapElement>() {
+ public int compare(MapElement o1, MapElement o2) {
+ Coord c1 = locs.get(o1);
+ Coord c2 = locs.get(o2);
+ return axis.getValue(c1) - axis.getValue(c2);
+ }
+ };
+
+ Collections.sort(elements, elementSort);
+ sortAxis = axis;
+ }
+
+ MapArea testArea = new MapArea(bounds, resolution);
+ ListIterator<MapElement> remainElems = elements.listIterator();
+
+ List<MapElement> nextAreaElems = new ArrayList<MapElement>();
+ while (remainElems.hasNext()) {
+ MapElement elem = remainElems.next();
+
+ testArea.addElement(elem);
+ if (getAreaFillLevel(testArea) > 1.0d) {
+ // the area is full
+ assert nextAreaElems.isEmpty() == false;
+
+ // use the
+ int newBorder1 = axis.getValue(nextAreaElems.get(nextAreaElems.size()-1));
+ int newBorder2 = axis.getValue(elem);
+ int newBorder = (newBorder1+newBorder2)/2;
+ List<Area> splitAreas = axis.splitArea(bounds, newBorder);
+
+
+ Area newAreaBounds = splitAreas.get(0);
+ MapArea newArea = new MapArea(newAreaBounds, resolution);
+ for (MapElement mElem : nextAreaElems) {
+ newArea.addElement(mElem);
+ }
+ mapAreas.add(newArea);
+
+ bounds = splitAreas.get(1);
+ break;
+
+ } else {
+ nextAreaElems.add(elem);
+ remainElems.remove();
+ }
+ }
+
+ if (elements.isEmpty()) {
+ mapAreas.add(testArea);
+ }
+ }
+
+// int x = 0;
+// for (MapArea a : mapAreas) {
+// GpxCreator.createAreaGpx(basename+"b"+x, a.getBounds());
+// GpxCreator.createAreaGpx(basename+"f"+x, a.getFullBounds());
+// x++;
+// }
+
+ return mapAreas;
+ }
/**
* Split the area into portions that have the maximum size. There is a
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
