[PATCH] alpha patch for simplifying ways and reducing img size
Find attached an patch (usable on R915), which reduces the point density of ways and roads to reduce the filesize of the resulting img file. It does it by using the douglas peucker algorithm. With this algorithm it is possible to set a max error distance and the resulting line will have filtered out all points without any points outside this distance band. For an exact explanation consult wikipedia. I tried it with an error distance of 10m. Higher distances don't gain much more. The saving is in some areas with bad osm data (useless high point density) up to 25%. In general it saves only 5% in file size. Consider this patch as an alpha release, which should only show the possibilities. For the release it will need at least an option at the commandline for setting the error distance. Also I'm not sure, if the StyledConverter.java is the correct file for this patch. I've seen there is some filter infrastructure in the mkgmap project, but I've no idea how to use it.
Hi Johann,
Find attached an patch (usable on R915), which reduces the point density of ways and roads to reduce the filesize of the resulting img file. It does it by using the douglas peucker algorithm. With this algorithm it is possible to set a max error distance and the resulting line will have filtered out all points without any points outside this distance band. For an exact explanation consult wikipedia.
I tried it with an error distance of 10m. Higher distances don't gain much more. The saving is in some areas with bad osm data (useless high point density) up to 25%. In general it saves only 5% in file size.
Consider this patch as an alpha release, which should only show the possibilities. For the release it will need at least an option at the commandline for setting the error distance.
Also I'm not sure, if the StyledConverter.java is the correct file for this patch. I've seen there is some filter infrastructure in the mkgmap project, but I've no idea how to use it.
Personally, I would not want this feature enabled by default. Why not add an option that turns it on and also can be used to specify the error distance. e.g. --reduce-point-density to turn the feature on and --reduce-point-density=NUM to turn it on and specify the, non-default, error distance. The --frig-roundabouts option does a similar thing. Also, is it a feature that should be available for the mp input as well as the osm? Cheers, Mark
Hi, On Fri, Feb 20, 2009 at 2:07 PM, Mark Burton <markb@ordern.com> wrote:
Personally, I would not want this feature enabled by default. Why not add an option that turns it on and also can be used to specify the error distance. e.g. --reduce-point-density to turn the feature on and --reduce-point-density=NUM to turn it on and specify the, non-default, error distance. The --frig-roundabouts option does a similar thing.
Considering the quality of osm data it's good to be enabled by default, but bad for debuging. .mp files have it as parameter added in the last version. from the cgps change log: New parameter to define simplification level of Douglas-Peucker simplification alg. [IMG ID] .. SimplifyLevel=1 This allow to change simplification level of lines and polygons. Allowed values between 0.1 and 10 Would it make sense to do a simplification per level let's say 24 bits - 10m, 23 bits 20 meters, and so on ? -- have fun, alex
Hi,
On Fri, Feb 20, 2009 at 2:07 PM, Mark Burton <markb@ordern.com> wrote:
Personally, I would not want this feature enabled by default. Why not add an option that turns it on and also can be used to specify the error distance. e.g. --reduce-point-density to turn the feature on and --reduce-point-density=NUM to turn it on and specify the, non-default, error distance. The --frig-roundabouts option does a similar thing.
Considering the quality of osm data it's good to be enabled by default, but bad for debuging.
Well, I think you have to have a means of disabling it. Whether it is enabled by default or not doesn't worry me too much (however, I do think that by default, the map data should be frigged as little as possible).
.mp files have it as parameter added in the last version. from the cgps change log: New parameter to define simplification level of Douglas-Peucker simplification alg. [IMG ID] .. SimplifyLevel=1 This allow to change simplification level of lines and polygons. Allowed values between 0.1 and 10
Would it make sense to do a simplification per level let's say 24 bits - 10m, 23 bits 20 meters, and so on ?
As long as it can be adjusted from the options. Cheers, Mark
Well, I think you have to have a means of disabling it. Whether it is enabled by default or not doesn't worry me too much (however, I do think that by default, the map data should be frigged as little as possible).
Ok, in the attached patch I introduced a commandline option 'reduce-point-density=num', which enables my patch. num is the maximal allowed error in meters. Default is 0, meaning simplifying switched off. Still considering this patch as a alpha release.
Ok, here follows V3 of my patch. Needs some small code cleanup but works fine for now. I've now moved the code into the filter framework. First I've split up the SmoothingFilter into a SizeFilter and a SmothingFilter, as I consider the size filtering an task, which had nothing to do with the smoothing. Second I replaced the SmoothingFilter with the DouglasPeuckerFilter class. This does a much more convienient job at straightening out lines. For my test case it reduces the file size to 90% of the original one.
Well, I think you have to have a means of disabling it. Whether it is enabled by default or not doesn't worry me too much (however, I do think that by default, the map data should be frigged as little as possible).
The parameter is called --reduce-point-density=num. Without a given value it takes 2.6, which should lead only to invisible changes.
Would it make sense to do a simplification per level let's say 24 bits - 10m, 23 bits 20 meters, and so on ?
The allowed error distance gets shifted with the levels, so at lower zooms the filtering reduces more points. Problem at very low zoom levels is, that the MapLines becomes to short, soo a huge amount of short lines gets to be drawn. It would be very reasonable to merge the lines before straightening them out.
On Feb 27, 2009, at 3:43 PM, Johann Gail wrote:
Ok, here follows V3 of my patch. Needs some small code cleanup but works fine for now.
Are you still working on this patch? I've tried it out on a number of maps: I could get compression levels similar to what you describe (about a 10% reduction in size). I had also hoped that this would improve display performance of the maps, but I could not detect any noticeable change. On my eTrex when I zoom out to scales of 50 or 80 km, it can take a very long time for the device to draw the map. From my observation of the way the map is drawn, it seems like the highways are drawn segment by segment. As you have stated, a perhaps more effective approach would be first to join highway segments where possible (for example by merging bridges and tunnels, neither of which are displayed by the Garmin devices), and then to apply the Douglas-Peucker algorithm to these longer segments. Do you have any idea how this could be achieved? Cheers.
Are you still working on this patch?
Yes, but at the moment with low priority. The weather is to good, I prefer cycling.... Nevertheless find attached the latest revision of my patch. Based on R1001 of mkgmap.
I've tried it out on a number of maps: I could get compression levels similar to what you describe (about a 10% reduction in size). I had also hoped that this would improve display performance of the maps, but I could not detect any noticeable change.
Glad to hear someone uses my patch. For me it speeds up redrawing speed by factor 2 at low zoom levels (20 and 30km , 50km and lower shows basemap).
On my eTrex when I zoom out to scales of 50 or 80 km, it can take a very long time for the device to draw the map. From my observation of the way the map is drawn, it seems like the highways are drawn segment by segment.
Yes, I made the same observation. The highways gets drawn segment by segment. Therefore I introduced the switch --merge-lines, which should merge the segements.
As you have stated, a perhaps more effective approach would be first to join highway segments where possible (for example by merging bridges and tunnels, neither of which are displayed by the Garmin devices), and then to apply the Douglas-Peucker algorithm to these longer segments. Do you have any idea how this could be achieved?
Yes, use the switch --merge-lines :-) The line merging algorithm works in general, but could be improved. It connects all line endings, which have the same type and name. For efficiency reasons it is done by hashlists. I assume, there is some error in it, as there the resulting highways are sometimes split in segements, but the should be merged. What I'm thinking about at the moment: Each highway gets drawn double, as there is a line for each direction. It should be possible to merge these both lines into a single one, but I don't know an efficient algorithm to achieve this. Has anyone an idea for this?
On Mon, Apr 13, 2009 at 1:50 PM, Johann Gail <johann.gail@gmx.de> wrote:
Yes, but at the moment with low priority. The weather is to good, I prefer cycling....
Me too. :-)
Nevertheless find attached the latest revision of my patch. Based on R1001 of mkgmap.
Thanks. The --merge-lines options looks exactly like what I was looking for. Unfortunately, the patch you attached is not complete. The following files are missing: src/uk/me/parabola/mkgmap/filters/SizeFilter.java src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java src/uk/me/parabola/mkgmap/filters/SmoothingFilter.java I assume that you only did a diff on the SVN versioned files. Thus these unversioned files were not included. I took the missing files from your old v3 patch and merged them with your new patch (attached to this e-mail for anyone else who would like to try the patch). mgkmap now can compile with the new patch, but I obviously cannot confirm if the old files I added are obsolete. ;-) I would really appreciate it if you could send a complete version of your v4 patch, if you have changed the above three files since your v3 patch. Cheers.
On Mon, Apr 13, 2009 at 1:50 PM, Johann Gail <johann.gail@gmx.de> wrote:
On my eTrex when I zoom out to scales of 50 or 80 km, it can take a very long time for the device to draw the map. From my observation of the way the map is drawn, it seems like the highways are drawn segment by segment.
Yes, I made the same observation. The highways gets drawn segment by segment. Therefore I introduced the switch --merge-lines, which should merge the segements.
My initial observations are that with --merge-lines set, and simplification set to the default level, - map compilation takes significantly longer, and - display in my eTrex is significantly faster. In my opinion, it's worth the wait. :-) Of course, I did not have repeatable test cases to create empirical values for the drawing times: these initial observations are completely subjective. Cheers.
On Mon, Apr 13, 2009 at 1:50 PM, Johann Gail <johann.gail@gmx.de> wrote:
Yes, I made the same observation. The highways gets drawn segment by segment. Therefore I introduced the switch --merge-lines, which should merge the segements.
Although drawing performance was definitely improved, a lot of routing issues cropped up when I tried this in the field. - The routing issues seem similar to those which occurred before Mark Burton committed the MAX_POINTS_IN_WAY = 200 patch. Could it be that merging the highways pushes the number of nodes above this limit? - I also noticed frequent recalculations while driving. I have the sensitivity patch applied. Is it possible that the smoothing algorithm causes the ways to diverge enough from the actual route to trigger a recalculation? (I set the --reduce-point-density option to the default.) - There was also a lot of weirdness in roundabouts. I was often routed the wrong way, or back and forth on the roundabout. Perhaps the merging is sometimes overzealous? Would it be a good idea to exclude roundabouts from smoothing and merging? Cheers.
Sorry, at the moment it is absolutely not possible for me to contiue development of this patch. I'he seen Steve has checked in parts of it, but haven't tested so far. (By the way, why doesn't there appear any commit mails?) Some thoughts to the last posts:
Although drawing performance was definitely improved, a lot of routing issues cropped up when I tried this in the field.
Thank you for trying out and reporting the errors.
- The routing issues seem similar to those which occurred before Mark Burton committed the MAX_POINTS_IN_WAY = 200 patch. Could it be that merging the highways pushes the number of nodes above this limit?
Yes, could be the lines gets to long by merging. I for myself haven't seen any errors. In the file LineSplitterFilter.java there is a line private static final int MAX_POINTS_IN_LINE = 250; which cuts the lines after symplifiing again into smaller segments. (Line was existing before my modifications.) Maybe this value should be reduced to 200 too.
- I also noticed frequent recalculations while driving. I have the sensitivity patch applied. Is it possible that the smoothing algorithm causes the ways to diverge enough from the actual route to trigger a recalculation? (I set the --reduce-point-density option to the default.)
- There was also a lot of weirdness in roundabouts. I was often routed the wrong way, or back and forth on the roundabout. Perhaps the merging is sometimes overzealous? Would it be a good idea to exclude roundabouts from smoothing and merging?
Maybe we should introduce a small change to the filter. It should not touch any lines at zoom level 0, where routing takes place. This was the behaviour of the previous LineSmoothingFilter. This will loss some of the optimisations, but should avoid the routing problems.
Hi Johann I've finally tried the patch out and it makes the low zoom levels look much nicer than before. I will apply it in stages as there are a number of different changes in there. Starting with the filter itself. ..Steve
Hi Johann
I've finally tried the patch out and it makes the low zoom levels look much nicer than before.
I will apply it in stages as there are a number of different changes in there. Starting with the filter itself.
..Steve
Hi Steve, thank you for commiting this patch. In the last time I had not really much time for developing my patch. Today I have updated to the last revision and see some differences to my working copy. 1. In the R1041 the SizeFilter is not working. Originally this was done in SmoothingFilter. I have extracted the SizeFilter from the SmoothingFilter class. The inssertion in the filter chain is missing. Please use the attached patch to get it working and get the same behaviour as before. 2. The part for merging lines is not checked in. I will deliver a patch in near future based on the recent revision, as this improves display at low zoom a lot. 3. The part with the dead-end nodes seems to cause routing problems, so I will not continue it. Regards, Johann
Considering the quality of osm data it's good to be enabled by default, but bad for debuging. .mp files have it as parameter added in the last version. from the cgps change log: New parameter to define simplification level of Douglas-Peucker simplification alg. [IMG ID] .. SimplifyLevel=1 This allow to change simplification level of lines and polygons. Allowed values between 0.1 and 10
Would it make sense to do a simplification per level let's say 24 bits - 10m, 23 bits 20 meters, and so on ?
Yes, I find the idea a very good one. At the moment I dont see where to include it, but I will play around a little. Have not that much time at the moment, so be patient. I also will include an option to switch this feature on or off.
participants (5)
-
Alexander Atanasov -
Clinton Gladstone -
Johann Gail -
Mark Burton -
Steve Ratcliffe