[mkgmap-dev] [mp: PATCH] Multipolygon handling - decomposed polygons

Sat Jan 9 14:38:29 GMT 2010

>>> Another idea (don't know if this is possible):
>>>
>>> You have a big multipolygon forest. You could duplicate it. One copy
>>> without small inner polygons for the low resolutions. Another copy with
>>> the inner polygons which gets splitted for the higher resolutions. The
>>> copies could be marked with some mkgmap internal tag and used later.
>>>
>>>
>>>       
>> May I propose to move the whole multipolygon handling to the filter chain?
>> Then there is _no need_ for additional tags and duplicated polygons and
>> possible remerging of them. The filter chain is run for each resolution
>> level. With each run the poylgons could be handled accordingly.
>>
>> I don't think, your ideas are wrong. I appreciate your work. But I think
>> its made more complicated than actually needed.
>>
>>     
>
> Interesting idea!
>
> I am not very deep in the filter things, so please let me know if I am 
> on the complete wrong way.
> Some thoughts about moving mulitpolygon handling to the filter chain:
>
> * Computation time for multipolygon handling will be multiplied by the 
> number of resolutions. Probably this is ok as the current implementation 
> seems to be quite quick.
>
>   
This is true. So maybe you should only move the splitting task to the 
filter chain and not the multipolygon handling. This would however mean 
that the multipolygon handling is done for all levels and it would not 
be possible to take at different levels the polygon without holes.
> * At which point should the multipolygon filter run? This might be a 
> problem.
> Example:
> 1st - before the SizeFilter: As before the mp code splits large polygons 
> to smaller pieces that might be removed by size filter (or the dp filter?)
>   
I dont think the dp filter does remove anything as whole. It removes 
single points from the polygon thereby make nearly straight lines 
exactly straight.
> 2nd - after the SizeFilter: The size filter removes small lines(?) and 
> polygons that otherwise would be composed to larger polygons by the mp code.
>   
For your information:
There are two diferent filter chains. One for lines (ways, etc. ) and 
one for polygons. Both of them uses instances of SizeFilter, 
PolygonSplitter, etc. with different settings. So the filter chain for 
polygons will never remove small lines.

What do you mean by mo code composign larger polygons?
As far as I understand the thing, it combines an outer poylgon with an 
inner polygon to a poygon with an hole. But by definition the inner 
polygon has to be always smaller than the outer polygon. (BTW: What 
happens, if this is not the case, caused by wrong osm data??)

So what will happen?
If the inner polygon is small enough, then it will not be stamped out. 
This seems okay to me. If both of them are filtered out, then its ok too.
> Mmh, 1st solution seems to be ok. In low resolutions mp code only cuts 
> out large inner holes. In this case it shouldn't matter if some small 
> pieces are cut from the large outer polygon.
>
>   
I think, 1st solution is exactly what we have now??
mp code is exectued before filter chain and therefore before size filter.
I would prefer strongly 2nd solution. With this even small polygons are 
deleted before they are cut out from the bigger one.

But I see a technical problem arise:
In the filter chain there aren't any more tags or other information on 
how polygons are connected. There are only the raw polygon objects with 
coordinate data.

The whole process of mkgmap is a two stage process.
First the osm data (or mp data) gets parsed and imported into internal 
objects. While parsing more ore less complicated 
filtering/merging/sorting/generating of  pois/cleanup of the osm data is 
done. This is the stage where you are working at the moment with your 
multipolygon code. At the end of it, there should be a cleaned 
representation of the map with independent objects.

In the second stage this objects needs to be transfered into the garmin 
img format and the different levels. There are some limitations in the 
format, e.g. a polygon could not have more than 250 points. So it has to 
be splitted. And at very low zooms you cant all details of the polygon. 
So it could be simplified by the dp filter to save resources.

In my very private opinion the multipolygon handling should be done in 
the first stage, at it is now, and the splitting should be done in the 
filter chain after size and dp filter. But I see, that this could be 
problematic, as the splitting has given some performance boost to the MP 
code, so it will not be easy to extract this part of it.

Hmm, more thinking required...

Regards,
Johann

> WanMil
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> .
>
>   