tile takes very long time to generate
Hi. I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each. The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000. sea and bouds are used for mkgmap. At first i thought i am running low on memory but changing to max-jobs=1 (instead of the possible max of 2) did not make any change. Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles? I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing. Regards Karl
Hi Karl, I don't think that the order of the tiles should make a big difference. It is quite normal that some tiles take longer than others, but 30 minutes is far too long. One well known reason for slow processing are very complex multipolygons like Lake Huron. Another might be huge areas of sea. So, to find out if the order or the content is causing the delay you can process the tiles in a different order. I often use VisualVM to monitor a running mkgmap, it helps to find out which routines are called most often. If you identify a single tile that takes very long (also with the default style) you can upload that tile to http://files.mkgmap.org.uk/ Best is to add a small file with the options that were used, but you can also post them here. Hope that helps. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von 7770 <7770@foskan.eu> Gesendet: Montag, 8. März 2021 06:53 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: [mkgmap-dev] tile takes very long time to generate Hi. I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each. The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000. sea and bouds are used for mkgmap. At first i thought i am running low on memory but changing to max-jobs=1 (instead of the possible max of 2) did not make any change. Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles? I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing. Regards Karl _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Karl, The first tile is likely to be generated with only a single thread running whilst memory usage is checked, then the remainder may use both your processors. If there is something about this tile that causes it to take a long time, it may be worth moving it back in the list so that it doesn't hold up starting of parallel processes, resulting in an overall reduction in processing time. Cheers, Mike -----Original Message----- From: Gerd Petermann [mailto:gpetermann_muenchen@hotmail.com] Sent: 08 March 2021 06:32 To: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Subject: Re: [mkgmap-dev] tile takes very long time to generate Hi Karl, I don't think that the order of the tiles should make a big difference. It is quite normal that some tiles take longer than others, but 30 minutes is far too long. One well known reason for slow processing are very complex multipolygons like Lake Huron. Another might be huge areas of sea. So, to find out if the order or the content is causing the delay you can process the tiles in a different order. I often use VisualVM to monitor a running mkgmap, it helps to find out which routines are called most often. If you identify a single tile that takes very long (also with the default style) you can upload that tile to http://files.mkgmap.org.uk/ Best is to add a small file with the options that were used, but you can also post them here. Hope that helps. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von 7770 <7770@foskan.eu> Gesendet: Montag, 8. März 2021 06:53 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: [mkgmap-dev] tile takes very long time to generate Hi. I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each. The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000. sea and bouds are used for mkgmap. At first i thought i am running low on memory but changing to max-jobs=1 (instead of the possible max of 2) did not make any change. Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles? I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing. Regards Karl _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi. I have uploaded the splitter output http://files.mkgmap.org.uk/download/502/77700003.osm.pbf This is not the largest splitted pbf, but it generates the largest img-file. Around 12 MB compared to most other tiles which end up being 4-8 MB. I tested running mkgmap (--max-jobs=1) with this file only as input (with default style as well), it took 23 minutes before it was done, including any startup over head. I then took one random other pbf file and run mkgmap with the same parameters, it took 48 seconds including startup and overhead. I have a portion of data covering nordic and baltic countries, poland, chech, slovakia, austria, switserland, parts of germany and aslo greenland. Splitter options: java -Xmx2200m -jar ${SPLITTER} \ --output-dir=./splitted/ \ --mapid=77700001 \ --max-nodes=1275000 \ --no-trim \ kartdata/nord_ost.o5m mkgmap options: java -Xmx2800m -jar ${MKGMAP} \ --max-jobs \ --family-name="some name" \ --family-id=7770 \ --mapname=77710001 \ --draw-priority=20 \ --latin1 \ --net --route --index --split-name-index \ --housenumbers \ --add-boundary-nodes-at-admin-boundaries=2 \ --output-dir=./tiles_7771/ \ --bounds=bounds/ \ --precomp-sea=sea/ \ --style-file=styles_7771/ \ --description="some name" \ --add-pois-to-areas \ --lower-case \ ./splitted/777*.pbf is there some other tool or some options i can give to java runtime instead of using virualvm to see the amount of time/cpu spent in various sections of the program? Regards Karl On måndag 8 mars 2021 kl. 07:31:44 CET Gerd Petermann wrote:
Hi Karl,
I don't think that the order of the tiles should make a big difference. It is quite normal that some tiles take longer than others, but 30 minutes is far too long. One well known reason for slow processing are very complex multipolygons like Lake Huron. Another might be huge areas of sea. So, to find out if the order or the content is causing the delay you can process the tiles in a different order. I often use VisualVM to monitor a running mkgmap, it helps to find out which routines are called most often. If you identify a single tile that takes very long (also with the default style) you can upload that tile to http://files.mkgmap.org.uk/ Best is to add a small file with the options that were used, but you can also post them here. Hope that helps.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von 7770 <7770@foskan.eu> Gesendet: Montag, 8. März 2021 06:53 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: [mkgmap-dev] tile takes very long time to generate
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max-jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Karl, There are several ways to measure performance of java programs, but the options depend on the used JRE. You can search the web for "java performance command line". I think in your file the multipolygon relation (MP) 9488835 ("name:en"="Labrador Sea") is the problem,. I can reproduce slow processing without any options. The MP has ~25.000 members. The "physical" tag is place=sea and it contains thousands of islands. This requires a lot of computational power. One question here is why this happens as the default style doesn't render place=sea. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von 7770 <7770@foskan.eu> Gesendet: Montag, 8. März 2021 19:17 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi. I have uploaded the splitter output http://files.mkgmap.org.uk/download/502/77700003.osm.pbf This is not the largest splitted pbf, but it generates the largest img-file. Around 12 MB compared to most other tiles which end up being 4-8 MB. I tested running mkgmap (--max-jobs=1) with this file only as input (with default style as well), it took 23 minutes before it was done, including any startup over head. I then took one random other pbf file and run mkgmap with the same parameters, it took 48 seconds including startup and overhead. I have a portion of data covering nordic and baltic countries, poland, chech, slovakia, austria, switserland, parts of germany and aslo greenland. Splitter options: java -Xmx2200m -jar ${SPLITTER} \ --output-dir=./splitted/ \ --mapid=77700001 \ --max-nodes=1275000 \ --no-trim \ kartdata/nord_ost.o5m mkgmap options: java -Xmx2800m -jar ${MKGMAP} \ --max-jobs \ --family-name="some name" \ --family-id=7770 \ --mapname=77710001 \ --draw-priority=20 \ --latin1 \ --net --route --index --split-name-index \ --housenumbers \ --add-boundary-nodes-at-admin-boundaries=2 \ --output-dir=./tiles_7771/ \ --bounds=bounds/ \ --precomp-sea=sea/ \ --style-file=styles_7771/ \ --description="some name" \ --add-pois-to-areas \ --lower-case \ ./splitted/777*.pbf is there some other tool or some options i can give to java runtime instead of using virualvm to see the amount of time/cpu spent in various sections of the program? Regards Karl On måndag 8 mars 2021 kl. 07:31:44 CET Gerd Petermann wrote:
Hi Karl,
I don't think that the order of the tiles should make a big difference. It is quite normal that some tiles take longer than others, but 30 minutes is far too long. One well known reason for slow processing are very complex multipolygons like Lake Huron. Another might be huge areas of sea. So, to find out if the order or the content is causing the delay you can process the tiles in a different order. I often use VisualVM to monitor a running mkgmap, it helps to find out which routines are called most often. If you identify a single tile that takes very long (also with the default style) you can upload that tile to http://files.mkgmap.org.uk/ Best is to add a small file with the options that were used, but you can also post them here. Hope that helps.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von 7770 <7770@foskan.eu> Gesendet: Montag, 8. März 2021 06:53 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: [mkgmap-dev] tile takes very long time to generate
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max-jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi all, the performance problem for this special relation might be caused by the fact that the code in mkgmap still supports "old style" multipolygons. I think it is time to remove that support, the tagging style is deprecated since quite a while and the OSM carto style doesn't render it. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Dienstag, 9. März 2021 09:20 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Karl, There are several ways to measure performance of java programs, but the options depend on the used JRE. You can search the web for "java performance command line". I think in your file the multipolygon relation (MP) 9488835 ("name:en"="Labrador Sea") is the problem,. I can reproduce slow processing without any options. The MP has ~25.000 members. The "physical" tag is place=sea and it contains thousands of islands. This requires a lot of computational power. One question here is why this happens as the default style doesn't render place=sea. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von 7770 <7770@foskan.eu> Gesendet: Montag, 8. März 2021 19:17 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi. I have uploaded the splitter output http://files.mkgmap.org.uk/download/502/77700003.osm.pbf This is not the largest splitted pbf, but it generates the largest img-file. Around 12 MB compared to most other tiles which end up being 4-8 MB. I tested running mkgmap (--max-jobs=1) with this file only as input (with default style as well), it took 23 minutes before it was done, including any startup over head. I then took one random other pbf file and run mkgmap with the same parameters, it took 48 seconds including startup and overhead. I have a portion of data covering nordic and baltic countries, poland, chech, slovakia, austria, switserland, parts of germany and aslo greenland. Splitter options: java -Xmx2200m -jar ${SPLITTER} \ --output-dir=./splitted/ \ --mapid=77700001 \ --max-nodes=1275000 \ --no-trim \ kartdata/nord_ost.o5m mkgmap options: java -Xmx2800m -jar ${MKGMAP} \ --max-jobs \ --family-name="some name" \ --family-id=7770 \ --mapname=77710001 \ --draw-priority=20 \ --latin1 \ --net --route --index --split-name-index \ --housenumbers \ --add-boundary-nodes-at-admin-boundaries=2 \ --output-dir=./tiles_7771/ \ --bounds=bounds/ \ --precomp-sea=sea/ \ --style-file=styles_7771/ \ --description="some name" \ --add-pois-to-areas \ --lower-case \ ./splitted/777*.pbf is there some other tool or some options i can give to java runtime instead of using virualvm to see the amount of time/cpu spent in various sections of the program? Regards Karl On måndag 8 mars 2021 kl. 07:31:44 CET Gerd Petermann wrote:
Hi Karl,
I don't think that the order of the tiles should make a big difference. It is quite normal that some tiles take longer than others, but 30 minutes is far too long. One well known reason for slow processing are very complex multipolygons like Lake Huron. Another might be huge areas of sea. So, to find out if the order or the content is causing the delay you can process the tiles in a different order. I often use VisualVM to monitor a running mkgmap, it helps to find out which routines are called most often. If you identify a single tile that takes very long (also with the default style) you can upload that tile to http://files.mkgmap.org.uk/ Best is to add a small file with the options that were used, but you can also post them here. Hope that helps.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von 7770 <7770@foskan.eu> Gesendet: Montag, 8. März 2021 06:53 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: [mkgmap-dev] tile takes very long time to generate
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max-jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Karl, some time ago, I stumbled upon a tile which took 2 hours(!) on my machine. With the "--polygon-file" option, the time could be reduced to less than 100 s. See the old message in the archive: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/026490.html and the thread "Performance with large files": http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/thread.html#26463 Perhaps the trick helps in your case, too. Kind regards, Bernhard Am 08.03.2021 um 06:53 schrieb 7770:
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max-jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
Hi all, I sea no easy way to fix this. We'll have more and more monster multipolygons like r9488835. The current code in mkgmap r4607 processes a type=multipolygon before any rule from relations is used, so there is no easy way to tell mkgmap to ignore any MP with place=sea. Using a program like osmfilter on complete countries or continents also takes time, so maybe the best place to filter these killers would be in splitter, but we probably need some flexible syntax similar to the style rules. Another option would be a new mkgmap rule file for mkgmap that would be processed after reading the MP but before processing its geometry. This new rule file could allow actions like those in the finalize section of points/polygons. Any ideas besides hard coded "quick&dirty" solutions? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Bernhard Hiller <bhil@gmx.de> Gesendet: Dienstag, 9. März 2021 09:50 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Karl, some time ago, I stumbled upon a tile which took 2 hours(!) on my machine. With the "--polygon-file" option, the time could be reduced to less than 100 s. See the old message in the archive: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/026490.html and the thread "Performance with large files": http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/thread.html#26463 Perhaps the trick helps in your case, too. Kind regards, Bernhard Am 08.03.2021 um 06:53 schrieb 7770:
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max-jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi I'm not sure of all the rules regarding relations and resultant polygons and some of the MultiPolygonRelation.java code defeat me but some thoughts: Even though the relation might not have any relevant tags, it is what causes all the significant inner and/or outer polygons to be create by mkgmap. It might have been necessary to use a relation because the closed way has too many points, etc. mkgmap's OSM loading process drops any tags not referenced by the style. For relations it sets a flag to say if any tags have been dropped. Later, it doesn't bother processing the relation (building the multipolygons) if it *HAD* no tags. So, a relation tagged with just: [notUsedInStyle=someValue] will cause full processing, whereas without this, nothing will happen. Much of the cost of MultiPolygon processing is the assembling of bits of way to make up the polygons. The rest of the cost is cutting inner polygons out of outer polygons. If the outer polygons really don't have tags used in the style, maybe this phase can be skipped. In this example, the tag in question is "place"; this will occur in most styles. In the above, I'm ignoring the special relation tag "type" and internal mkgmap:* tags. Ticker On Tue, 2021-03-09 at 15:27 +0000, Gerd Petermann wrote:
Hi all,
I sea no easy way to fix this. We'll have more and more monster multipolygons like r9488835. The current code in mkgmap r4607 processes a type=multipolygon before any rule from relations is used, so there is no easy way to tell mkgmap to ignore any MP with place=sea. Using a program like osmfilter on complete countries or continents also takes time, so maybe the best place to filter these killers would be in splitter, but we probably need some flexible syntax similar to the style rules. Another option would be a new mkgmap rule file for mkgmap that would be processed after reading the MP but before processing its geometry. This new rule file could allow actions like those in the finalize section of points/polygons.
Any ideas besides hard coded "quick&dirty" solutions?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Bernhard Hiller <bhil@gmx.de> Gesendet: Dienstag, 9. März 2021 09:50 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Karl, some time ago, I stumbled upon a tile which took 2 hours(!) on my machine. With the "--polygon-file" option, the time could be reduced to less than 100 s. See the old message in the archive: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/026490.html and the thread "Performance with large files": http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/thread.html#2646 3 Perhaps the trick helps in your case, too. Kind regards, Bernhard
Am 08.03.2021 um 06:53 schrieb 7770:
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max -jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, I think it would be good if we could defer the actions in method MultiPolygonRelation.processElements() until the relation style rules were used. This would allow to remove rather useless relations like the place=sea or place=island MPs or maybe add a tag to tell mkgmap that only a POI is needed. No idea how much work that would be or what side effects it would have. I've not yet checked why the mentioned MP takes soooo long, maybe it's because the MP contains some errors. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 10. März 2021 13:13 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi I'm not sure of all the rules regarding relations and resultant polygons and some of the MultiPolygonRelation.java code defeat me but some thoughts: Even though the relation might not have any relevant tags, it is what causes all the significant inner and/or outer polygons to be create by mkgmap. It might have been necessary to use a relation because the closed way has too many points, etc. mkgmap's OSM loading process drops any tags not referenced by the style. For relations it sets a flag to say if any tags have been dropped. Later, it doesn't bother processing the relation (building the multipolygons) if it *HAD* no tags. So, a relation tagged with just: [notUsedInStyle=someValue] will cause full processing, whereas without this, nothing will happen. Much of the cost of MultiPolygon processing is the assembling of bits of way to make up the polygons. The rest of the cost is cutting inner polygons out of outer polygons. If the outer polygons really don't have tags used in the style, maybe this phase can be skipped. In this example, the tag in question is "place"; this will occur in most styles. In the above, I'm ignoring the special relation tag "type" and internal mkgmap:* tags. Ticker On Tue, 2021-03-09 at 15:27 +0000, Gerd Petermann wrote:
Hi all,
I sea no easy way to fix this. We'll have more and more monster multipolygons like r9488835. The current code in mkgmap r4607 processes a type=multipolygon before any rule from relations is used, so there is no easy way to tell mkgmap to ignore any MP with place=sea. Using a program like osmfilter on complete countries or continents also takes time, so maybe the best place to filter these killers would be in splitter, but we probably need some flexible syntax similar to the style rules. Another option would be a new mkgmap rule file for mkgmap that would be processed after reading the MP but before processing its geometry. This new rule file could allow actions like those in the finalize section of points/polygons.
Any ideas besides hard coded "quick&dirty" solutions?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Bernhard Hiller <bhil@gmx.de> Gesendet: Dienstag, 9. März 2021 09:50 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Karl, some time ago, I stumbled upon a tile which took 2 hours(!) on my machine. With the "--polygon-file" option, the time could be reduced to less than 100 s. See the old message in the archive: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/026490.html and the thread "Performance with large files": http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/thread.html#2646 3 Perhaps the trick helps in your case, too. Kind regards, Bernhard
Am 08.03.2021 um 06:53 schrieb 7770:
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max -jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, reg. thetag handling I forgot to mention the --delete-tags-file option. This would allow to remove tags like place=sea or place=island while the input file is read, but the strange handling of MP tags makes this useless. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Mittwoch, 10. März 2021 13:42 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Ticker, I think it would be good if we could defer the actions in method MultiPolygonRelation.processElements() until the relation style rules were used. This would allow to remove rather useless relations like the place=sea or place=island MPs or maybe add a tag to tell mkgmap that only a POI is needed. No idea how much work that would be or what side effects it would have. I've not yet checked why the mentioned MP takes soooo long, maybe it's because the MP contains some errors. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 10. März 2021 13:13 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi I'm not sure of all the rules regarding relations and resultant polygons and some of the MultiPolygonRelation.java code defeat me but some thoughts: Even though the relation might not have any relevant tags, it is what causes all the significant inner and/or outer polygons to be create by mkgmap. It might have been necessary to use a relation because the closed way has too many points, etc. mkgmap's OSM loading process drops any tags not referenced by the style. For relations it sets a flag to say if any tags have been dropped. Later, it doesn't bother processing the relation (building the multipolygons) if it *HAD* no tags. So, a relation tagged with just: [notUsedInStyle=someValue] will cause full processing, whereas without this, nothing will happen. Much of the cost of MultiPolygon processing is the assembling of bits of way to make up the polygons. The rest of the cost is cutting inner polygons out of outer polygons. If the outer polygons really don't have tags used in the style, maybe this phase can be skipped. In this example, the tag in question is "place"; this will occur in most styles. In the above, I'm ignoring the special relation tag "type" and internal mkgmap:* tags. Ticker On Tue, 2021-03-09 at 15:27 +0000, Gerd Petermann wrote:
Hi all,
I sea no easy way to fix this. We'll have more and more monster multipolygons like r9488835. The current code in mkgmap r4607 processes a type=multipolygon before any rule from relations is used, so there is no easy way to tell mkgmap to ignore any MP with place=sea. Using a program like osmfilter on complete countries or continents also takes time, so maybe the best place to filter these killers would be in splitter, but we probably need some flexible syntax similar to the style rules. Another option would be a new mkgmap rule file for mkgmap that would be processed after reading the MP but before processing its geometry. This new rule file could allow actions like those in the finalize section of points/polygons.
Any ideas besides hard coded "quick&dirty" solutions?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Bernhard Hiller <bhil@gmx.de> Gesendet: Dienstag, 9. März 2021 09:50 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Karl, some time ago, I stumbled upon a tile which took 2 hours(!) on my machine. With the "--polygon-file" option, the time could be reduced to less than 100 s. See the old message in the archive: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/026490.html and the thread "Performance with large files": http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/thread.html#2646 3 Perhaps the trick helps in your case, too. Kind regards, Bernhard
Am 08.03.2021 um 06:53 schrieb 7770:
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max -jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd Having looked more closely at current OSM rules and what you said earlier in the thread about "old style" multipolygons and: https://wiki.openstreetmap.org/wiki/Old_style_multipolygons I'd agree that support for these should be removed. Then, with the appropriate --delete-tags-file=... the problem goes away. Ticker On Wed, 2021-03-10 at 12:47 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. thetag handling I forgot to mention the --delete-tags-file option. This would allow to remove tags like place=sea or place=island while the input file is read, but the strange handling of MP tags makes this useless.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Mittwoch, 10. März 2021 13:42 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Ticker,
I think it would be good if we could defer the actions in method MultiPolygonRelation.processElements() until the relation style rules were used. This would allow to remove rather useless relations like the place=sea or place=island MPs or maybe add a tag to tell mkgmap that only a POI is needed. No idea how much work that would be or what side effects it would have.
I've not yet checked why the mentioned MP takes soooo long, maybe it's because the MP contains some errors.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 10. März 2021 13:13 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi
I'm not sure of all the rules regarding relations and resultant polygons and some of the MultiPolygonRelation.java code defeat me but some thoughts:
Even though the relation might not have any relevant tags, it is what causes all the significant inner and/or outer polygons to be create by mkgmap. It might have been necessary to use a relation because the closed way has too many points, etc.
mkgmap's OSM loading process drops any tags not referenced by the style. For relations it sets a flag to say if any tags have been dropped. Later, it doesn't bother processing the relation (building the multipolygons) if it *HAD* no tags. So, a relation tagged with just: [notUsedInStyle=someValue] will cause full processing, whereas without this, nothing will happen.
Much of the cost of MultiPolygon processing is the assembling of bits of way to make up the polygons. The rest of the cost is cutting inner polygons out of outer polygons. If the outer polygons really don't have tags used in the style, maybe this phase can be skipped.
In this example, the tag in question is "place"; this will occur in most styles.
In the above, I'm ignoring the special relation tag "type" and internal mkgmap:* tags.
Ticker
On Tue, 2021-03-09 at 15:27 +0000, Gerd Petermann wrote:
Hi all,
I sea no easy way to fix this. We'll have more and more monster multipolygons like r9488835. The current code in mkgmap r4607 processes a type=multipolygon before any rule from relations is used, so there is no easy way to tell mkgmap to ignore any MP with place=sea. Using a program like osmfilter on complete countries or continents also takes time, so maybe the best place to filter these killers would be in splitter, but we probably need some flexible syntax similar to the style rules. Another option would be a new mkgmap rule file for mkgmap that would be processed after reading the MP but before processing its geometry. This new rule file could allow actions like those in the finalize section of points/polygons.
Any ideas besides hard coded "quick&dirty" solutions?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Bernhard Hiller <bhil@gmx.de> Gesendet: Dienstag, 9. März 2021 09:50 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Karl, some time ago, I stumbled upon a tile which took 2 hours(!) on my machine. With the "--polygon-file" option, the time could be reduced to less than 100 s. See the old message in the archive: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/026490.html and the thread "Performance with large files": http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/thread.html#26 46 3 Perhaps the trick helps in your case, too. Kind regards, Bernhard
Am 08.03.2021 um 06:53 schrieb 7770:
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max -jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, I fear the problem will not go away because the relation still has tags like name:en . Anyway, I work on a patch to remove the old-style support. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 10. März 2021 16:04 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd Having looked more closely at current OSM rules and what you said earlier in the thread about "old style" multipolygons and: https://wiki.openstreetmap.org/wiki/Old_style_multipolygons I'd agree that support for these should be removed. Then, with the appropriate --delete-tags-file=... the problem goes away. Ticker On Wed, 2021-03-10 at 12:47 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. thetag handling I forgot to mention the --delete-tags-file option. This would allow to remove tags like place=sea or place=island while the input file is read, but the strange handling of MP tags makes this useless.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Mittwoch, 10. März 2021 13:42 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Ticker,
I think it would be good if we could defer the actions in method MultiPolygonRelation.processElements() until the relation style rules were used. This would allow to remove rather useless relations like the place=sea or place=island MPs or maybe add a tag to tell mkgmap that only a POI is needed. No idea how much work that would be or what side effects it would have.
I've not yet checked why the mentioned MP takes soooo long, maybe it's because the MP contains some errors.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 10. März 2021 13:13 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi
I'm not sure of all the rules regarding relations and resultant polygons and some of the MultiPolygonRelation.java code defeat me but some thoughts:
Even though the relation might not have any relevant tags, it is what causes all the significant inner and/or outer polygons to be create by mkgmap. It might have been necessary to use a relation because the closed way has too many points, etc.
mkgmap's OSM loading process drops any tags not referenced by the style. For relations it sets a flag to say if any tags have been dropped. Later, it doesn't bother processing the relation (building the multipolygons) if it *HAD* no tags. So, a relation tagged with just: [notUsedInStyle=someValue] will cause full processing, whereas without this, nothing will happen.
Much of the cost of MultiPolygon processing is the assembling of bits of way to make up the polygons. The rest of the cost is cutting inner polygons out of outer polygons. If the outer polygons really don't have tags used in the style, maybe this phase can be skipped.
In this example, the tag in question is "place"; this will occur in most styles.
In the above, I'm ignoring the special relation tag "type" and internal mkgmap:* tags.
Ticker
On Tue, 2021-03-09 at 15:27 +0000, Gerd Petermann wrote:
Hi all,
I sea no easy way to fix this. We'll have more and more monster multipolygons like r9488835. The current code in mkgmap r4607 processes a type=multipolygon before any rule from relations is used, so there is no easy way to tell mkgmap to ignore any MP with place=sea. Using a program like osmfilter on complete countries or continents also takes time, so maybe the best place to filter these killers would be in splitter, but we probably need some flexible syntax similar to the style rules. Another option would be a new mkgmap rule file for mkgmap that would be processed after reading the MP but before processing its geometry. This new rule file could allow actions like those in the finalize section of points/polygons.
Any ideas besides hard coded "quick&dirty" solutions?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Bernhard Hiller <bhil@gmx.de> Gesendet: Dienstag, 9. März 2021 09:50 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Karl, some time ago, I stumbled upon a tile which took 2 hours(!) on my machine. With the "--polygon-file" option, the time could be reduced to less than 100 s. See the old message in the archive: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/026490.html and the thread "Performance with large files": http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/thread.html#26 46 3 Perhaps the trick helps in your case, too. Kind regards, Bernhard
Am 08.03.2021 um 06:53 schrieb 7770:
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max -jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi all, most of the time that is needed to process complex multipolygons (MP) is spent in compex tests which try to detect invalid geometries like "inner" ring is not inside outer or overlapping /crossing rings. I wonder if it really makes sense to perform those tests in mkgmap. In JOSM, the strategy is like this: The renderer is optimistic and assumes that the geometry is correct, for invalid geometries "garbage in -> garbage out" is used. The validator performs a lot more tests and should find all the special cases mkgmap is looking for. This test is slow but still much faster than that in mkgmap (maybe 30 secs in JOSM, many minutes in mkgmap). If mkgmap finds invalid geometries the behaviour is still rather unpredictable. I've used JOSM to create some test cases with "inner" overlapping "outer" and sometimes the inner is completely ignores, sometimes not. So, I really wonder what all the complex code is doing. I've attached my test file I am not sure if I should try to improve the test code 1) to be faster or 2) to be more predictable or 3) both 1+2 or 4) if I should just remove all code that isn't needed to produce good results with correct data Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Donnerstag, 11. März 2021 07:58 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Ticker, I fear the problem will not go away because the relation still has tags like name:en . Anyway, I work on a patch to remove the old-style support. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 10. März 2021 16:04 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd Having looked more closely at current OSM rules and what you said earlier in the thread about "old style" multipolygons and: https://wiki.openstreetmap.org/wiki/Old_style_multipolygons I'd agree that support for these should be removed. Then, with the appropriate --delete-tags-file=... the problem goes away. Ticker On Wed, 2021-03-10 at 12:47 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. thetag handling I forgot to mention the --delete-tags-file option. This would allow to remove tags like place=sea or place=island while the input file is read, but the strange handling of MP tags makes this useless.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Mittwoch, 10. März 2021 13:42 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Ticker,
I think it would be good if we could defer the actions in method MultiPolygonRelation.processElements() until the relation style rules were used. This would allow to remove rather useless relations like the place=sea or place=island MPs or maybe add a tag to tell mkgmap that only a POI is needed. No idea how much work that would be or what side effects it would have.
I've not yet checked why the mentioned MP takes soooo long, maybe it's because the MP contains some errors.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 10. März 2021 13:13 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi
I'm not sure of all the rules regarding relations and resultant polygons and some of the MultiPolygonRelation.java code defeat me but some thoughts:
Even though the relation might not have any relevant tags, it is what causes all the significant inner and/or outer polygons to be create by mkgmap. It might have been necessary to use a relation because the closed way has too many points, etc.
mkgmap's OSM loading process drops any tags not referenced by the style. For relations it sets a flag to say if any tags have been dropped. Later, it doesn't bother processing the relation (building the multipolygons) if it *HAD* no tags. So, a relation tagged with just: [notUsedInStyle=someValue] will cause full processing, whereas without this, nothing will happen.
Much of the cost of MultiPolygon processing is the assembling of bits of way to make up the polygons. The rest of the cost is cutting inner polygons out of outer polygons. If the outer polygons really don't have tags used in the style, maybe this phase can be skipped.
In this example, the tag in question is "place"; this will occur in most styles.
In the above, I'm ignoring the special relation tag "type" and internal mkgmap:* tags.
Ticker
On Tue, 2021-03-09 at 15:27 +0000, Gerd Petermann wrote:
Hi all,
I sea no easy way to fix this. We'll have more and more monster multipolygons like r9488835. The current code in mkgmap r4607 processes a type=multipolygon before any rule from relations is used, so there is no easy way to tell mkgmap to ignore any MP with place=sea. Using a program like osmfilter on complete countries or continents also takes time, so maybe the best place to filter these killers would be in splitter, but we probably need some flexible syntax similar to the style rules. Another option would be a new mkgmap rule file for mkgmap that would be processed after reading the MP but before processing its geometry. This new rule file could allow actions like those in the finalize section of points/polygons.
Any ideas besides hard coded "quick&dirty" solutions?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Bernhard Hiller <bhil@gmx.de> Gesendet: Dienstag, 9. März 2021 09:50 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Karl, some time ago, I stumbled upon a tile which took 2 hours(!) on my machine. With the "--polygon-file" option, the time could be reduced to less than 100 s. See the old message in the archive: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/026490.html and the thread "Performance with large files": http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2017q1/thread.html#26 46 3 Perhaps the trick helps in your case, too. Kind regards, Bernhard
Am 08.03.2021 um 06:53 schrieb 7770:
Hi.
I observe a situation that one of the very first tiles (often the first or the third) that mkgmap generates takes 20 - 30 minutes to generate, wheres the others take about 30 seconds each.
The map data produced by splitter is a total of around 700 files with splitter option --max-nodes=1275000.
sea and bouds are used for mkgmap.
At first i thought i am running low on memory but changing to max -jobs=1 (instead of the possible max of 2) did not make any change.
Is mkgmap doing something specific in the beginning that can explain this long time generating one of the very first tiles?
I can provide more details, let me know how i can best collect those details in case i need to set some parameters to have mkgmap to say more about what it is doing.
Regards Karl
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd I think the extra testing should be removed and the logic should work on the assumption of correct data; just emitting warning/errors when problems are found during the normal processing. It also has extra complexity due to early versions of the splitter not keeping relations/polygons complete. Presumably this can be simplified now. role=inner/outer handling is strange, it looks like it totally ignores it! Going with "assuming correct data", conflicting "inner" and "outer" in a JoinedWay should be flagged, otherwise any "inner" or "outer" should be believed, with all null being considered "outer". Ticker On Sat, 2021-03-13 at 08:32 +0000, Gerd Petermann wrote:
Hi all,
most of the time that is needed to process complex multipolygons (MP) is spent in compex tests which try to detect invalid geometries like "inner" ring is not inside outer or overlapping /crossing rings. I wonder if it really makes sense to perform those tests in mkgmap. In JOSM, the strategy is like this: The renderer is optimistic and assumes that the geometry is correct, for invalid geometries "garbage in -> garbage out" is used. The validator performs a lot more tests and should find all the special cases mkgmap is looking for. This test is slow but still much faster than that in mkgmap (maybe 30 secs in JOSM, many minutes in mkgmap). If mkgmap finds invalid geometries the behaviour is still rather unpredictable. I've used JOSM to create some test cases with "inner" overlapping "outer" and sometimes the inner is completely ignores, sometimes not. So, I really wonder what all the complex code is doing.
I've attached my test file I am not sure if I should try to improve the test code 1) to be faster or 2) to be more predictable or 3) both 1+2 or 4) if I should just remove all code that isn't needed to produce good results with correct data
Gerd
Hi Ticker, the handling of the inner/outer role is indeed strange. The program calculates the "real" roles first, based on geometry. Later it checks if the given roles from the relation and may ignore the MP if no way has an empty role or role outer. This test should be done first or not at all. I think it is a good idea to calculate the roles based on geometry, for empty roles we need the code for this calculation anyway. I just think that mkgmap shouldn't care too much about invalid geometries when data is complete. I have to think again about those cases where data is not complete. Even with splitter and --keep-complete this can happen, e.g. when the input for splitter already contains incomplete relations. Maybe mkgmap can simply ignore incomplete MP after logging a warning. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Samstag, 13. März 2021 12:21 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd I think the extra testing should be removed and the logic should work on the assumption of correct data; just emitting warning/errors when problems are found during the normal processing. It also has extra complexity due to early versions of the splitter not keeping relations/polygons complete. Presumably this can be simplified now. role=inner/outer handling is strange, it looks like it totally ignores it! Going with "assuming correct data", conflicting "inner" and "outer" in a JoinedWay should be flagged, otherwise any "inner" or "outer" should be believed, with all null being considered "outer". Ticker On Sat, 2021-03-13 at 08:32 +0000, Gerd Petermann wrote:
Hi all,
most of the time that is needed to process complex multipolygons (MP) is spent in compex tests which try to detect invalid geometries like "inner" ring is not inside outer or overlapping /crossing rings. I wonder if it really makes sense to perform those tests in mkgmap. In JOSM, the strategy is like this: The renderer is optimistic and assumes that the geometry is correct, for invalid geometries "garbage in -> garbage out" is used. The validator performs a lot more tests and should find all the special cases mkgmap is looking for. This test is slow but still much faster than that in mkgmap (maybe 30 secs in JOSM, many minutes in mkgmap). If mkgmap finds invalid geometries the behaviour is still rather unpredictable. I've used JOSM to create some test cases with "inner" overlapping "outer" and sometimes the inner is completely ignores, sometimes not. So, I really wonder what all the complex code is doing.
I've attached my test file I am not sure if I should try to improve the test code 1) to be faster or 2) to be more predictable or 3) both 1+2 or 4) if I should just remove all code that isn't needed to produce good results with correct data
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi all, I've started a new branch called faster-mp, see http://www.mkgmap.org.uk/websvn/revision.php?repname=mkgmap&rev=4609 and the corresponding download link on the bottom of http://www.mkgmap.org.uk/download/mkgmap.html So far I've only started to remove "old-style MP" support. There are still some parts of the code that I don't fullly understand, so I think I have to create a functional unit test next, containing all the special cases like incomplete data , MP which are only partly inside of a tile or covering a complete tile and maybe also incorrect MP which should still be rendered somehow. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Sonntag, 14. März 2021 09:47 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Ticker, the handling of the inner/outer role is indeed strange. The program calculates the "real" roles first, based on geometry. Later it checks if the given roles from the relation and may ignore the MP if no way has an empty role or role outer. This test should be done first or not at all. I think it is a good idea to calculate the roles based on geometry, for empty roles we need the code for this calculation anyway. I just think that mkgmap shouldn't care too much about invalid geometries when data is complete. I have to think again about those cases where data is not complete. Even with splitter and --keep-complete this can happen, e.g. when the input for splitter already contains incomplete relations. Maybe mkgmap can simply ignore incomplete MP after logging a warning. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Samstag, 13. März 2021 12:21 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd I think the extra testing should be removed and the logic should work on the assumption of correct data; just emitting warning/errors when problems are found during the normal processing. It also has extra complexity due to early versions of the splitter not keeping relations/polygons complete. Presumably this can be simplified now. role=inner/outer handling is strange, it looks like it totally ignores it! Going with "assuming correct data", conflicting "inner" and "outer" in a JoinedWay should be flagged, otherwise any "inner" or "outer" should be believed, with all null being considered "outer". Ticker On Sat, 2021-03-13 at 08:32 +0000, Gerd Petermann wrote:
Hi all,
most of the time that is needed to process complex multipolygons (MP) is spent in compex tests which try to detect invalid geometries like "inner" ring is not inside outer or overlapping /crossing rings. I wonder if it really makes sense to perform those tests in mkgmap. In JOSM, the strategy is like this: The renderer is optimistic and assumes that the geometry is correct, for invalid geometries "garbage in -> garbage out" is used. The validator performs a lot more tests and should find all the special cases mkgmap is looking for. This test is slow but still much faster than that in mkgmap (maybe 30 secs in JOSM, many minutes in mkgmap). If mkgmap finds invalid geometries the behaviour is still rather unpredictable. I've used JOSM to create some test cases with "inner" overlapping "outer" and sometimes the inner is completely ignores, sometimes not. So, I really wonder what all the complex code is doing.
I've attached my test file I am not sure if I should try to improve the test code 1) to be faster or 2) to be more predictable or 3) both 1+2 or 4) if I should just remove all code that isn't needed to produce good results with correct data
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd Although it feels correct that the roles should be respected and used to avoid complex logic to work out the geometry, and blank role should be assumed outer, given it needs to work out which polygons to cut out from others, I agree with you and they should just act as a validation. I started looking in detail at the initial stages of MP processing at the end of last week and have re-written code to do the joining into polygons and lines. One thing I've done is added inner/outer counts to JoinedWay so conflict can be recognised (either in the free-standing polygon or with respect to the geometry of other polygons). I'll send you this in a while and you might consider some of the ideas worthwhile. At the moment is handles everything in the GB map except double-joined polygons and some strange boundaries (11 problems in all) Ticker On Sun, 2021-03-14 at 08:47 +0000, Gerd Petermann wrote:
Hi Ticker,
the handling of the inner/outer role is indeed strange. The program calculates the "real" roles first, based on geometry. Later it checks if the given roles from the relation and may ignore the MP if no way has an empty role or role outer. This test should be done first or not at all.
I think it is a good idea to calculate the roles based on geometry, for empty roles we need the code for this calculation anyway. I just think that mkgmap shouldn't care too much about invalid geometries when data is complete. I have to think again about those cases where data is not complete. Even with splitter and --keep-complete this can happen, e.g. when the input for splitter already contains incomplete relations.
Maybe mkgmap can simply ignore incomplete MP after logging a warning.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Samstag, 13. März 2021 12:21 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
I think the extra testing should be removed and the logic should work on the assumption of correct data; just emitting warning/errors when problems are found during the normal processing.
It also has extra complexity due to early versions of the splitter not keeping relations/polygons complete. Presumably this can be simplified now.
role=inner/outer handling is strange, it looks like it totally ignores it! Going with "assuming correct data", conflicting "inner" and "outer" in a JoinedWay should be flagged, otherwise any "inner" or "outer" should be believed, with all null being considered "outer".
Ticker
On Sat, 2021-03-13 at 08:32 +0000, Gerd Petermann wrote:
Hi all,
most of the time that is needed to process complex multipolygons (MP) is spent in compex tests which try to detect invalid geometries like "inner" ring is not inside outer or overlapping /crossing rings. I wonder if it really makes sense to perform those tests in mkgmap. In JOSM, the strategy is like this: The renderer is optimistic and assumes that the geometry is correct, for invalid geometries "garbage in -> garbage out" is used. The validator performs a lot more tests and should find all the special cases mkgmap is looking for. This test is slow but still much faster than that in mkgmap (maybe 30 secs in JOSM, many minutes in mkgmap). If mkgmap finds invalid geometries the behaviour is still rather unpredictable. I've used JOSM to create some test cases with "inner" overlapping "outer" and sometimes the inner is completely ignores, sometimes not. So, I really wonder what all the complex code is doing.
I've attached my test file I am not sure if I should try to improve the test code 1) to be faster or 2) to be more predictable or 3) both 1+2 or 4) if I should just remove all code that isn't needed to produce good results with correct data
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, OK, so I'll try to find a way to test this code. In the JOSM code there is a large collection of special cases which is used to test the validator. See https://josm.openstreetmap.de/browser/josm/trunk/nodist/data/multipolygon.os... I think about a similar file for mkgmap, I just have to find a good way to make the current code testable. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 09:50 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd Although it feels correct that the roles should be respected and used to avoid complex logic to work out the geometry, and blank role should be assumed outer, given it needs to work out which polygons to cut out from others, I agree with you and they should just act as a validation. I started looking in detail at the initial stages of MP processing at the end of last week and have re-written code to do the joining into polygons and lines. One thing I've done is added inner/outer counts to JoinedWay so conflict can be recognised (either in the free-standing polygon or with respect to the geometry of other polygons). I'll send you this in a while and you might consider some of the ideas worthwhile. At the moment is handles everything in the GB map except double-joined polygons and some strange boundaries (11 problems in all) Ticker On Sun, 2021-03-14 at 08:47 +0000, Gerd Petermann wrote:
Hi Ticker,
the handling of the inner/outer role is indeed strange. The program calculates the "real" roles first, based on geometry. Later it checks if the given roles from the relation and may ignore the MP if no way has an empty role or role outer. This test should be done first or not at all.
I think it is a good idea to calculate the roles based on geometry, for empty roles we need the code for this calculation anyway. I just think that mkgmap shouldn't care too much about invalid geometries when data is complete. I have to think again about those cases where data is not complete. Even with splitter and --keep-complete this can happen, e.g. when the input for splitter already contains incomplete relations.
Maybe mkgmap can simply ignore incomplete MP after logging a warning.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Samstag, 13. März 2021 12:21 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
I think the extra testing should be removed and the logic should work on the assumption of correct data; just emitting warning/errors when problems are found during the normal processing.
It also has extra complexity due to early versions of the splitter not keeping relations/polygons complete. Presumably this can be simplified now.
role=inner/outer handling is strange, it looks like it totally ignores it! Going with "assuming correct data", conflicting "inner" and "outer" in a JoinedWay should be flagged, otherwise any "inner" or "outer" should be believed, with all null being considered "outer".
Ticker
On Sat, 2021-03-13 at 08:32 +0000, Gerd Petermann wrote:
Hi all,
most of the time that is needed to process complex multipolygons (MP) is spent in compex tests which try to detect invalid geometries like "inner" ring is not inside outer or overlapping /crossing rings. I wonder if it really makes sense to perform those tests in mkgmap. In JOSM, the strategy is like this: The renderer is optimistic and assumes that the geometry is correct, for invalid geometries "garbage in -> garbage out" is used. The validator performs a lot more tests and should find all the special cases mkgmap is looking for. This test is slow but still much faster than that in mkgmap (maybe 30 secs in JOSM, many minutes in mkgmap). If mkgmap finds invalid geometries the behaviour is still rather unpredictable. I've used JOSM to create some test cases with "inner" overlapping "outer" and sometimes the inner is completely ignores, sometimes not. So, I really wonder what all the complex code is doing.
I've attached my test file I am not sure if I should try to improve the test code 1) to be faster or 2) to be more predictable or 3) both 1+2 or 4) if I should just remove all code that isn't needed to produce good results with correct data
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd Some possible test cases: Looking at the problems my code is detecting, the complicated cases are when possible polygons share 2 or more end-points with other possibles; for instance: http://www.openstreetmap.org/relation/5329106 adjacent buildings, touching each other, are mapped as a complete set of outers, using distinct ways. In general there is no easy way to resolve this. In the simple case of 2 buildings together, after all the simple ways have been joined, there are 4 ways between 2 points. Another case is: https://www.openstreetmap.org/relation/11093511 This is an outer area with an inner touching along part of the edge. This can be resolved by looking at the roles except that the shared edge uses the same way, which is repeated in the relation. Repeated ways are removed when the MP relation is created. Removing this de-dupe will probably causes other (invalid) relations not to be resolvable. The other class of problems I'm seeing is boundaries split across tiles. Ticker On Mon, 2021-03-15 at 09:10 +0000, Gerd Petermann wrote:
Hi Ticker,
OK, so I'll try to find a way to test this code. In the JOSM code there is a large collection of special cases which is used to test the validator. See https://josm.openstreetmap.de/browser/josm/trunk/nodist/data/multipol ygon.osm
I think about a similar file for mkgmap, I just have to find a good way to make the current code testable.
Gerd
Hi Ticker, both MP are are clearly invalid. I think mkgmap can ignore them. The outer rings of an MP must not share a segment with another ring. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 13:08 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd Some possible test cases: Looking at the problems my code is detecting, the complicated cases are when possible polygons share 2 or more end-points with other possibles; for instance: http://www.openstreetmap.org/relation/5329106 adjacent buildings, touching each other, are mapped as a complete set of outers, using distinct ways. In general there is no easy way to resolve this. In the simple case of 2 buildings together, after all the simple ways have been joined, there are 4 ways between 2 points. Another case is: https://www.openstreetmap.org/relation/11093511 This is an outer area with an inner touching along part of the edge. This can be resolved by looking at the roles except that the shared edge uses the same way, which is repeated in the relation. Repeated ways are removed when the MP relation is created. Removing this de-dupe will probably causes other (invalid) relations not to be resolvable. The other class of problems I'm seeing is boundaries split across tiles. Ticker On Mon, 2021-03-15 at 09:10 +0000, Gerd Petermann wrote:
Hi Ticker,
OK, so I'll try to find a way to test this code. In the JOSM code there is a large collection of special cases which is used to test the validator. See https://josm.openstreetmap.de/browser/josm/trunk/nodist/data/multipol ygon.osm
I think about a similar file for mkgmap, I just have to find a good way to make the current code testable.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd You might consider the some of the ideas here as improvements to the initial parts of MP processing. This is a patch based on trunk rather than the new branch. It isn't structured as for final usage, rather for minimising the spread of changes, working in parallel with the existing code so I could see if found the same MP problems as the existing code and having clearly identifiable diagnostics in the log file. Ticker
Hi all, I still struggle with the unit test because it's hard to say what we want to get in special cases. The current code doesn't really work in the way that I expected. I always thought that roles like "inner" and "outer" are completely ignored and that mkgmap calculates and uses the correct roles. This is only partly true. See attached file with MP were a forest contains a lake that contains a forest. For a nested polygon where the innermost ring has wrong role "inner" this doesn't work as expected. The forest in the lake is ignored. With the correct role "outer" it is not ignored. No idea if this is intended or an error. Fortunately nested MP are very rare. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 17:15 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd You might consider the some of the ideas here as improvements to the initial parts of MP processing. This is a patch based on trunk rather than the new branch. It isn't structured as for final usage, rather for minimising the spread of changes, working in parallel with the existing code so I could see if found the same MP problems as the existing code and having clearly identifiable diagnostics in the log file. Ticker
Hi Gerd, Nested polygons may not be as rare as you think, it was a situation I was thinking about when this discussion started. Zambia has a number of large wetlands where there are islands with wetland within the island, particularly as these wetlands are seasonal and the islands will be inundated during the rains with the low points of the island staying wet once the water recedes. This is similar to your forest with a lake that contains a forest. Dave Original Message From: gpetermann_muenchen@hotmail.com Sent: 18 March 2021 12:21 To: mkgmap-dev@lists.mkgmap.org.uk Reply to: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] tile takes very long time to generate Hi all, I still struggle with the unit test because it's hard to say what we want to get in special cases. The current code doesn't really work in the way that I expected. I always thought that roles like "inner" and "outer" are completely ignored and that mkgmap calculates and uses the correct roles. This is only partly true. See attached file with MP were a forest contains a lake that contains a forest. For a nested polygon where the innermost ring has wrong role "inner" this doesn't work as expected. The forest in the lake is ignored. With the correct role "outer" it is not ignored. No idea if this is intended or an error. Fortunately nested MP are very rare. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 17:15 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd You might consider the some of the ideas here as improvements to the initial parts of MP processing. This is a patch based on trunk rather than the new branch. It isn't structured as for final usage, rather for minimising the spread of changes, working in parallel with the existing code so I could see if found the same MP problems as the existing code and having clearly identifiable diagnostics in the log file. Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Dave, thanks for the hint. I'll have a closer look at that country. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Dave <dfjkman@gmail.com> Gesendet: Donnerstag, 18. März 2021 12:02 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd, Nested polygons may not be as rare as you think, it was a situation I was thinking about when this discussion started. Zambia has a number of large wetlands where there are islands with wetland within the island, particularly as these wetlands are seasonal and the islands will be inundated during the rains with the low points of the island staying wet once the water recedes. This is similar to your forest with a lake that contains a forest. Dave Original Message From: gpetermann_muenchen@hotmail.com Sent: 18 March 2021 12:21 To: mkgmap-dev@lists.mkgmap.org.uk Reply to: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] tile takes very long time to generate Hi all, I still struggle with the unit test because it's hard to say what we want to get in special cases. The current code doesn't really work in the way that I expected. I always thought that roles like "inner" and "outer" are completely ignored and that mkgmap calculates and uses the correct roles. This is only partly true. See attached file with MP were a forest contains a lake that contains a forest. For a nested polygon where the innermost ring has wrong role "inner" this doesn't work as expected. The forest in the lake is ignored. With the correct role "outer" it is not ignored. No idea if this is intended or an error. Fortunately nested MP are very rare. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 17:15 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd You might consider the some of the ideas here as improvements to the initial parts of MP processing. This is a patch based on trunk rather than the new branch. It isn't structured as for final usage, rather for minimising the spread of changes, working in parallel with the existing code so I could see if found the same MP problems as the existing code and having clearly identifiable diagnostics in the log file. Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd I'm revising my opinion about considering the geometry to determine inner and outer. All the different BitSets, containsMatrix etc logic is too complex, and if it then conflicts with the explicit definition of the MP it just gets worse. I'd simpify it along these lines: split the polygon/joinedWay list: error: the explicit conflicting inner/outer inners: at least one inner element outers: all the rest for each inner find a larger_area outer that contains a part of it add to the outer.listOfInners error if more than one for each outer cut out listOfInners apply tags output to the wayMap This copes correctly with outer with inner hole that contains another outer. If, in the above logic, more than one larger outer is found, then choosing the smallest would allow this nesting to any level. Ticker On Thu, 2021-03-18 at 10:21 +0000, Gerd Petermann wrote:
Hi all,
I still struggle with the unit test because it's hard to say what we want to get in special cases. The current code doesn't really work in the way that I expected. I always thought that roles like "inner" and "outer" are completely ignored and that mkgmap calculates and uses the correct roles. This is only partly true. See attached file with MP were a forest contains a lake that contains a forest. For a nested polygon where the innermost ring has wrong role "inner" this doesn't work as expected. The forest in the lake is ignored. With the correct role "outer" it is not ignored. No idea if this is intended or an error. Fortunately nested MP are very rare.
Gerd
Hi Ticker, I don't know what data we see when MultipolygonRelation is used with polish input, but I am sure that there is no info about roles. I also thought about using the info about the area size as a quick indicator before doing complex tests. The missing unit tests are my real problem. I've not (yet) found a good way to test the result. I'd like to have a test that allows to rotate or reverse rings so that we find errors with handling of the closing node. I think we need the complex and somehow tolerant tests for the boundary calculations, we cannot simply stop on error. I know that some admin boundaries have very special cases (France), they are not exactly correct reg. the rules for touching outer rings. So, I started to use already tested code where possible, e.g. IsInUtil. See attached patch. Run times seem similar to the existing code in trunk. Just experimental so far, but at least a lot less code... Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 30. März 2021 15:17 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd I'm revising my opinion about considering the geometry to determine inner and outer. All the different BitSets, containsMatrix etc logic is too complex, and if it then conflicts with the explicit definition of the MP it just gets worse. I'd simpify it along these lines: split the polygon/joinedWay list: error: the explicit conflicting inner/outer inners: at least one inner element outers: all the rest for each inner find a larger_area outer that contains a part of it add to the outer.listOfInners error if more than one for each outer cut out listOfInners apply tags output to the wayMap This copes correctly with outer with inner hole that contains another outer. If, in the above logic, more than one larger outer is found, then choosing the smallest would allow this nesting to any level. Ticker On Thu, 2021-03-18 at 10:21 +0000, Gerd Petermann wrote:
Hi all,
I still struggle with the unit test because it's hard to say what we want to get in special cases. The current code doesn't really work in the way that I expected. I always thought that roles like "inner" and "outer" are completely ignored and that mkgmap calculates and uses the correct roles. This is only partly true. See attached file with MP were a forest contains a lake that contains a forest. For a nested polygon where the innermost ring has wrong role "inner" this doesn't work as expected. The forest in the lake is ignored. With the correct role "outer" it is not ignored. No idea if this is intended or an error. Fortunately nested MP are very rare.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd Looking at the Polish format (cGPSmapper-UsrMan-v02.4.pdf), my understanding is that a polygon definition with multiple Data# statements at the same level defines a single outer with multiple inners (Page 20 and 74/5). Touching inner or outer rings is a slightly different problem and, I think, the current code has made all its choices about this before the complexity of geometry determination. I wasn't suggesting stopping on errors, but if there are only 2 way elements ending at a Coord, and one is explicitly marked "inner" and the other "outer" then I think this can be errored and chucked. Ticker On Wed, 2021-03-31 at 07:57 +0000, Gerd Petermann wrote:
Hi Ticker,
I don't know what data we see when MultipolygonRelation is used with polish input, but I am sure that there is no info about roles.
I also thought about using the info about the area size as a quick indicator before doing complex tests.
The missing unit tests are my real problem. I've not (yet) found a good way to test the result. I'd like to have a test that allows to rotate or reverse rings so that we find errors with handling of the closing node.
I think we need the complex and somehow tolerant tests for the boundary calculations, we cannot simply stop on error. I know that some admin boundaries have very special cases (France), they are not exactly correct reg. the rules for touching outer rings.
So, I started to use already tested code where possible, e.g. IsInUtil. See attached patch. Run times seem similar to the existing code in trunk. Just experimental so far, but at least a lot less code...
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 30. März 2021 15:17 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
I'm revising my opinion about considering the geometry to determine inner and outer. All the different BitSets, containsMatrix etc logic is too complex, and if it then conflicts with the explicit definition of the MP it just gets worse.
I'd simpify it along these lines:
split the polygon/joinedWay list: error: the explicit conflicting inner/outer inners: at least one inner element outers: all the rest
for each inner find a larger_area outer that contains a part of it add to the outer.listOfInners error if more than one
for each outer cut out listOfInners apply tags output to the wayMap
This copes correctly with outer with inner hole that contains another outer. If, in the above logic, more than one larger outer is found, then choosing the smallest would allow this nesting to any level.
Ticker
On Thu, 2021-03-18 at 10:21 +0000, Gerd Petermann wrote:
Hi all,
I still struggle with the unit test because it's hard to say what we want to get in special cases. The current code doesn't really work in the way that I expected. I always thought that roles like "inner" and "outer" are completely ignored and that mkgmap calculates and uses the correct roles. This is only partly true. See attached file with MP were a forest contains a lake that contains a forest. For a nested polygon where the innermost ring has wrong role "inner" this doesn't work as expected. The forest in the lake is ignored. With the correct role "outer" it is not ignored. No idea if this is intended or an error. Fortunately nested MP are very rare.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, reg. polish input: There was code based on the documentation and I removed it again. Don't remember why, see changes for r4269 and r4272 and http://gis.19327.n8.nabble.com/Artifacts-in-final-map-MP-gt-IMG-conversion-t... The current code is really too complex. A lot of the code exists for reporting purposes only. Another big portion is for the handling of incomplete data. There are probably hundreds of possible error cases with MPs. One of my goals is to find out which ones are tolerated by the current code and why they are tolerated. If nobody offers an approach regarding unit tests we may try to simply write a 2nd implementation for MultipolygonRelation and use an option to switch between them. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 31. März 2021 11:10 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd Looking at the Polish format (cGPSmapper-UsrMan-v02.4.pdf), my understanding is that a polygon definition with multiple Data# statements at the same level defines a single outer with multiple inners (Page 20 and 74/5). Touching inner or outer rings is a slightly different problem and, I think, the current code has made all its choices about this before the complexity of geometry determination. I wasn't suggesting stopping on errors, but if there are only 2 way elements ending at a Coord, and one is explicitly marked "inner" and the other "outer" then I think this can be errored and chucked. Ticker On Wed, 2021-03-31 at 07:57 +0000, Gerd Petermann wrote:
Hi Ticker,
I don't know what data we see when MultipolygonRelation is used with polish input, but I am sure that there is no info about roles.
I also thought about using the info about the area size as a quick indicator before doing complex tests.
The missing unit tests are my real problem. I've not (yet) found a good way to test the result. I'd like to have a test that allows to rotate or reverse rings so that we find errors with handling of the closing node.
I think we need the complex and somehow tolerant tests for the boundary calculations, we cannot simply stop on error. I know that some admin boundaries have very special cases (France), they are not exactly correct reg. the rules for touching outer rings.
So, I started to use already tested code where possible, e.g. IsInUtil. See attached patch. Run times seem similar to the existing code in trunk. Just experimental so far, but at least a lot less code...
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 30. März 2021 15:17 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
I'm revising my opinion about considering the geometry to determine inner and outer. All the different BitSets, containsMatrix etc logic is too complex, and if it then conflicts with the explicit definition of the MP it just gets worse.
I'd simpify it along these lines:
split the polygon/joinedWay list: error: the explicit conflicting inner/outer inners: at least one inner element outers: all the rest
for each inner find a larger_area outer that contains a part of it add to the outer.listOfInners error if more than one
for each outer cut out listOfInners apply tags output to the wayMap
This copes correctly with outer with inner hole that contains another outer. If, in the above logic, more than one larger outer is found, then choosing the smallest would allow this nesting to any level.
Ticker
On Thu, 2021-03-18 at 10:21 +0000, Gerd Petermann wrote:
Hi all,
I still struggle with the unit test because it's hard to say what we want to get in special cases. The current code doesn't really work in the way that I expected. I always thought that roles like "inner" and "outer" are completely ignored and that mkgmap calculates and uses the correct roles. This is only partly true. See attached file with MP were a forest contains a lake that contains a forest. For a nested polygon where the innermost ring has wrong role "inner" this doesn't work as expected. The forest in the lake is ignored. With the correct role "outer" it is not ignored. No idea if this is intended or an error. Fortunately nested MP are very rare.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd I think this might be the reason why you backed out the Polish inner/outer definition changes: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2019q1/029478.html Maybe there needs to be an option to say how multiple DATA{sameLevel} should be handled: a/ first outer, following inners. b/ outers clockwise, inners anti-clockwise; presume each outer is followed by its inners. c/ try to work out from geometry. Ticker On Wed, 2021-03-31 at 09:39 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. polish input: There was code based on the documentation and I removed it again. Don't remember why, see changes for r4269 and r4272 and http://gis.19327.n8.nabble.com/Artifacts-in-final-map-MP-gt-IMG-conve rsion-tc5932812.html
The current code is really too complex. A lot of the code exists for reporting purposes only. Another big portion is for the handling of incomplete data. There are probably hundreds of possible error cases with MPs. One of my goals is to find out which ones are tolerated by the current code and why they are tolerated.
If nobody offers an approach regarding unit tests we may try to simply write a 2nd implementation for MultipolygonRelation and use an option to switch between them.
Gerd
Hi Ticker, I tried to use your patch mpInitialLogic.patch. It is missing the code to update the field Way.points, means, the final polygons only contain the points of one way. Not sure how you used that code? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 17:15 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd You might consider the some of the ideas here as improvements to the initial parts of MP processing. This is a patch based on trunk rather than the new branch. It isn't structured as for final usage, rather for minimising the spread of changes, working in parallel with the existing code so I could see if found the same MP problems as the existing code and having clearly identifiable diagnostics in the log file. Ticker
Hi Gerd One of the ideas of the code is that it doesn't keep reversing all the points as it gets to joining the ways to make a polygon. Once all the ways have been gathered, then another stage is needed adds the points from JoinedWay.originalWay to .points the correct order, removing the intermediate joining points, etc. Another part that's missing is what to do with unclosed ways, and here I guess it can take a similar line to the existing logic. I can do another patch, based on faster_mp branch - for real - if you think this change is worth while. Ticker On Tue, 2021-04-06 at 10:45 +0000, Gerd Petermann wrote:
Hi Ticker,
I tried to use your patch mpInitialLogic.patch. It is missing the code to update the field Way.points, means, the final polygons only contain the points of one way.
Not sure how you used that code?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 17:15 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
You might consider the some of the ideas here as improvements to the initial parts of MP processing.
This is a patch based on trunk rather than the new branch. It isn't structured as for final usage, rather for minimising the spread of changes, working in parallel with the existing code so I could see if found the same MP problems as the existing code and having clearly identifiable diagnostics in the log file.
Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, no need for another patch at the moment. I just try to make up my mind at what places the role info should/must be used and while looking at your code I wondered how it would work. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 6. April 2021 12:59 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd One of the ideas of the code is that it doesn't keep reversing all the points as it gets to joining the ways to make a polygon. Once all the ways have been gathered, then another stage is needed adds the points from JoinedWay.originalWay to .points the correct order, removing the intermediate joining points, etc. Another part that's missing is what to do with unclosed ways, and here I guess it can take a similar line to the existing logic. I can do another patch, based on faster_mp branch - for real - if you think this change is worth while. Ticker On Tue, 2021-04-06 at 10:45 +0000, Gerd Petermann wrote:
Hi Ticker,
I tried to use your patch mpInitialLogic.patch. It is missing the code to update the field Way.points, means, the final polygons only contain the points of one way.
Not sure how you used that code?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 17:15 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
You might consider the some of the ideas here as improvements to the initial parts of MP processing.
This is a patch based on trunk rather than the new branch. It isn't structured as for final usage, rather for minimising the spread of changes, working in parallel with the existing code so I could see if found the same MP problems as the existing code and having clearly identifiable diagnostics in the log file.
Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, reg. mpInitialLogic.patch: I think I tried the same approach to join the ways in the past. Problem is that the patched code produces rings with an unpredictable start/end and thus random content in RGN. This makes comparisons of two mkgmap outputs much more difficult if not impossable. The existing algo works quite well if the members are sorted and most complex MP are sorted well enough. I think in the worst case (badly shuffled member list) the algo complexity is probably O(n²) , in the best case it is O(n) where n gives the number of unclosed ways in the member list. Maybe you find a way to use the HashMap to avoid the sequential search for the next member without adding too much complexity to the current code? Or a simple sort to avoid the worst case? Even with worse cases I don't see more than a few seconds for very complex MP. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Dienstag, 6. April 2021 13:06 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Ticker, no need for another patch at the moment. I just try to make up my mind at what places the role info should/must be used and while looking at your code I wondered how it would work. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 6. April 2021 12:59 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd One of the ideas of the code is that it doesn't keep reversing all the points as it gets to joining the ways to make a polygon. Once all the ways have been gathered, then another stage is needed adds the points from JoinedWay.originalWay to .points the correct order, removing the intermediate joining points, etc. Another part that's missing is what to do with unclosed ways, and here I guess it can take a similar line to the existing logic. I can do another patch, based on faster_mp branch - for real - if you think this change is worth while. Ticker On Tue, 2021-04-06 at 10:45 +0000, Gerd Petermann wrote:
Hi Ticker,
I tried to use your patch mpInitialLogic.patch. It is missing the code to update the field Way.points, means, the final polygons only contain the points of one way.
Not sure how you used that code?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Montag, 15. März 2021 17:15 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
You might consider the some of the ideas here as improvements to the initial parts of MP processing.
This is a patch based on trunk rather than the new branch. It isn't structured as for final usage, rather for minimising the spread of changes, working in parallel with the existing code so I could see if found the same MP problems as the existing code and having clearly identifiable diagnostics in the log file.
Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd Problem is that IdentityHashMap is the ideal solution, but ordering behaviour depends on internal java object handles. A solution to this stability issue would be to rotate joinedWays.originalWays so, say, the one with the lowest ID is first, doing this just before the full point -list is created. Maybe not worth it if existing logic is not a problem. Some of the other advantages my logic: Clearer and more efficient. Elements are scanned once; cOg and closed polygons are processed immediately. Elements from SeaGenerator are all closed. Single touching polygons are handled without difficulty; just part of the way the algo is expressed. Maintaining jw.inner/outerCount gives clarity to this issue. Can be used for error reporting and behavioral definition. If the roles are not to be trusted, the counts can be adjusted when the geometry is determined. Ticker On Wed, 2021-04-07 at 08:57 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. mpInitialLogic.patch: I think I tried the same approach to join the ways in the past. Problem is that the patched code produces rings with an unpredictable start/end and thus random content in RGN. This makes comparisons of two mkgmap outputs much more difficult if not impossable.
The existing algo works quite well if the members are sorted and most complex MP are sorted well enough. I think in the worst case (badly shuffled member list) the algo complexity is probably O(n²) , in the best case it is O(n) where n gives the number of unclosed ways in the member list.
Maybe you find a way to use the HashMap to avoid the sequential search for the next member without adding too much complexity to the current code? Or a simple sort to avoid the worst case? Even with worse cases I don't see more than a few seconds for very complex MP.
Gerd
Hi Ticker, I think I am making progress with my divide&conquer approach. I see ~20 secs instead of more than 7 minutes to process the monster relation r9488835. The basic approach is to use ShapeSplitter.splitShape() multiple times to divide the multipolygon into smaller pieces where no ring has more than 20.000 nodes and executing the block analyseRelationRoles() ... doReporting() for each piece. The work is not yet done, the output file is a bit larger, not yet sure why, and the calculation of the "largestOuterPolygon" neads a bit more work. There are probably edge cases where this doesn't work, esp. when inners are very large. BTW: I found a bug in IsInUtil.isLineInShape() : It sometimes returns ON when it should return IN/ON I think it happens when a ring has start /end node ON and also 2nd or 2nd-last node ON. Probably a special case created by the ShapeSplitter. Attached patch fixes the problem in IsInUtil. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 7. April 2021 13:02 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd Problem is that IdentityHashMap is the ideal solution, but ordering behaviour depends on internal java object handles. A solution to this stability issue would be to rotate joinedWays.originalWays so, say, the one with the lowest ID is first, doing this just before the full point -list is created. Maybe not worth it if existing logic is not a problem. Some of the other advantages my logic: Clearer and more efficient. Elements are scanned once; cOg and closed polygons are processed immediately. Elements from SeaGenerator are all closed. Single touching polygons are handled without difficulty; just part of the way the algo is expressed. Maintaining jw.inner/outerCount gives clarity to this issue. Can be used for error reporting and behavioral definition. If the roles are not to be trusted, the counts can be adjusted when the geometry is determined. Ticker On Wed, 2021-04-07 at 08:57 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. mpInitialLogic.patch: I think I tried the same approach to join the ways in the past. Problem is that the patched code produces rings with an unpredictable start/end and thus random content in RGN. This makes comparisons of two mkgmap outputs much more difficult if not impossable.
The existing algo works quite well if the members are sorted and most complex MP are sorted well enough. I think in the worst case (badly shuffled member list) the algo complexity is probably O(n²) , in the best case it is O(n) where n gives the number of unclosed ways in the member list.
Maybe you find a way to use the HashMap to avoid the sequential search for the next member without adding too much complexity to the current code? Or a simple sort to avoid the worst case? Even with worse cases I don't see more than a few seconds for very complex MP.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd I'd have thought using isPointInShape() in combination with polygon areas to be more efficient and robust than isLineInShape() (which makes multiple calls to isPointInShape). Would need to choose a reference point within each polygon, ensuring it is IN but not ON itself. Probably splitShape(), isPointInShape() and calcAreaSize()/calcAreaSizeTestVal() all have very similar costs; linear on number of points. I understand some benefits of splitting a massive outer into multiples polygons, in that a point-IN question might give an quicker answer, but it must introduce a lot of other difficulties with edge cases on the artificial boundaries, etc, etc. Splitting inners shouldn't cause a probem in this respect (just a list of inners), but if there is another outer in the hole, this will become confusing. A couple of other things I meant to mention following earlier faster-mp svn updates: I found cases, as both inner and outer, where adjacent rectangles (eg buildings) are touched together, with either a duplicate or identical member being the dividing wall. I realise that some combinations of this violate OSM MP rules, but, keeping the duplicate, allows this simple "double-touching" structure to be resolved; where there are 4 ways at a node, don't join 2 that are identical or have same other-end and no other points. Joining ways if possible in the initial element iteration and ignoring roles can lead to problems when inner and outer touch. Whereas saving them all in a Map of both ends, before attempting to join, will avoid the problem for single-touching. For double-touching, any roles can be used to join the correct parts. For ordering stability if using a HashMap, could just keep track of lowest element# in joinedWays and always keep this first. Ticker On Mon, 2021-04-26 at 14:17 +0000, Gerd Petermann wrote:
Hi Ticker,
I think I am making progress with my divide&conquer approach. I see ~20 secs instead of more than 7 minutes to process the monster relation r9488835. The basic approach is to use ShapeSplitter.splitShape() multiple times to divide the multipolygon into smaller pieces where no ring has more than 20.000 nodes and executing the block
analyseRelationRoles() ... doReporting() for each piece.
The work is not yet done, the output file is a bit larger, not yet sure why, and the calculation of the "largestOuterPolygon" neads a bit more work. There are probably edge cases where this doesn't work, esp. when inners are very large.
BTW: I found a bug in IsInUtil.isLineInShape() : It sometimes returns ON when it should return IN/ON I think it happens when a ring has start /end node ON and also 2nd or 2nd-last node ON. Probably a special case created by the ShapeSplitter. Attached patch fixes the problem in IsInUtil.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 7. April 2021 13:02 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
Problem is that IdentityHashMap is the ideal solution, but ordering behaviour depends on internal java object handles. A solution to this stability issue would be to rotate joinedWays.originalWays so, say, the one with the lowest ID is first, doing this just before the full point -list is created.
Maybe not worth it if existing logic is not a problem.
Some of the other advantages my logic:
Clearer and more efficient.
Elements are scanned once; cOg and closed polygons are processed immediately. Elements from SeaGenerator are all closed.
Single touching polygons are handled without difficulty; just part of the way the algo is expressed.
Maintaining jw.inner/outerCount gives clarity to this issue. Can be used for error reporting and behavioral definition. If the roles are not to be trusted, the counts can be adjusted when the geometry is determined.
Ticker
On Wed, 2021-04-07 at 08:57 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. mpInitialLogic.patch: I think I tried the same approach to join the ways in the past. Problem is that the patched code produces rings with an unpredictable start/end and thus random content in RGN. This makes comparisons of two mkgmap outputs much more difficult if not impossable.
The existing algo works quite well if the members are sorted and most complex MP are sorted well enough. I think in the worst case (badly shuffled member list) the algo complexity is probably O(n²) , in the best case it is O(n) where n gives the number of unclosed ways in the member list.
Maybe you find a way to use the HashMap to avoid the sequential search for the next member without adding too much complexity to the current code? Or a simple sort to avoid the worst case? Even with worse cases I don't see more than a few seconds for very complex MP.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, I don't care much about invalid MP so far. It is not allowed that inner ways and outer ways are connected, nor is it allowed that outer rings share segments. So, at the moment that means Garbage in -> Garbage out. There are some special cases more than two outer ways are connected at the same node and there should be a back-tracking algo to combine them in a ways that doesn't produce self intersecting rings. No idea how to implement that. reg. containsMatrix: I did not find any problems with nested polygons so far, but yes, the partitioning is more likely to produce more edge cases. I don't see how a single call of isPointInShape() can be enough. It only helps if it returns OUT, but that is unlikely. If it returns IN the polygons may still be overlapping. I've not yet decided what to do with those MP because the real MP with complete data might be correct and the overlapping could be a result of artifically closed rings. I've just noticed that the branch is sometimes erronously connecting ways which trunk doesn't connect (only with BoundaryRelation). I think it will take a one or two more weeks before this branch is getting stable. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 27. April 2021 15:37 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd I'd have thought using isPointInShape() in combination with polygon areas to be more efficient and robust than isLineInShape() (which makes multiple calls to isPointInShape). Would need to choose a reference point within each polygon, ensuring it is IN but not ON itself. Probably splitShape(), isPointInShape() and calcAreaSize()/calcAreaSizeTestVal() all have very similar costs; linear on number of points. I understand some benefits of splitting a massive outer into multiples polygons, in that a point-IN question might give an quicker answer, but it must introduce a lot of other difficulties with edge cases on the artificial boundaries, etc, etc. Splitting inners shouldn't cause a probem in this respect (just a list of inners), but if there is another outer in the hole, this will become confusing. A couple of other things I meant to mention following earlier faster-mp svn updates: I found cases, as both inner and outer, where adjacent rectangles (eg buildings) are touched together, with either a duplicate or identical member being the dividing wall. I realise that some combinations of this violate OSM MP rules, but, keeping the duplicate, allows this simple "double-touching" structure to be resolved; where there are 4 ways at a node, don't join 2 that are identical or have same other-end and no other points. Joining ways if possible in the initial element iteration and ignoring roles can lead to problems when inner and outer touch. Whereas saving them all in a Map of both ends, before attempting to join, will avoid the problem for single-touching. For double-touching, any roles can be used to join the correct parts. For ordering stability if using a HashMap, could just keep track of lowest element# in joinedWays and always keep this first. Ticker On Mon, 2021-04-26 at 14:17 +0000, Gerd Petermann wrote:
Hi Ticker,
I think I am making progress with my divide&conquer approach. I see ~20 secs instead of more than 7 minutes to process the monster relation r9488835. The basic approach is to use ShapeSplitter.splitShape() multiple times to divide the multipolygon into smaller pieces where no ring has more than 20.000 nodes and executing the block
analyseRelationRoles() ... doReporting() for each piece.
The work is not yet done, the output file is a bit larger, not yet sure why, and the calculation of the "largestOuterPolygon" neads a bit more work. There are probably edge cases where this doesn't work, esp. when inners are very large.
BTW: I found a bug in IsInUtil.isLineInShape() : It sometimes returns ON when it should return IN/ON I think it happens when a ring has start /end node ON and also 2nd or 2nd-last node ON. Probably a special case created by the ShapeSplitter. Attached patch fixes the problem in IsInUtil.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 7. April 2021 13:02 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
Problem is that IdentityHashMap is the ideal solution, but ordering behaviour depends on internal java object handles. A solution to this stability issue would be to rotate joinedWays.originalWays so, say, the one with the lowest ID is first, doing this just before the full point -list is created.
Maybe not worth it if existing logic is not a problem.
Some of the other advantages my logic:
Clearer and more efficient.
Elements are scanned once; cOg and closed polygons are processed immediately. Elements from SeaGenerator are all closed.
Single touching polygons are handled without difficulty; just part of the way the algo is expressed.
Maintaining jw.inner/outerCount gives clarity to this issue. Can be used for error reporting and behavioral definition. If the roles are not to be trusted, the counts can be adjusted when the geometry is determined.
Ticker
On Wed, 2021-04-07 at 08:57 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. mpInitialLogic.patch: I think I tried the same approach to join the ways in the past. Problem is that the patched code produces rings with an unpredictable start/end and thus random content in RGN. This makes comparisons of two mkgmap outputs much more difficult if not impossable.
The existing algo works quite well if the members are sorted and most complex MP are sorted well enough. I think in the worst case (badly shuffled member list) the algo complexity is probably O(n²) , in the best case it is O(n) where n gives the number of unclosed ways in the member list.
Maybe you find a way to use the HashMap to avoid the sequential search for the next member without adding too much complexity to the current code? Or a simple sort to avoid the worst case? Even with worse cases I don't see more than a few seconds for very complex MP.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd Point IN and area should be adequate for determining enclosed/enclosing polygons relationships. Overlapping / intersecting is an error anyway, but, even with badly/arbitrarily closed boundaries, provided the closing takes a similar route around the known mapArea, the area shouldsuffice. Ticker On Tue, 2021-04-27 at 14:23 +0000, Gerd Petermann wrote:
Hi Ticker,
I don't care much about invalid MP so far. It is not allowed that inner ways and outer ways are connected, nor is it allowed that outer rings share segments. So, at the moment that means Garbage in -> Garbage out. There are some special cases more than two outer ways are connected at the same node and there should be a back-tracking algo to combine them in a ways that doesn't produce self intersecting rings. No idea how to implement that.
reg. containsMatrix: I did not find any problems with nested polygons so far, but yes, the partitioning is more likely to produce more edge cases.
I don't see how a single call of isPointInShape() can be enough. It only helps if it returns OUT, but that is unlikely. If it returns IN the polygons may still be overlapping. I've not yet decided what to do with those MP because the real MP with complete data might be correct and the overlapping could be a result of artifically closed rings.
I've just noticed that the branch is sometimes erronously connecting ways which trunk doesn't connect (only with BoundaryRelation).
I think it will take a one or two more weeks before this branch is getting stable.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 27. April 2021 15:37 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
I'd have thought using isPointInShape() in combination with polygon areas to be more efficient and robust than isLineInShape() (which makes multiple calls to isPointInShape). Would need to choose a reference point within each polygon, ensuring it is IN but not ON itself.
Probably splitShape(), isPointInShape() and calcAreaSize()/calcAreaSizeTestVal() all have very similar costs; linear on number of points.
I understand some benefits of splitting a massive outer into multiples polygons, in that a point-IN question might give an quicker answer, but it must introduce a lot of other difficulties with edge cases on the artificial boundaries, etc, etc. Splitting inners shouldn't cause a probem in this respect (just a list of inners), but if there is another outer in the hole, this will become confusing.
A couple of other things I meant to mention following earlier faster -mp svn updates:
I found cases, as both inner and outer, where adjacent rectangles (eg buildings) are touched together, with either a duplicate or identical member being the dividing wall. I realise that some combinations of this violate OSM MP rules, but, keeping the duplicate, allows this simple "double-touching" structure to be resolved; where there are 4 ways at a node, don't join 2 that are identical or have same other -end and no other points.
Joining ways if possible in the initial element iteration and ignoring roles can lead to problems when inner and outer touch. Whereas saving them all in a Map of both ends, before attempting to join, will avoid the problem for single-touching. For double-touching, any roles can be used to join the correct parts. For ordering stability if using a HashMap, could just keep track of lowest element# in joinedWays and always keep this first.
Ticker
On Mon, 2021-04-26 at 14:17 +0000, Gerd Petermann wrote:
Hi Ticker,
I think I am making progress with my divide&conquer approach. I see ~20 secs instead of more than 7 minutes to process the monster relation r9488835. The basic approach is to use ShapeSplitter.splitShape() multiple times to divide the multipolygon into smaller pieces where no ring has more than 20.000 nodes and executing the block
analyseRelationRoles() ... doReporting() for each piece.
The work is not yet done, the output file is a bit larger, not yet sure why, and the calculation of the "largestOuterPolygon" neads a bit more work. There are probably edge cases where this doesn't work, esp. when inners are very large.
BTW: I found a bug in IsInUtil.isLineInShape() : It sometimes returns ON when it should return IN/ON I think it happens when a ring has start /end node ON and also 2nd or 2nd-last node ON. Probably a special case created by the ShapeSplitter. Attached patch fixes the problem in IsInUtil.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 7. April 2021 13:02 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
Problem is that IdentityHashMap is the ideal solution, but ordering behaviour depends on internal java object handles. A solution to this stability issue would be to rotate joinedWays.originalWays so, say, the one with the lowest ID is first, doing this just before the full point -list is created.
Maybe not worth it if existing logic is not a problem.
Some of the other advantages my logic:
Clearer and more efficient.
Elements are scanned once; cOg and closed polygons are processed immediately. Elements from SeaGenerator are all closed.
Single touching polygons are handled without difficulty; just part of the way the algo is expressed.
Maintaining jw.inner/outerCount gives clarity to this issue. Can be used for error reporting and behavioral definition. If the roles are not to be trusted, the counts can be adjusted when the geometry is determined.
Ticker
On Wed, 2021-04-07 at 08:57 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. mpInitialLogic.patch: I think I tried the same approach to join the ways in the past. Problem is that the patched code produces rings with an unpredictable start/end and thus random content in RGN. This makes comparisons of two mkgmap outputs much more difficult if not impossable.
The existing algo works quite well if the members are sorted and most complex MP are sorted well enough. I think in the worst case (badly shuffled member list) the algo complexity is probably O(n²) , in the best case it is O(n) where n gives the number of unclosed ways in the member list.
Maybe you find a way to use the HashMap to avoid the sequential search for the next member without adding too much complexity to the current code? Or a simple sort to avoid the worst case? Even with worse cases I don't see more than a few seconds for very complex MP.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, I did a few tests with a tile in Zambia that contains some complex multipolygons and nestings. No 1) disable partitioning 2) disable partitioning and skip isLineInShape() test if center of geometry of the inner is IN for inner AND outer 3) use code in branch as is (enabled partitioning) 4) enable partitioning and skip isLineInShape() test if center of geometry of the inner is IN for inner AND outer Times for the compilation of the tile are 39 secs for 1) 32 secs for 2) 4 secs for 3) and 4) With 3) and 4) I see only ~2 secs for the "processing MP relation" part, so it would require more complex relations to see improvements with 4) If you know a quick and stable and simple method to find a point that is IN please let me know and I do some more testing. The getCofG() only works well for convex polygons. For around 3 percent of the polygons in my tests getCofG() returns a point outside of the polygon, and those polygons are likely more complex. I've also done some tests with PrecompSeaGenerator and the complex tile sea_2752512_851968.osm.pbf Results are more or less equal for all 4 methods, the processing of the generated MP takes ~20 secs, only ~2 secs are used in createContainsMatrix() and ~18 secs are used in MultipolygonCutter At the moment I try to decide what to do with incomplete data. I see three different situations with incomplete relations: 1) BoundaryPreprocessor is used with a country extract or maybe the combination of multiple extracts from geofabrik or other sources. In this case I tend to think that we can either ignore incomplete data completely or we might use the *.poly file(s) that were used to cut the data to "close the boundary polygon along the cutting polygon". The latter might help to avoid situations where the LocationHook returns no info for points outside of the cutting polygon. 2) mkgmap is used with splitter data and splitter was used with --keep-complete=false In this case lots of multipolygons are incomplete, esp. those near the tile boundary. We MUST do some guessing about the missing data, else the maps are more or less unusable because large wood or lake areas wood be missing. 3) mkgmap is used with splitter data and splitter was used with --keep-complete=true In this case we see incomplete MP when the country extract was already incomplete or with those MP that splitter doesn't keep complete. It's hard to say if we can ignore those incomplete MP or not. Most of them are boundaries. The default style doesn't render any boundary as polygon, but other styles do, e.g. the OpenFietsMap styles. Maybe a simple new option "--ignore-incomplete-data" could improve performance. This would be easy to implement. A much more complex solution would be a new hook that is called directly before the processElements() call. It would use a new rule file similar to relations and could set special tags to tell mkgmap if it should calculate the areas of the multipolygon or just handle the outlines to produce the mkgmap:stylefilter=polyline ways. Just an idea so far. The current code only tries to use the "tile boundary" to complete data. I think it would be better to use the cutting polygon. I started to experiment with that but found out that many *.poly files from geofabrik intersect with the country borders which are expected to be fully inside. I contacted them about this and Frederick Ramm confirmed that they want to fix that. ciao, Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 27. April 2021 18:09 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate Hi Gerd Point IN and area should be adequate for determining enclosed/enclosing polygons relationships. Overlapping / intersecting is an error anyway, but, even with badly/arbitrarily closed boundaries, provided the closing takes a similar route around the known mapArea, the area shouldsuffice. Ticker On Tue, 2021-04-27 at 14:23 +0000, Gerd Petermann wrote:
Hi Ticker,
I don't care much about invalid MP so far. It is not allowed that inner ways and outer ways are connected, nor is it allowed that outer rings share segments. So, at the moment that means Garbage in -> Garbage out. There are some special cases more than two outer ways are connected at the same node and there should be a back-tracking algo to combine them in a ways that doesn't produce self intersecting rings. No idea how to implement that.
reg. containsMatrix: I did not find any problems with nested polygons so far, but yes, the partitioning is more likely to produce more edge cases.
I don't see how a single call of isPointInShape() can be enough. It only helps if it returns OUT, but that is unlikely. If it returns IN the polygons may still be overlapping. I've not yet decided what to do with those MP because the real MP with complete data might be correct and the overlapping could be a result of artifically closed rings.
I've just noticed that the branch is sometimes erronously connecting ways which trunk doesn't connect (only with BoundaryRelation).
I think it will take a one or two more weeks before this branch is getting stable.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Dienstag, 27. April 2021 15:37 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
I'd have thought using isPointInShape() in combination with polygon areas to be more efficient and robust than isLineInShape() (which makes multiple calls to isPointInShape). Would need to choose a reference point within each polygon, ensuring it is IN but not ON itself.
Probably splitShape(), isPointInShape() and calcAreaSize()/calcAreaSizeTestVal() all have very similar costs; linear on number of points.
I understand some benefits of splitting a massive outer into multiples polygons, in that a point-IN question might give an quicker answer, but it must introduce a lot of other difficulties with edge cases on the artificial boundaries, etc, etc. Splitting inners shouldn't cause a probem in this respect (just a list of inners), but if there is another outer in the hole, this will become confusing.
A couple of other things I meant to mention following earlier faster -mp svn updates:
I found cases, as both inner and outer, where adjacent rectangles (eg buildings) are touched together, with either a duplicate or identical member being the dividing wall. I realise that some combinations of this violate OSM MP rules, but, keeping the duplicate, allows this simple "double-touching" structure to be resolved; where there are 4 ways at a node, don't join 2 that are identical or have same other -end and no other points.
Joining ways if possible in the initial element iteration and ignoring roles can lead to problems when inner and outer touch. Whereas saving them all in a Map of both ends, before attempting to join, will avoid the problem for single-touching. For double-touching, any roles can be used to join the correct parts. For ordering stability if using a HashMap, could just keep track of lowest element# in joinedWays and always keep this first.
Ticker
On Mon, 2021-04-26 at 14:17 +0000, Gerd Petermann wrote:
Hi Ticker,
I think I am making progress with my divide&conquer approach. I see ~20 secs instead of more than 7 minutes to process the monster relation r9488835. The basic approach is to use ShapeSplitter.splitShape() multiple times to divide the multipolygon into smaller pieces where no ring has more than 20.000 nodes and executing the block
analyseRelationRoles() ... doReporting() for each piece.
The work is not yet done, the output file is a bit larger, not yet sure why, and the calculation of the "largestOuterPolygon" neads a bit more work. There are probably edge cases where this doesn't work, esp. when inners are very large.
BTW: I found a bug in IsInUtil.isLineInShape() : It sometimes returns ON when it should return IN/ON I think it happens when a ring has start /end node ON and also 2nd or 2nd-last node ON. Probably a special case created by the ShapeSplitter. Attached patch fixes the problem in IsInUtil.
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 7. April 2021 13:02 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] tile takes very long time to generate
Hi Gerd
Problem is that IdentityHashMap is the ideal solution, but ordering behaviour depends on internal java object handles. A solution to this stability issue would be to rotate joinedWays.originalWays so, say, the one with the lowest ID is first, doing this just before the full point -list is created.
Maybe not worth it if existing logic is not a problem.
Some of the other advantages my logic:
Clearer and more efficient.
Elements are scanned once; cOg and closed polygons are processed immediately. Elements from SeaGenerator are all closed.
Single touching polygons are handled without difficulty; just part of the way the algo is expressed.
Maintaining jw.inner/outerCount gives clarity to this issue. Can be used for error reporting and behavioral definition. If the roles are not to be trusted, the counts can be adjusted when the geometry is determined.
Ticker
On Wed, 2021-04-07 at 08:57 +0000, Gerd Petermann wrote:
Hi Ticker,
reg. mpInitialLogic.patch: I think I tried the same approach to join the ways in the past. Problem is that the patched code produces rings with an unpredictable start/end and thus random content in RGN. This makes comparisons of two mkgmap outputs much more difficult if not impossable.
The existing algo works quite well if the members are sorted and most complex MP are sorted well enough. I think in the worst case (badly shuffled member list) the algo complexity is probably O(n²) , in the best case it is O(n) where n gives the number of unclosed ways in the member list.
Maybe you find a way to use the HashMap to avoid the sequential search for the next member without adding too much complexity to the current code? Or a simple sort to avoid the worst case? Even with worse cases I don't see more than a few seconds for very complex MP.
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd I'm away at moment, without full access to sources, so can't follow the current progress with partitioning, etc. Regarding finding a point IN (and not ON) polygon: 1/ Try bounds center. 2/ Assumed determined [counter-]clockwise from area calculation. Pick 3 sequential points, bisect the angle and go in along this line by a small multiple of IsInUtil.EPS[_HP] and try this point. 3/ Move around by one and try again. 4/ If get back to the start, the polygon must be so thin that cannot contain another polygon. Take any Point and hope that this isn't ON more than possible outer Ticker On Thu, 2021-04-29 at 08:31 +0000, Gerd Petermann wrote:
Hi Ticker,
I did a few tests with a tile in Zambia that contains some complex multipolygons and nestings. No 1) disable partitioning 2) disable partitioning and skip isLineInShape() test if center of geometry of the inner is IN for inner AND outer 3) use code in branch as is (enabled partitioning) 4) enable partitioning and skip isLineInShape() test if center of geometry of the inner is IN for inner AND outer
Times for the compilation of the tile are 39 secs for 1) 32 secs for 2) 4 secs for 3) and 4)
With 3) and 4) I see only ~2 secs for the "processing MP relation" part, so it would require more complex relations to see improvements with 4)
If you know a quick and stable and simple method to find a point that is IN please let me know and I do some more testing. The getCofG() only works well for convex polygons. For around 3 percent of the polygons in my tests getCofG() returns a point outside of the polygon, and those polygons are likely more complex.
I've also done some tests with PrecompSeaGenerator and the complex tile sea_2752512_851968.osm.pbf Results are more or less equal for all 4 methods, the processing of the generated MP takes ~20 secs, only ~2 secs are used in createContainsMatrix() and ~18 secs are used in MultipolygonCutter
At the moment I try to decide what to do with incomplete data. I see three different situations with incomplete relations: 1) BoundaryPreprocessor is used with a country extract or maybe the combination of multiple extracts from geofabrik or other sources. In this case I tend to think that we can either ignore incomplete data completely or we might use the *.poly file(s) that were used to cut the data to "close the boundary polygon along the cutting polygon". The latter might help to avoid situations where the LocationHook returns no info for points outside of the cutting polygon. 2) mkgmap is used with splitter data and splitter was used with - -keep-complete=false In this case lots of multipolygons are incomplete, esp. those near the tile boundary. We MUST do some guessing about the missing data, else the maps are more or less unusable because large wood or lake areas wood be missing. 3) mkgmap is used with splitter data and splitter was used with - -keep-complete=true In this case we see incomplete MP when the country extract was already incomplete or with those MP that splitter doesn't keep complete. It's hard to say if we can ignore those incomplete MP or not. Most of them are boundaries. The default style doesn't render any boundary as polygon, but other styles do, e.g. the OpenFietsMap styles.
Maybe a simple new option "--ignore-incomplete-data" could improve performance. This would be easy to implement. A much more complex solution would be a new hook that is called directly before the processElements() call. It would use a new rule file similar to relations and could set special tags to tell mkgmap if it should calculate the areas of the multipolygon or just handle the outlines to produce the mkgmap:stylefilter=polyline ways. Just an idea so far.
The current code only tries to use the "tile boundary" to complete data. I think it would be better to use the cutting polygon. I started to experiment with that but found out that many *.poly files from geofabrik intersect with the country borders which are expected to be fully inside. I contacted them about this and Frederick Ramm confirmed that they want to fix that.
ciao, Gerd
participants (6)
-
7770 -
Bernhard Hiller -
Dave -
Gerd Petermann -
Mike Baggaley -
Ticker Berkin