Re: [mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable
Essentially the best option for drawing Polygons would be to determine their resolution based on size. So make large forests appearing at lower resolutions than small forests (well I think we all know that best would be if resolution of any element were adapted to map density, but I think that is even more complicated). I don't think this would be an easy task. Depending on the area or country (e.g. France with the Corine land cover import) putting forests at low resolutions really slows down map panning. Yes, I know, DP works not perfect at the moment for poygons. I've spent some thoughts on it, how to improve the thing. Maybe the algorithm should not look at the distance of the points, but at the difference in area. So some small areas with sharp angles should be candidates for deleting. (The current algorithm will preserve them) Another idea comes together with the rounding to resolution: Maybe we should not round to the nearest point, but to the point which least changes the outline, i.e which do the smallest changes to the angle of the polygon. An easy compromise could be to put stronger douglas peucker filter on polygons than on roads (I currently use 5.4, because 10 seems to be too strong on roads). However for Polygons a value of 10 works pretty well. It would be great if there would be support for that At the moment there is a commandline switch (-simplify-lines=xxx) which allows you to set the dp error distance for each call. It should be doable with nearly no effort to introduce a second option for polygon settings. (I don't know if the douglas peucker filter is applied after or before the style-file, if before of course the above will not be easy). For your information: DP filter is applied after the style file. Its applied while building the img. It must be this late, because it has to filter each resolution with different settings. The lower resolutions are filtered stronger. The better mapped countries are getting, the more importance choosing the proper resolutions will have. The changes to the default style over the last weeks were already a good step forward, but outside of cities OSM rarely has more than 20-30% of ways and landuse covered (I dare people in future will not draw few big forests, but split up more and more detailed) so the solely based on tags approach will become more and more difficult... (well at least I hope the difference between countryside and cities will flatten out a bit). I see one big problem: DP is or will in near future be disabled for polygons because of multipolygon problem. (Suggested by Mark, if I recall correctly). The reason for it is, that the multipolygons get split up into smaller polygons. This seems neccessary because of limitations of the img file format. But if such splitted polygons gets simplified, the parallel edges may not be parallel any more, which leads to drawing errors. So what to do here? Regards, Johann ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable
On 07.01.2010 16:19, Johann Gail wrote: Essentially the best option for drawing Polygons would be to determine their resolution based on size. So make large forests appearing at lower resolutions than small forests (well I think we all know that best would be if resolution of any element were adapted to map density, but I think that is even more complicated). I don't think this would be an easy task. Depending on the area or country (e.g. France with the Corine land cover import) putting forests at low resolutions really slows down map panning. Yes, I know, DP works not perfect at the moment for poygons. I've spent some thoughts on it, how to improve the thing. Maybe the algorithm should not look at the distance of the points, but at the difference in area. So some small areas with sharp angles should be candidates for deleting. (The current algorithm will preserve them) Another idea comes together with the rounding to resolution: Maybe we should not round to the nearest point, but to the point which least changes the outline, i.e which do the smallest changes to the angle of the polygon. An easy compromise could be to put stronger douglas peucker filter on polygons than on roads (I currently use 5.4, because 10 seems to be too strong on roads). However for Polygons a value of 10 works pretty well. It would be great if there would be support for that At the moment there is a commandline switch (-simplify-lines=xxx) which allows you to set the dp error distance for each call. It should be doable with nearly no effort to introduce a second option for polygon settings. Would be interesting if one could achieve improvements. I would also still like a tad heavier progression on the dp error distance --- 19 and lower could for my taste be filtered stronger, while 24,22,21,20 seem to be allright to me (I don't use 23 because it seems not to get used on all devices/Mapsource). (I don't know if the douglas peucker filter is applied after or before the style-file, if before of course the above will not be easy). For your information: DP filter is applied after the style file. Its applied while building the img. It must be this late, because it has to filter each resolution with different settings. The lower resolutions are filtered stronger. The better mapped countries are getting, the more importance choosing the proper resolutions will have. The changes to the default style over the last weeks were already a good step forward, but outside of cities OSM rarely has more than 20-30% of ways and landuse covered (I dare people in future will not draw few big forests, but split up more and more detailed) so the solely based on tags approach will become more and more difficult... (well at least I hope the difference between countryside and cities will flatten out a bit). I see one big problem: DP is or will in near future be disabled for polygons because of multipolygon problem. (Suggested by Mark, if I recall correctly). The reason for it is, that the multipolygons get split up into smaller polygons. This seems neccessary because of limitations of the img file format. But if such splitted polygons gets simplified, the parallel edges may not be parallel any more, which leads to drawing errors. So what to do here? Well that would be a really big problem, or meaning that no polygons lower than resolution 20 at any cost. Already right now having forest and riverbanks as only polygons go down to 19 makes maps pretty slow. Also more and more buildings appear. It strikes me already to remove buidling=yes from my polygons file (even though only present at res=24) that maps get to slow (and significant size increase) because of all the buildings. I like to have buildings in the map in sparsely populated areas for orientation, even more if still lots of ways are missing, but inside cities actually not much need for building=yes to get better orientation. It is really bad that Garmin never foresaw the need for holes in polygons Regards, Johann ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Multiple .img files in one gmapsupp.img: Some will not show up
On 01/07/2010 06:09 PM, Simon Eugster wrote: MKGMAP (gmapsupp.img) --gmapsupp %s (with all .img files as argument) You have to tell mkgmap which img is which FID in this stage. The FID is not stored in the individual tiles, just in the TDB file and in the gmapsupp.img. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
[mkgmap-dev] [PATCH v1] Tag delete bug fix
Hi Steve,
I think I have found the problem in Tags.java that was causing the
assertion when I tried to delete multiple tags. I believe the root
cause was the fact that remove() would decrement size so it looked as
if there was space but it didn't actually remove the key (as the
comment there suggests that is not the place to do that). So later, when
trying to add another tag, it looked as if there was space (because
size had been decremented) but keyPos() returned null because all the
slots in the key array were full.
The attached patch fixes this issue by not decrementing size when a tag
is deleted (the key will get garbage collected in ensureSpace()
so that it will be removed when the arrays are grown) and size gets
adjusted (see below).
I also set size to 0 in ensureSpace() before copying the key/value
pairs into the new arrays because put() will increment size when
there isn't an existing value for that key (which there won't be when
the arrays are being grown because they are newly allocated).
Previously, when ensureSpace() copied the key/values into the new
arrays size would have been incremented from its current value so that
the arrays would look like they are almost full again straight away
which means that they would be doubled in size for every couple of tags
added (can that really be true?)
Anyway, please check the attached patch for sanity as I don't profess
to understand the tag stuff that well.
Cheers,
Mark
diff --git a/src/uk/me/parabola/mkgmap/reader/osm/Tags.java b/src/uk/me/parabola/mkgmap/reader/osm/Tags.java
index 96bf4e6..707f1ba 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/Tags.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/Tags.java
@@ -99,7 +99,7 @@ public class Tags implements IterableString {
ensureSpace();
Integer ind = keyPos(key);
if (ind == null)
- assert false;
+ assert false : keyPos( + key + ) returns null - size = + size + , capacity = + capacity;
keys[ind] = key;
String old = values[ind];
@@ -118,8 +118,6 @@ public class Tags implements IterableString {
// except when resizing.
String old = values[k];
values[k] = null;
- if (old != null)
-size--;
return old;
}
return null;
@@ -149,10 +147,12 @@ public class Tags implements IterableString {
keys = new String[ncap];
values = new String[ncap];
capacity = ncap;
+ size = 0;
for (int i = 0; i okey.length; i++) {
String k = okey[i];
-if (k != null)
- put(k, oval[i]);
+String v = oval[i];
+if (k != null v != null)
+ put(k, v);
}
}
assert size capacity;
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Multiple .img files in one gmapsupp.img: Some will not show up
I fear this did not solve the problem either. Here is what I tried: java -Xmx1500m -jar /data/gps/maps/mkgmap/dist/mkgmap.jar --gmapsupp --family-id=00010002 /data/gps/maps/new/osmData/austria/00010002.img --family-id=00010004 /data/gps/maps/new/osmData/austria/00010004.img --family-id=00010006 /data/gps/maps/new/osmData/austria/00010006.img --family-id=00010001 /data/gps/maps/new/osmData/austria/00010001.img --family-id=00010003 /data/gps/maps/new/osmData/austria/00010003.img --family-id=0001 /data/gps/maps/new/osmData/austria/0001.img --family-id=00010005 /data/gps/maps/new/osmData/austria/00010005.img [...] And still there are the (, , Jan 2010). And uncovered parts of the image. The file names are unique too, by the way. Something else that could have gone wrong? Simon Ralf Kleineisel wrote: On 01/07/2010 06:09 PM, Simon Eugster wrote: MKGMAP (gmapsupp.img) --gmapsupp %s (with all .img files as argument) You have to tell mkgmap which img is which FID in this stage. The FID is not stored in the individual tiles, just in the TDB file and in the gmapsupp.img. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Multiple .img files in one gmapsupp.img: Some will not show up
On 01/07/2010 08:46 PM, Simon Eugster wrote: I fear this did not solve the problem either. Here is what I tried: java -Xmx1500m -jar /data/gps/maps/mkgmap/dist/mkgmap.jar --gmapsupp --family-id=00010002 /data/gps/maps/new/osmData/austria/00010002.img --family-id=00010004 /data/gps/maps/new/osmData/austria/00010004.img --family-id=00010006 /data/gps/maps/new/osmData/austria/00010006.img --family-id=00010001 /data/gps/maps/new/osmData/austria/00010001.img --family-id=00010003 /data/gps/maps/new/osmData/austria/00010003.img --family-id=0001 /data/gps/maps/new/osmData/austria/0001.img --family-id=00010005 /data/gps/maps/new/osmData/austria/00010005.img [...] I've never seen such big numbers as FIDs, and never leading zeroes, but this may be by accident. Does anyone know the limit for FIDs? What does wgmaptool show in the info page for your gmapsupp.img (or run gmt.exe -i gmapsupp.img)? ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable
The Douglas Peucker Algorithm might not be the best way to tackle the problem of too small polygons. Right now polygons will be dropped if they have a maximum extension of less than one map unit at the current resolution. The code is in mkgmap/filters/SizeFilter.java if you want to try it, just set MIN_SIZE to a value greater than one should do it. The proper solution would be to merge polygons if they overlap at the current resolution. Otherwise we might get holes in forests if they are mapped in small pieces. But I have no idea how to implement that... Regards Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable
The proper solution would be to merge polygons if they overlap at the current resolution. Otherwise we might get holes in forests if they are mapped in small pieces. But I have no idea how to implement that... Which would be rather counterproductive to the PolygonSplitter code :-( The polygons gets split to not hit any limits. Seems, we need a complete new concept in handling polygons and multipolygons. Maybe the splitting should be done *after* the dp step. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable
On 07.01.2010 23:13, Thilo Hannemann wrote: The Douglas Peucker Algorithm might not be the best way to tackle the problem of too small polygons. Right now polygons will be dropped if they have a maximum extension of less than one map unit at the current resolution. The code is in mkgmap/filters/SizeFilter.java if you want to try it, just set MIN_SIZE to a value greater than one should do it. The proper solution would be to merge polygons if they overlap at the current resolution. Otherwise we might get holes in forests if they are mapped in small pieces. But I have no idea how to implement that... Regards Thilo Thanks for that tipp. Will try it out tomorrow (currently just pushing through map updates...). Setting this to 5 or 6 might be working well. It's too bad that the better people will map, the more complicated rendering becomes. ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable
Am 07.01.2010 um 23:22 schrieb Johann Gail: The proper solution would be to merge polygons if they overlap at the current resolution. Otherwise we might get holes in forests if they are mapped in small pieces. But I have no idea how to implement that... Which would be rather counterproductive to the PolygonSplitter code :-( The polygons gets split to not hit any limits. Not necessarily. With merging the polygons I meant to merge *what you actually see* on the map. That is also what makes it so hard, because the polygons will have no common points or even a common border, it just happens that they will overlap when displayed at a certain resolution. Seems, we need a complete new concept in handling polygons and multipolygons. Maybe we need to rasterize the OSM polygons to a bitmap and then create the Garmin polygons from that? Would be lots of work though (programming and computing/memory wise)... Regards Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Multiple .img files in one gmapsupp.img: Some will not show up
Ralf Kleineisel wrote: On 01/07/2010 08:46 PM, Simon Eugster wrote: I fear this did not solve the problem either. Here is what I tried: java -Xmx1500m -jar /data/gps/maps/mkgmap/dist/mkgmap.jar --gmapsupp --family-id=00010002 /data/gps/maps/new/osmData/austria/00010002.img --family-id=00010004 /data/gps/maps/new/osmData/austria/00010004.img --family-id=00010006 /data/gps/maps/new/osmData/austria/00010006.img --family-id=00010001 /data/gps/maps/new/osmData/austria/00010001.img --family-id=00010003 /data/gps/maps/new/osmData/austria/00010003.img --family-id=0001 /data/gps/maps/new/osmData/austria/0001.img --family-id=00010005 /data/gps/maps/new/osmData/austria/00010005.img [...] I've never seen such big numbers as FIDs, and never leading zeroes, but this may be by accident. Does anyone know the limit for FIDs? What does wgmaptool show in the info page for your gmapsupp.img (or run gmt.exe -i gmapsupp.img)? Eight digits? The overview map number has also 8. And defaults to 6324. gmt.exe output below. As it seems the family id is interpreted as an unsigned integer? Limited to 65 535. At least that's what it seems like when looking at the family ID which does not match anymore from 0007 on. ... indeed. Tested. 65535 is the upper bound. Leading zeros have no effect by the way. Just changed the program to use lower IDs (just numbered the files). Still the same problem. I just tried that (for the small Liechtenstein map): mkgmap --gmapsupp --mapname=1111 --description='Hello, I am a map' --family-name='famname' --family-id=552428 63240001.img And what I'm getting in the list is: * OSM Street Map, Area 63240001, Jan 2010 Whereas gmt shows: File: gmapsupp.img, length 73216 Header: 07.00.2010 23:15:51, DSKIMG, xor 00h Mapset: Hello, I am a map Map length s-f CPprio PID FID name MAKEGMAP MPS91 1 63240001 MPC 67328 3 25 1 28140 OSM street map Data MPS F: PID 1, FID 28140, famname V: OSM map set (0) Now _where_ exactly do I have to give the family name and the map name. ... ah, now I see. They have to be given when creating the .img file from the .osm.gz file because mkgmap does not modify this .img files anymore when generating the gmapsupp file. Just tried to re-generate Spain (which was missing completely). No success. There were some error messages (as usual) when generating the .img files, but this happens for other maps too. Or does this cause tiles to be discarded? SCHWERWIEGEND (Polyline): Problem writing line (class uk.me.parabola.imgfmt.app.trergn.Polyline) of type 0x1e containing 9 points and starting at http://www.openstreetmap.org/?lat=41.86583lon=-9.14028zoom=17 SCHWERWIEGEND (Polyline): Subdivision shift is 0 and its centre is at http://www.openstreetmap.org/?lat=42.69547lon=-9.18597zoom=17 SCHWERWIEGEND (Polyline): deltaLat = -38664 SCHWERWIEGEND (Polyline): Problem writing line (class uk.me.parabola.imgfmt.app.trergn.Polyline) of type 0x1e containing 2 points and starting at http://www.openstreetmap.org/?lat=43.77790lon=-6.89478zoom=17 SCHWERWIEGEND (Polyline): Subdivision shift is 0 and its centre is at http://www.openstreetmap.org/?lat=43.72988lon=-5.88635zoom=17 SCHWERWIEGEND (Polyline): deltaLong = -46996 Ah and yes. Spain alone works perfectly. There are about ten million more roads than when I build the Europe map with Spain (because then I'm only shown the basemap). I nearly missed the exact meaning of your first mail. Trying with equal FID for every country now. (gmt output also below) -- No. Still the same. Spain missing, Germany partially missing. I don't know what to do now. Any idea? Simon $ wine gmt.exe -i /data/gps/maps/new/gmapsupp.img gmt v0.4.8.2154 (C) AP fixme:msvcrt:MSVCRT_setlocale :Codepage only locale not implemented File: /data/gps/maps/new/gmapsupp.img, length 1154777088 Header: 07.00.2010 20:35:09, DSKIMG, xor 00h Mapset: OSM street map Map length s-f CPprio PID FID name MAKEGMAP MPS 7916 1 00010002 MPC 9456297 5 1252 25 1 10002 OSM street map 00010004 MPC 4245221 5 1252 25 1 10004 OSM street map 00010006 MPC 11182177 5 1252 25 1 10006 OSM street map 00010001 MPC 12149098 5 1252 25 1 10001 OSM street map 00010003 MPC 7411091 5 1252 25 1 10003 OSM street map 0001 MPC 17715152 5 1252 25 1 1 OSM street map 00010005 MPC 12342743 5 1252 25 1 10005 OSM street map 00020013 MPC 7791286 5 1252 25 1 20013 OSM street map 00020021 MPC 8977343 5 1252 25 1 20021 OSM
Re: [mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable
Thilo Hannemann schrieb: Am 07.01.2010 um 23:22 schrieb Johann Gail: The proper solution would be to merge polygons if they overlap at the current resolution. Otherwise we might get holes in forests if they are mapped in small pieces. But I have no idea how to implement that... Which would be rather counterproductive to the PolygonSplitter code :-( The polygons gets split to not hit any limits. Not necessarily. With merging the polygons I meant to merge *what you actually see* on the map. That is also what makes it so hard, because the polygons will have no common points or even a common border, it just happens that they will overlap when displayed at a certain resolution. Yes, but I assume the PolygonSplitter code is here, because the Polygons has been already to big for the garmin img fmt. And if we merge them afterwards, the polygons could (not must) become to big again. Yes, the algorithm has to merge some poygons with spaces between them not bigger than the current resolution. But maybe in this space could be some polygons of other type. So the final polygon has to be the sum/majority of all invisible small polygons. For example I think of a landscape covered mostly with forests/sees. Maybe 50% seas, 50% forests, all smaller than resolution. What should the final polygon show?? Would be fine if they would be merged, but at the moment I have really no idea what the result should be, much less an algorithm to it. Seems, we need a complete new concept in handling polygons and multipolygons. Maybe we need to rasterize the OSM polygons to a bitmap and then create the Garmin polygons from that? Would be lots of work though (programming and computing/memory wise)... I had exactly the same idea some minutes ago. But its inthinkable. The algorithm would be not that complicated, but the resources for it will be incredibly high. No way... It will be thinkable to calculate the bounding box of each polygon, round the coordinates to resolution and merge polygons, if the bounding box touches or overlap. But even this would nees some tricks with hashcodes or similar, as comparing millions of bounding boxes to each other could not be done in reasonable time. Regards, Johann ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable
At the moment there is a commandline switch (-reduce-point-density=xxx) which allows you to set the dp error distance for each call. It should be doable with nearly no effort to introduce a second option for polygon settings. Just added a patch with an additional option 'reduce-point-density-polygon=xxx', which allows to set different dp settings for polygons. This patch is for testing only, it is not be meant to be checked in. Index: src/uk/me/parabola/mkgmap/build/MapBuilder.java === --- src/uk/me/parabola/mkgmap/build/MapBuilder.java (Revision 1473) +++ src/uk/me/parabola/mkgmap/build/MapBuilder.java (Arbeitskopie) @@ -110,6 +110,7 @@ private String regionAbbr; private double reducePointError; + private double reducePointErrorPolygon; private boolean mergeLines; private int locationAutofillLevel; @@ -131,6 +132,9 @@ regionName = props.getProperty(region-name, null); regionAbbr = props.getProperty(region-abbr, null); reducePointError = props.getProperty(reduce-point-density, 2.6); + reducePointErrorPolygon = props.getProperty(reduce-point-density-polygon, -1); + if (reducePointErrorPolygon == -1) + reducePointErrorPolygon = reducePointError; mergeLines = props.containsKey(merge-lines); makePOIIndex = props.getProperty(make-poi-index, false); @@ -924,8 +928,8 @@ filters.addFilter(new SizeFilter()); //DouglasPeucker behaves at the moment not really optimal at low zooms, but acceptable. //Is there an similar algorithm for polygons? - if(reducePointError 0) -filters.addFilter(new DouglasPeuckerFilter(reducePointError)); + if(reducePointErrorPolygon 0) +filters.addFilter(new DouglasPeuckerFilter(reducePointErrorPolygon)); } filters.addFilter(new PolygonSplitterFilter()); filters.addFilter(new RemoveEmpty()); ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
[mkgmap-dev] Error in Polygon-Splitter
Maybe the splitting should be done *after* the dp step. Have just looked into the code. The splitting with PolygonSplitter *is done* after the dp step. So this is ok. But while looking at it I found a severe error in the splitter code. See attached picture. If the polygon gets split at 6, it will give two polygons. 1234561 and 678916 The first one fills additional area. The second one will be a real weird one. No idea how the garmin units will handle this. Maybe this error is the cause for the bad behaviour of the multipolygon code? There was some mention of code for splitting a polygon to only convex ones at this mailing list. Would this code be usable in this place too? Or does the error in future not occur any more, as the polygons are converted to convex polygons in an earlier stage? Regards, Johann inline: polygon.jpg___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
