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. 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 (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"). 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).
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
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
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
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.
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
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
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
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.
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
I just set it to 8 to see the effects. a) it also removes many road pieces on low resolutions - so there are pretty big holes in roads. b) it is much much faster both in Mapsource as on my vista hcx. So concluding from that little try, yes having some algorithm joings roads and polygons (and dropping very small polygons) would mean a huge speed increase (and joining should not care for "name" or "ref" on resolution 18 or below). Actually already setting MIN_SIZE to 2 makes a noticeable speed improvement and only a very few holes do appear. I will leave it at "2".
The problem with the roads is that the SizeFilter is called for lines as well as for polygons. But the call to the filter is in two different places in mkgmap/build/MapBuilder.java. So if you make the MIN_SIZE a parameter and use different values for lines and polygons you won't have any holes in the roads at all and can set MIN_SIZE to a bigger value for the polygons. Regards Thilo Am 08.01.2010 um 15:52 schrieb Felix Hartmann:
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...
I just set it to 8 to see the effects.
a) it also removes many road pieces on low resolutions - so there are pretty big holes in roads. b) it is much much faster both in Mapsource as on my vista hcx.
So concluding from that little try, yes having some algorithm joings roads and polygons (and dropping very small polygons) would mean a huge speed increase (and joining should not care for "name" or "ref" on resolution 18 or below). Actually already setting MIN_SIZE to 2 makes a noticeable speed improvement and only a very few holes do appear. I will leave it at "2".
Just created a patch for it. Thilo Hannemann schrieb:
The problem with the roads is that the SizeFilter is called for lines as well as for polygons. But the call to the filter is in two different places in mkgmap/build/MapBuilder.java. So if you make the MIN_SIZE a parameter and use different values for lines and polygons you won't have any holes in the roads at all and can set MIN_SIZE to a bigger value for the polygons.
Regards Thilo
Am 08.01.2010 um 15:52 schrieb Felix Hartmann:
That patch works pretty nice. I upped the value to 40 and that gave nice results when zoomed far out. Here is the settings that I would find optimal resolution 24 == 4 (I think 4 is anyhow the minimum because if less than 4 pixels than it ain't an area) resolution 23 == 6 ( resolution 23 is not used by all GPS devices if resolution 24 and 22 are present) resolution 22 == 6 resolution 21 == 20 resolution 20 == 40 resolution 19 == 80 resolution >18 == 120 The only problem of course appears when large areas are splitted up into tiny polygons, but I think this is not really solvable without the very difficult work of merging. On 08.01.2010 20:16, Johann Gail wrote:
Just created a patch for it.
Thilo Hannemann schrieb:
The problem with the roads is that the SizeFilter is called for lines as well as for polygons. But the call to the filter is in two different places in mkgmap/build/MapBuilder.java. So if you make the MIN_SIZE a parameter and use different values for lines and polygons you won't have any holes in the roads at all and can set MIN_SIZE to a bigger value for the polygons.
Regards Thilo
Am 08.01.2010 um 15:52 schrieb Felix Hartmann:
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Felix Hartmann schrieb:
That patch works pretty nice. I upped the value to 40 and that gave nice results when zoomed far out. Here is the settings that I would find optimal resolution 24 == 4 (I think 4 is anyhow the minimum because if less than 4 pixels than it ain't an area) resolution 23 == 6 ( resolution 23 is not used by all GPS devices if resolution 24 and 22 are present) resolution 22 == 6 resolution 21 == 20 resolution 20 == 40 resolution 19 == 80 resolution >18 == 120
Just to be sure there is no missunderstanding: You are not able to set minsizes for each resolution. You haven't set them, or have you? The SizeFilter itself should shift the minsize according to the resolution. I.e. if you init it with number 2 the following minsizes should be uesed: resolution 24 = 2 resolution 23 = 4 resolution 22 = 8 resolution 21 = 16 resolution 20 = 32 resolution 19 = 64 resolution 18 = 128 which matches roughly your demands.
I've tried the patch as well and it works nicely. Smaller maps, some map clutter removed and seems to be faster as well. Regards Thilo Am 08.01.2010 um 21:48 schrieb Johann Gail:
Felix Hartmann schrieb:
That patch works pretty nice. I upped the value to 40 and that gave nice results when zoomed far out. Here is the settings that I would find optimal resolution 24 == 4 (I think 4 is anyhow the minimum because if less than 4 pixels than it ain't an area) resolution 23 == 6 ( resolution 23 is not used by all GPS devices if resolution 24 and 22 are present) resolution 22 == 6 resolution 21 == 20 resolution 20 == 40 resolution 19 == 80 resolution >18 == 120
Just to be sure there is no missunderstanding: You are not able to set minsizes for each resolution. You haven't set them, or have you?
The SizeFilter itself should shift the minsize according to the resolution. I.e. if you init it with number 2 the following minsizes should be uesed:
resolution 24 = 2 resolution 23 = 4 resolution 22 = 8 resolution 21 = 16 resolution 20 = 32 resolution 19 = 64 resolution 18 = 128
which matches roughly your demands.
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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.
participants (3)
-
Felix Hartmann -
Johann Gail -
Thilo Hannemann