[mkgmap-dev] [mp: PATCH] Multipolygons: inner and nested polygons supported now

Sat Jan 2 12:10:43 GMT 2010

On 02.01.2010 12:36, WanMil wrote:
> Am 02.01.2010 12:17, schrieb Felix Hartmann:
>> Ups, there must be some bug, or the code is very inefficient.
>>
>> Austria compiled fine, but when I compiled Italy using this patch versus
>> standard trunk. Usually the 16 tiles of italy compile in 8 minutes. Now
>> it has compiled 6 tiles in 20 minutes only. However while 5 tiles
>> compiled in normal speed, 1 took 10 minutes and currently it is stuck 
>> again.
>> It seems to get stuck on single tiles and max-jobs is then not
>> continuing until the file it is stuck on finishes (only one instead of 2
>> cpu cores used for a long time).
>>
>> The one tile it took 10 minutes instead of 1 minute to compile, was also
>> the only one with quite substantial size increase (5.07 to 5.20 MB).
>>
>> I'll break the rendering now and delete the following line from my
>> relations file, maybe this is causing it to go slow?
>> landuse=forest                         { apply { add landuse=forest; add
>> name = '${name}'; add ref = '${ref}'    } }
Well the above line in the relations file seems to be not needed 
anymore. However it is not responsible for the slowdown. I just ran it 
with the default style-file and processing time did not decrease 
significantly.
>> _______________________________________________
>> mkgmap-dev mailing list
>> mkgmap-dev at lists.mkgmap.org.uk
>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>>
>
> The code is not optimized (and not well tested...) yet.
> I expect two possible problems:
> * an endless loop?
> * the bugfixed findCpa method is much more complex
>
> findCpa now checks if the line that is created between the outer and 
> the inner polygon intersects the outer polygon. I am using a very 
> rough (and probably very unoptimized) solution. And it will get worse 
> because the current implementation is not complete.
> The if statement in line 698
> if (intersects(l1,
>                l1.get(newDistance.index1),
>                l2.get(newDistance.index2)) == false) {
>
> must be replaced with
>
> if (intersects(l1,
>                l1.get(newDistance.index1),
>                l2.get(newDistance.index2)) == false
> && intersects(l2,
>                l1.get(newDistance.index1),
>                l2.get(newDistance.index2)) == false) {
>
> You could try to increase the maxEntries variable in findCpa. The 
> current value 500000 seems to be too low. Set it much higher might 
> reduce the number of intersects calls. But this also depends on the 
> geometry of the polygons.
Okay, I wil will try to increase the maxEntries values, and hope someone 
finds a way to optimize the code....
I'll run it against Germany now, in order to see whether the problem 
might be due to some bogus osm data in Italy, or the huge time penalties 
(about 10x the time needed on the problem tiles) are inherent to the use 
of multipolygons. I think in Austria we have still few multipolygons but 
Germany should stress it a lot more.

--------
I have one idea for optimization that should be simple on map data, but 
probably difficult to code.
Essentially when using a TYP-File we only need Multipolygons when an 
area with lower or equal draw priority (DP) overlaps an area with higher 
draw priority.

Most people will have polygons like natural=forest or 
landuse=residential with very low draw priority.

This leaves us two important things:
1. I could define no multipolygon check needed on forest and 
landuse=residential because they have DP=0 and anyhow all other areas 
will overlap them. I think that dropping all multipolygons where forest 
is outer should already kick out 50% of Multipolygons from the calculation.
2. We could go so far that one includes all DP not only in the TYP-File, 
but also in the style-file, and only if a lower DP inner multipolygon 
overlaps an higher DP outer multipolygon there needs to be action taken.
>
> WanMil