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

Thu Jan 7 23:24:25 GMT 2010

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