Patch V8 updated to r1404.
- do not merge lines at resolution 24, as the dp filter is disabled.
With this change there should be no longer routing problems.
-------------------------------------------------------------------
Patch V7 is now based on the R1041 (and the SizeFilter.patch)
- removing of the -- suppress-dead-end-nodes option, as it causes
problems with routing.
- code cleanup, introduction of new classes.
-------------------------------------------------------------------
Patch V4 now supports three options.
Its build on top of r972. With all three options used, it will reduce
the four bavaria tiles from 58MB to 46MB. Drawing at low zoom levels
gets speed up significantly at my etrex.
This will not be the last version of the patch. I'm working further on
it, but have no idea, how fast work will progress.
The options are as follows:
+--reduce-point-density=num
+ Simplifies the ways with the douglas peucker algorithm.
+ num is the maximal allowed error distance, by which the resulting
+ way may differ from the original one.
+ This distance gets shifted with lower zoom levels.
+ Recommended setting is 10, this should lead to only small differences
+ (Default is 2.6, which should lead to invisible changes)
+
+-- suppress-dead-end-nodes
+ Do not generate nodes at the end of an dead end way.
+ Decrease file size and should speed up routing slightly.
+ May possibly cause errors, but not seen any one at the moment.
+
+--merge-lines
+ Try to merge lines. This helps the simplify filter to straighten out
+ longer chunks at lower zoom levels. Decreases file size more.
+ Increases paint speed at low zoom levels
.
Index: src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
===================================================================
--- src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java (Revision 1404)
+++ src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java (Arbeitskopie)
@@ -55,6 +55,7 @@
import uk.me.parabola.mkgmap.reader.osm.Rule;
import uk.me.parabola.mkgmap.reader.osm.Style;
import uk.me.parabola.mkgmap.reader.osm.Way;
+import uk.me.parabola.util.EnhancedProperties;
import uk.me.parabola.mkgmap.reader.polish.PolishMapDataSource;
/**
@@ -143,7 +144,7 @@
}
};
- public StyledConverter(Style style, MapCollector collector, Properties props) {
+ public StyledConverter(Style style, MapCollector collector, EnhancedProperties props) {
this.collector = collector;
nameTagList = style.getNameTagList();
Index: src/uk/me/parabola/mkgmap/build/MapBuilder.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapBuilder.java (Revision 1404)
+++ src/uk/me/parabola/mkgmap/build/MapBuilder.java (Arbeitskopie)
@@ -57,6 +57,7 @@
import uk.me.parabola.mkgmap.filters.DouglasPeuckerFilter;
import uk.me.parabola.mkgmap.filters.FilterConfig;
import uk.me.parabola.mkgmap.filters.LineSplitterFilter;
+import uk.me.parabola.mkgmap.filters.LineMergeFilter;
import uk.me.parabola.mkgmap.filters.MapFilter;
import uk.me.parabola.mkgmap.filters.MapFilterChain;
import uk.me.parabola.mkgmap.filters.PolygonSplitterFilter;
@@ -107,6 +108,10 @@
private String countryAbbr = "ABC";
private String regionName;
private String regionAbbr;
+
+ private double reducePointError;
+ private boolean mergeLines;
+
private int locationAutofillLevel;
private boolean poiAddresses = true;
private int poiDisplayFlags;
@@ -126,6 +131,8 @@
countryAbbr = props.getProperty("country-abbr", countryAbbr);
regionName = props.getProperty("region-name", null);
regionAbbr = props.getProperty("region-abbr", null);
+ reducePointError = props.getProperty("reduce-point-density", 2.6);
+ mergeLines = props.containsKey("merge-lines");
makePOIIndex = props.getProperty("make-poi-index", false);
@@ -866,11 +873,19 @@
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 RoundCoordsFilter());
filters.addFilter(new SizeFilter());
- filters.addFilter(new DouglasPeuckerFilter(FILTER_DISTANCE));
+ filters.addFilter(new DouglasPeuckerFilter(reducePointError));
}
filters.addFilter(new LineSplitterFilter());
filters.addFilter(new RemoveEmpty());
@@ -909,7 +924,7 @@
filters.addFilter(new SizeFilter());
//DouglasPeucker behaves at the moment not really optimal at low zooms, but acceptable.
//Is there an similar algorithm for polygons?
- filters.addFilter(new DouglasPeuckerFilter(FILTER_DISTANCE));
+ filters.addFilter(new DouglasPeuckerFilter(reducePointError));
}
filters.addFilter(new PolygonSplitterFilter());
filters.addFilter(new RemoveEmpty());
Index: src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5MapDataSource.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5MapDataSource.java (Revision 1404)
+++ src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5MapDataSource.java (Arbeitskopie)
@@ -32,6 +32,7 @@
import uk.me.parabola.mkgmap.osmstyle.eval.SyntaxException;
import uk.me.parabola.mkgmap.reader.osm.OsmConverter;
import uk.me.parabola.mkgmap.reader.osm.Style;
+import uk.me.parabola.util.EnhancedProperties;
import org.xml.sax.SAXException;
@@ -104,7 +105,7 @@
*/
private OsmConverter createStyler() {
- Properties props = getConfig();
+ EnhancedProperties props = getConfig();
String loc = props.getProperty("style-file");
if (loc == null)
loc = props.getProperty("map-features");
Index: src/uk/me/parabola/mkgmap/filters/LineMergeFilter.java
===================================================================
--- src/uk/me/parabola/mkgmap/filters/LineMergeFilter.java (Revision 0)
+++ src/uk/me/parabola/mkgmap/filters/LineMergeFilter.java (Revision 0)
@@ -0,0 +1,110 @@
+package uk.me.parabola.mkgmap.filters;
+
+import java.util.List;
+import java.util.ArrayList;
+import uk.me.parabola.imgfmt.app.Coord;
+import uk.me.parabola.log.Logger;
+import uk.me.parabola.mkgmap.general.MapLine;
+import uk.me.parabola.util.MultiHashMap;
+
+
+
+public class LineMergeFilter{
+ private static final Logger log = Logger.getLogger(LineMergeFilter.class);
+
+ List<MapLine> linesMerged;
+ MultiHashMap<Coord, MapLine> startPoints = new MultiHashMap<Coord, MapLine>();
+ MultiHashMap<Coord, MapLine> endPoints = new MultiHashMap<Coord, MapLine>();
+
+ public LineMergeFilter() {}
+
+ private void addLine(MapLine line) {
+ linesMerged.add(line);
+ List<Coord> points = line.getPoints();
+ startPoints.add(points.get(0), line);
+ endPoints.add(points.get(points.size()-1), line);
+ }
+
+ private void mergeLines(MapLine line1, MapLine line2) {
+ // Removes the first line,
+ // Merges the points in the second one
+ List<Coord> points1 = line1.getPoints();
+ List<Coord> points2 = line2.getPoints();
+ startPoints.remove(points1.get(0), line1);
+ endPoints.remove(points1.get(points1.size()-1), line1);
+ startPoints.remove(points2.get(0), line2);
+ startPoints.add(points1.get(0), line2);
+ line2.insertPointsAtStart(points1);
+ linesMerged.remove(line1);
+ }
+
+ private void addPointsAtStart(MapLine line, List<Coord> additionalPoints) {
+ log.info("merged lines before " + line.getName());
+ List<Coord> points = line.getPoints();
+ startPoints.remove(points.get(0), line);
+ line.insertPointsAtStart(additionalPoints);
+ startPoints.add(points.get(0), line);
+ }
+
+ private void addPointsAtEnd(MapLine line, List<Coord> additionalPoints) {
+ log.info("merged lines after " + line.getName());
+ List<Coord> points = line.getPoints();
+ endPoints.remove(points.get(points.size()-1), line);
+ line.insertPointsAtEnd(additionalPoints);
+ endPoints.add(points.get(points.size()-1), line);
+ }
+
+ public List<MapLine> merge(List<MapLine> lines) {
+ linesMerged = new ArrayList<MapLine>(lines.size()); //better use LinkedList??
+ for (MapLine line : lines) {
+ boolean isMerged = false;
+ List<Coord> points = line.getPoints();
+ Coord start = points.get(0);
+ Coord end = points.get(points.size()-1);
+
+ // Search for start point in hashlist
+ // (can the end of current line connected to an existing line?)
+ for (MapLine line2 : startPoints.get(end)) {
+ if (line.isSimilar(line2)) {
+ addPointsAtStart(line2, points);
+ // Search for endpoint in hashlist
+ // (if the other end (=start of line =start of line2) could be connected to an existing line,
+ // both lines has to be merged and one of them dropped)
+ for (MapLine line1 : endPoints.get(start)) {
+ if (line2.isSimilar(line1)
+ && !line2.equals(line1)) // don't make a closed loop a double loop
+ {
+ mergeLines(line1, line2);
+ break;
+ }
+ }
+ isMerged = true;
+ break;
+ }
+ }
+ if (isMerged)
+ continue;
+
+ // Search for endpoint in hashlist
+ // (can the start of current line connected to an existing line?)
+ for (MapLine line2 : endPoints.get(start)) {
+ if (line.isSimilar(line2)) {
+ addPointsAtEnd(line2, points);
+ isMerged = true;
+ break;
+ }
+ }
+ if (isMerged)
+ continue;
+
+ // No matching, create a copy of line
+ MapLine l = line.copy();
+ List<Coord> p = new ArrayList<Coord>(line.getPoints()); //use better LinkedList for performance?
+ l.setPoints(p);
+ addLine(l);
+ }
+ return linesMerged;
+ }
+
+}
+
Index: src/uk/me/parabola/mkgmap/general/MapLine.java
===================================================================
--- src/uk/me/parabola/mkgmap/general/MapLine.java (Revision 1404)
+++ src/uk/me/parabola/mkgmap/general/MapLine.java (Arbeitskopie)
@@ -59,8 +59,13 @@
if (this.points != null)
log.warn("overwriting points");
assert points != null : "trying to set null points";
+ assert points.size() != 0 : "trying to set points with zero length";
this.points = points;
+ testForConsecutivePoints(points);
+ }
+
+ public void testForConsecutivePoints(List<Coord> points) {
Coord last = null;
for (Coord co : points) {
if (last != null && last.equals(co))
@@ -72,6 +77,18 @@
}
}
+ public void insertPointsAtStart(List<Coord> additionalPoints) {
+ testForConsecutivePoints(additionalPoints);
+ points.addAll(0, additionalPoints);
+ points.remove(additionalPoints.size()-1); //End node exists now twice
+ }
+
+ public void insertPointsAtEnd(List<Coord> additionalPoints) {
+ testForConsecutivePoints(additionalPoints);
+ points.remove(points.size()-1);
+ points.addAll(additionalPoints);
+ }
+
public boolean isDirection() {
return direction;
}
Index: src/uk/me/parabola/mkgmap/general/MapElement.java
===================================================================
--- src/uk/me/parabola/mkgmap/general/MapElement.java (Revision 1404)
+++ src/uk/me/parabola/mkgmap/general/MapElement.java (Arbeitskopie)
@@ -167,6 +167,24 @@
this.type = type;
}
+ public boolean isSimilar(MapElement other) {
+ if (this.minResolution != other.minResolution)
+ return false;
+ if (this.maxResolution != other.maxResolution)
+ return false;
+ if (this.type != other.type)
+ return false;
+
+ String thisName = getName();
+ String otherName = other.getName();
+
+ if (thisName == null && otherName == null)
+ return true;
+ if (thisName!=null && otherName!=null && thisName.equals(otherName))
+ return true;
+ return false;
+ }
+
public boolean hasExtendedType() {
return hasExtendedType(type);
}
Index: src/uk/me/parabola/util/MultiHashMap.java
===================================================================
--- src/uk/me/parabola/util/MultiHashMap.java (Revision 0)
+++ src/uk/me/parabola/util/MultiHashMap.java (Revision 0)
@@ -0,0 +1,59 @@
+package uk.me.parabola.util;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+
+
+public class MultiHashMap<K,V> extends HashMap<K,List<V>> {
+
+ /**
+ * the empty list to be returned when there is key without values.
+ */
+ private List<V> emptyList = Collections.unmodifiableList(new ArrayList<V>(0));
+
+ /**
+ * Returns the list of values associated with the given key.
+ *
+ * @param o the key to get the values for.
+ * @return a list of values for the given keys or the empty list of no such
+ * value exist.
+ */
+ public List<V> get(K key) {
+ List<V> result = super.get(key);
+ return result == null ? emptyList : result;
+ }
+
+
+ public V add(K key, V value )
+ {
+
+ List<V> values = super.get(key);
+ if (values == null ) {
+ values = new LinkedList<V>();
+ super.put( key, values );
+ }
+
+ boolean results = values.add(value);
+
+ return ( results ? value : null );
+ }
+
+ public V remove(K key, V value )
+ {
+
+ List<V> values = super.get(key);
+ if (values == null )
+ return null;
+
+ values.remove(value);
+
+ if (values.size() == 0)
+ super.remove(values);
+
+ return value;
+ }
+}
+
Index: resources/help/en/options
===================================================================
--- resources/help/en/options (Revision 1404)
+++ resources/help/en/options (Arbeitskopie)
@@ -156,8 +156,27 @@
number is 63240000.
+<<<<<<< .mine
+Optimization options:
+
+--reduce-point-density=num
+ Simplifies the ways with the douglas peucker algorithm.
+ num is the maximal allowed error distance, by which the resulting
+ way may differ from the original one.
+ This distance gets shifted with lower zoom levels.
+ Recommended setting is 10, this should lead to only small differences
+ (Default is 2.6, which should lead to invisible changes)
+
+--merge-lines
+ Try to merge lines. This helps the simplify filter to straighten out
+ longer chunks at lower zoom levels. Decreases file size more.
+ Increases paint speed at low zoom levels
+
Miscellaneous options:
--max-jobs[=number]
When number is specified, allow that number of maps to be
processed concurrently. If number is not specified, the limit
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
