[mkgmap-dev] Suggestion - Make Douglas Peucker Algorithm more Configurable

Thu Jan 7 15:37:04 GMT 2010


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
>
>
>