[mp: PATCH] Multipolygons: inner and nested polygons supported now
Thanks for committing the new multipolygon to a branch and for all of your comments. They're helpful always! I have improved the multipolygon handling in the mp-branch. Changes: * Tagged inner polygons are supported now * Nested polygons (outer in inner in outer etc) are supported now * Bugfix in the findCpa method (this could also be interesting for the trunk). findCpa did search only for the two closest points. It didn't check if this connection intersects the outer polygon. The bugfix checks this (see attached picture: old version selects the red line, bugfix selects the green line). Next thing to do is to bugfix the PolygonSplitter. Comments are welcome! WanMil
Finally the forest east of Vienna is shown on mkgmap created maps. My map of Austria increase from 55.8MB to 60MB in size, so I think there must be some more polygons that were dropped before but now included into the map (compared to the first published MultiPolygonRelation.java by WanMil - I'm not using the multipolyn branch but only the file plus the new patch by WanMil).
Am 02.01.2010 11:45, schrieb Felix Hartmann:
Finally the forest east of Vienna is shown on mkgmap created maps. My map of Austria increase from 55.8MB to 60MB in size, so I think there must be some more polygons that were dropped before but now included into the map (compared to the first published MultiPolygonRelation.java by WanMil - I'm not using the multipolyn branch but only the file plus the new patch by WanMil).
That's good news! The mp branch differs only by the MultiPolygonRelation.java so there should be no difference between your test and the mp branch. WanMil
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}' } }
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}' } } _______________________________________________ mkgmap-dev mailing list mkgmap-dev@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. WanMil
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@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
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}' } } _______________________________________________ mkgmap-dev mailing list mkgmap-dev@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.
.. Germany needed only 10% more compilation time. For Italy I now increased maxEntries to 25000000 (so 50x bigger) and it compiled the first two tiles where it got stuck before as usual and takes about 15% more time in general.. I did not notice any big difference in memory consumption (though as the other message I wrote today mkgmap memory requirements doubled over the last 50 revisions . and I suspect a memory leak somewhere). It got stuck a bit later on one tile for 8 minutes nevertheless. I then reran with 250Mio and expeceted it to not get stuck anymore. But the same tile as above again took ~8 minutes instead of ~1 minute to compile so it is not the maxEntries that is too low with that particular tile (though 50.000 definitely was too low, and increasing it to 25 Mio seemed to have good effects, Should I try with 50 billions to see whether it does not get stuck anymore?). --Now I will retry Austria/Germany/Italy with the different if statement in line 698 and look at the result.
WanMil
participants (2)
-
Felix Hartmann -
WanMil