However, how do you want to do the merging without loosing attributes
(i.e. roadname changes, bridge, etc..), I think this could only work
by running after the main processing, and merging everything identical
if possible.
Otherwise before merging there needs to be a check whether there is
not a rule in the style-file that would change either the name of the
road OR the type (0x??) of a road. If both not changed then merge it.
The trick would be to do the merging on the data just before it is
converted into the Garmin format, after the style files are applied.
Then you have the final settings of all attributes and the name and
can merge only those ways that are identical in that respect. This is
also the point when the filters get applied to the ways. The problem
here is that the filters see only each way in turn, so they can only
perform modifications on a single way. Unfortunately it is not that
easy to find a place in the source code where you could apply the
merging of ways, which is the reason why I haven't had a go at it yet.
Find attached an patch of my working copy. It is based mainly on my old
simplifyWays patch. Its diffed against the current R1102.
The main idea is to merge the lines directly before input them to the
filters.
It improves drawing speed on my etrex considerably on very low zooms.
I'm not sure, if it is the optimal place to do the merging, but it seems
to work.
Its not a clean patch for now, but the diff of my working copy.
Index: src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
===================================================================
--- src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java (Revision 1102)
+++ src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java (Arbeitskopie)
@@ -52,7 +52,9 @@
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;
+
/**
* Convert from OSM to the mkgmap intermediate format using a style.
* A style is a collection of files that describe the mappings to be used
@@ -130,7 +132,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 1102)
+++ src/uk/me/parabola/mkgmap/build/MapBuilder.java (Arbeitskopie)
@@ -55,6 +55,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;
@@ -103,6 +104,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;
@@ -120,6 +125,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");
if(props.getProperty("no-poi-address", null) != null)
poiAddresses = false;
@@ -819,10 +826,18 @@
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) {
+ LineMergeFilter merger = new LineMergeFilter();
+ lines = merger.merge(lines);
+ }
+
LayerFilterChain filters = new LayerFilterChain(config);
if (enableLineCleanFilters && (res < 24)) {
filters.addFilter(new SizeFilter());
- filters.addFilter(new DouglasPeuckerFilter(FILTER_DISTANCE));
+ filters.addFilter(new DouglasPeuckerFilter(reducePointError));
}
filters.addFilter(new LineSplitterFilter());
filters.addFilter(new RemoveEmpty());
@@ -860,7 +875,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 1102)
+++ 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;
+ }
+
+}
+
Eigenschaftsänderungen: src/uk/me/parabola/mkgmap/filters/LineMergeFilter.java
___________________________________________________________________
Hinzugefügt: svn:executable
+ *
Eigenschaftsänderungen: src/uk/me/parabola/mkgmap/filters/SizeFilter.java
___________________________________________________________________
Hinzugefügt: svn:executable
+ *
Index: src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java
===================================================================
--- src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java (Revision 1102)
+++ src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java (Arbeitskopie)
@@ -61,18 +61,11 @@
MapLine line = (MapLine) element;
List<Coord> points = line.getPoints();
- int n = points.size()-1;
// Create a new list to rewrite the points into. Don't alter the original one
- List<Coord> coords = new ArrayList<Coord>(n);
+ List<Coord> coords = new ArrayList<Coord>(points.size());
coords.addAll(points);
- // If the first point is identic with the last one (a polygon), drop it
- // Otherwise douglasPeucker will not work!
- while ((n > 0) && coords.get(0).equals(coords.get(n))) {
- coords.remove(n);
- n--;
- }
//#if (Node version)
//Dont touch Coords, which are nodes.
@@ -84,7 +77,7 @@
for(int i = endIndex-1; i > 0; i--) {
Coord p = coords.get(i);
//int highwayCount = p.getHighwayCount();
-
+
// If a node in the line use the douglas peucker algorithm for upper segment
// TODO: Should consider only nodes connected to roads visible at current resolution.
if (p instanceof CoordNode) {
@@ -129,16 +122,28 @@
Coord b = points.get(endIndex);
double ab = a.distance(b);
- // Find point with highest distance.
- for(int i = endIndex-1; i > startIndex; i--) {
- Coord p = points.get(i);
- double ap = p.distance(a);
- double bp = p.distance(b);
- double abpa = (ab+ap+bp)/2;
- double distance = 2 * Math.sqrt(abpa * (abpa-ab) * (abpa-ap) * (abpa-bp)) / ab;
- if (distance > maxDistance) {
- maxDistance = distance;
- maxIndex = i;
+ if (ab == 0) { // Start- and endpoint are the same
+ // Find point with highest distance to start- and endpoint
+ for (int i = endIndex-1; i > startIndex; i--) {
+ Coord p = points.get(i);
+ double distance = p.distance(a);
+ if (distance > maxDistance) {
+ maxDistance = distance;
+ maxIndex = i;
+ }
+ }
+ } else {
+ // Find point with highest distance to line between start- and endpoint by using herons formula.
+ for(int i = endIndex-1; i > startIndex; i--) {
+ Coord p = points.get(i);
+ double ap = p.distance(a);
+ double bp = p.distance(b);
+ double abpa = (ab+ap+bp)/2;
+ double distance = 2 * Math.sqrt(abpa * (abpa-ab) * (abpa-ap) * (abpa-bp)) / ab;
+ if (distance > maxDistance) {
+ maxDistance = distance;
+ maxIndex = i;
+ }
}
}
if (maxDistance > allowedError) {
@@ -148,6 +153,12 @@
}
else {
// All points in tolerance, delete all of them.
+
+ // Remove the endpoint if it is the same as the startpoint
+ if (ab == 0)
+ points.remove(endIndex);
+
+ // Remove the points in between
for(int i = endIndex-1; i > startIndex; i--) {
points.remove(i);
}
Eigenschaftsänderungen: src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java
___________________________________________________________________
Hinzugefügt: svn:executable
+ *
Index: src/uk/me/parabola/mkgmap/general/MapLine.java
===================================================================
--- src/uk/me/parabola/mkgmap/general/MapLine.java (Revision 1102)
+++ 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))
@@ -70,6 +75,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 1102)
+++ src/uk/me/parabola/mkgmap/general/MapElement.java (Arbeitskopie)
@@ -160,6 +160,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;
+ }
+
/**
* Get the 'location' of the element. This is the mid point of the bounding
* box for the element. For a point, this will be the coordinates of the
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;
+ }
+}
+
Eigenschaftsänderungen: src/uk/me/parabola/util/MultiHashMap.java
___________________________________________________________________
Hinzugefügt: svn:executable
+ *
Index: resources/styles/default/polygons
===================================================================
--- resources/styles/default/polygons (Revision 1102)
+++ resources/styles/default/polygons (Arbeitskopie)
@@ -27,6 +27,7 @@
landuse=quarry [0x0c resolution 18]
landuse=recreation_ground [0x19 resolution 18]
landuse=reservoir [0x3f resolution 18]
+landuse=residential [0x03 resolution 18]
landuse=retail [0x08 resolution 20]
landuse=village_green [0x17 resolution 20]
landuse=vineyard [0x4e resolution 20]
Index: resources/help/en/options
===================================================================
--- resources/help/en/options (Revision 1102)
+++ resources/help/en/options (Arbeitskopie)
@@ -107,6 +107,21 @@
tdb file. The default number is 63240000.
+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
+
Misc options:
--max-jobs[=number]
When number is specified, allow that number of maps to be
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
