[mp: PATCH] Multipolygon handling - decomposed polygons
I have made some improvements to the multipolygon branch. Changes: * Polygons with inner polygons are now divided into several polygons. It's much faster and the PolygonSplitter cannot destroy them any more. * Improved tag handling. The tags from original ways are removed. This has the disadvantage that non polygon tags like highway are destroyed. This must be fixed within one of the next patches. * Added a FakeIdGenerator that creates unique fake ids for elements created by mkgmap. The Osm5XmlHandler has been adapted to that. As before I am happy about any (good and bad) feedback!! WanMil Note: The code is not ready for the trunk. Some documentation and better method naming will be applied in one of the next patch.
Well speed seems improved... however "lake Neusidel" / "Neusiedler See" in Austria is now "empty" in some places where before it was filled with water. In general it seems to be working great (and very quick). Of course missing the ways makes it not production ready yet. On 07.01.2010 23:39, WanMil wrote:
I have made some improvements to the multipolygon branch.
Changes: * Polygons with inner polygons are now divided into several polygons. It's much faster and the PolygonSplitter cannot destroy them any more. * Improved tag handling. The tags from original ways are removed. This has the disadvantage that non polygon tags like highway are destroyed. This must be fixed within one of the next patches. * Added a FakeIdGenerator that creates unique fake ids for elements created by mkgmap. The Osm5XmlHandler has been adapted to that.
As before I am happy about any (good and bad) feedback!! WanMil
Note: The code is not ready for the trunk. Some documentation and better method naming will be applied in one of the next patch.
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Lake Neusidel in Austria is divided by the country border to Hungary. Therefore I suppose it is not completely contained in the OSM file. At the moment the algorithm is very strict with discarding non closed ways. This has to be addressed in one of the next versions. WanMil
Well speed seems improved...
however "lake Neusidel" / "Neusiedler See" in Austria is now "empty" in some places where before it was filled with water. In general it seems to be working great (and very quick). Of course missing the ways makes it not production ready yet.
On 07.01.2010 23:39, WanMil wrote:
I have made some improvements to the multipolygon branch.
Changes: * Polygons with inner polygons are now divided into several polygons. It's much faster and the PolygonSplitter cannot destroy them any more. * Improved tag handling. The tags from original ways are removed. This has the disadvantage that non polygon tags like highway are destroyed. This must be fixed within one of the next patches. * Added a FakeIdGenerator that creates unique fake ids for elements created by mkgmap. The Osm5XmlHandler has been adapted to that.
As before I am happy about any (good and bad) feedback!! WanMil
Note: The code is not ready for the trunk. Some documentation and better method naming will be applied in one of the next patch.
_______________________________________________ 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
however "lake Neusidel" / "Neusiedler See" in Austria is now "empty" in some places where before it was filled with water.
I have compared the trunk to the the mp branch with the Austria dump from http://download.geofabrik.de/osm/europe/. Trunk: "lake Neusiedel" is completely empty. No water at all. Only some puddles. mp: "lake Neusiedel" is filled with water. Only some parts in the south are empty and some of the southern islands are inverted and flodded with water. This can be easily fixed in mulitpolygon code. WanMil
Changes: * Polygons with inner polygons are now divided into several polygons. It's much faster and the PolygonSplitter cannot destroy them any more.
Hello WanMil, this change could have some other side effects. (As observed and described in another thread) If the polygons gets small enough, then the SizeFilter will remove parts of them. I.e. if a big forrest gets cut into smaller pieces, some of them may be small enough to be catched by the SizeFilter. Is it a must for splitting them up? Or was it just done to serve the PolygonSplitter? Regards, Johann
Am 09.01.2010 00:05, schrieb Johann Gail:
Changes: * Polygons with inner polygons are now divided into several polygons. It's much faster and the PolygonSplitter cannot destroy them any more.
Hello WanMil,
this change could have some other side effects. (As observed and described in another thread) If the polygons gets small enough, then the SizeFilter will remove parts of them. I.e. if a big forrest gets cut into smaller pieces, some of them may be small enough to be catched by the SizeFilter.
Is it a must for splitting them up? Or was it just done to serve the PolygonSplitter?
Regards, Johann
Johann, the old findCpa method was quite slow. Its complexity is O(n^3) at its worsty worst case and usually O(n^2). Therefore I started to implement the new algorithm without the findCpa method. The current implementation may have problems with small polygons but it should be possible to perform some remerging. Another idea is to add some specific tags by the mulitpolygon algorithm that link to the other pieces of the formerly big forrest. This could be evaluated by the SizeFilter? WanMil
On 09.01.2010 10:08, WanMil wrote:
Am 09.01.2010 00:05, schrieb Johann Gail:
Changes: * Polygons with inner polygons are now divided into several polygons. It's much faster and the PolygonSplitter cannot destroy them any more.
Hello WanMil,
this change could have some other side effects. (As observed and described in another thread) If the polygons gets small enough, then the SizeFilter will remove parts of them. I.e. if a big forrest gets cut into smaller pieces, some of them may be small enough to be catched by the SizeFilter.
Is it a must for splitting them up? Or was it just done to serve the PolygonSplitter?
Regards, Johann
Johann,
the old findCpa method was quite slow. Its complexity is O(n^3) at its worsty worst case and usually O(n^2).
Therefore I started to implement the new algorithm without the findCpa method. The current implementation may have problems with small polygons but it should be possible to perform some remerging.
Another idea is to add some specific tags by the mulitpolygon algorithm that link to the other pieces of the formerly big forrest. This could be evaluated by the SizeFilter?
That would be good. Another thing would be to implement a variable setting for Multipolygon inner cutouts based on type (put it into the style-file). I think on resolution 24 and 23 it is clear that we want to have multipolygon inner cutout. In 22 I am not to sure. From 21 down I would prefer only lakes and sea to make use of inner, but all other objects to be displayed as if there was only the outer. That should be added to style-file like "mp 22" meaning 22 is the last resolution were inner polygons are cut out.
WanMil _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
On 01/09/2010 10:08 AM, WanMil wrote:
Another idea is to add some specific tags by the mulitpolygon algorithm that link to the other pieces of the formerly big forrest. This could be evaluated by the SizeFilter?
Another idea (don't know if this is possible): You have a big multipolygon forest. You could duplicate it. One copy without small inner polygons for the low resolutions. Another copy with the inner polygons which gets splitted for the higher resolutions. The copies could be marked with some mkgmap internal tag and used later.
Am 09.01.2010 11:25, schrieb Ralf Kleineisel:
On 01/09/2010 10:08 AM, WanMil wrote:
Another idea is to add some specific tags by the mulitpolygon algorithm that link to the other pieces of the formerly big forrest. This could be evaluated by the SizeFilter?
Another idea (don't know if this is possible):
You have a big multipolygon forest. You could duplicate it. One copy without small inner polygons for the low resolutions. Another copy with the inner polygons which gets splitted for the higher resolutions. The copies could be marked with some mkgmap internal tag and used later.
That should be no problem for the mulitpolygon code. But I need someone who can modify the style handling. What about POI searches? If we have multiple versions of the famous Wienerwald the search for forrests should return only one version.
AFAIK the POI searches work only with the actual POIs that are generated, not the polygons. So this should be no big problem. You should make sure though that the --add-pois-to-areas option doesn't generate the POIs twice. Regards Thilo Am 09.01.2010 um 11:56 schrieb WanMil:
Am 09.01.2010 11:25, schrieb Ralf Kleineisel:
On 01/09/2010 10:08 AM, WanMil wrote:
Another idea is to add some specific tags by the mulitpolygon algorithm that link to the other pieces of the formerly big forrest. This could be evaluated by the SizeFilter?
Another idea (don't know if this is possible):
You have a big multipolygon forest. You could duplicate it. One copy without small inner polygons for the low resolutions. Another copy with the inner polygons which gets splitted for the higher resolutions. The copies could be marked with some mkgmap internal tag and used later.
That should be no problem for the mulitpolygon code. But I need someone who can modify the style handling.
What about POI searches? If we have multiple versions of the famous Wienerwald the search for forrests should return only one version.
Is there any mkgmap tag yet to avoid this? (like mkgmap:noaddpoitoarea=yes) WanMil
AFAIK the POI searches work only with the actual POIs that are generated, not the polygons. So this should be no big problem. You should make sure though that the --add-pois-to-areas option doesn't generate the POIs twice.
Regards Thilo
Am 09.01.2010 um 11:56 schrieb WanMil:
Am 09.01.2010 11:25, schrieb Ralf Kleineisel:
On 01/09/2010 10:08 AM, WanMil wrote:
Another idea is to add some specific tags by the mulitpolygon algorithm that link to the other pieces of the formerly big forrest. This could be evaluated by the SizeFilter?
Another idea (don't know if this is possible):
You have a big multipolygon forest. You could duplicate it. One copy without small inner polygons for the low resolutions. Another copy with the inner polygons which gets splitted for the higher resolutions. The copies could be marked with some mkgmap internal tag and used later.
That should be no problem for the mulitpolygon code. But I need someone who can modify the style handling.
What about POI searches? If we have multiple versions of the famous Wienerwald the search for forrests should return only one version.
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
On Jan 9, 2010, at 12:41, WanMil wrote:
Is there any mkgmap tag yet to avoid this? (like mkgmap:noaddpoitoarea=yes)
POI generation from areas is disabled by default. Command line option --add-pois-to-areas enables this. Further, POIs will only be generated from areas if there is a corresponding entry in the points style file. Cheers
Ralf Kleineisel schrieb:
On 01/09/2010 10:08 AM, WanMil wrote:
Another idea is to add some specific tags by the mulitpolygon algorithm that link to the other pieces of the formerly big forrest. This could be evaluated by the SizeFilter?
Another idea (don't know if this is possible):
You have a big multipolygon forest. You could duplicate it. One copy without small inner polygons for the low resolutions. Another copy with the inner polygons which gets splitted for the higher resolutions. The copies could be marked with some mkgmap internal tag and used later.
May I propose to move the whole multipolygon handling to the filter chain? Then there is _no need_ for additional tags and duplicated polygons and possible remerging of them. The filter chain is run for each resolution level. With each run the poylgons could be handled accordingly. I don't think, your ideas are wrong. I appreciate your work. But I think its made more complicated than actually needed.
Ralf Kleineisel schrieb:
On 01/09/2010 10:08 AM, WanMil wrote:
Another idea is to add some specific tags by the mulitpolygon algorithm that link to the other pieces of the formerly big forrest. This could be evaluated by the SizeFilter?
Another idea (don't know if this is possible):
You have a big multipolygon forest. You could duplicate it. One copy without small inner polygons for the low resolutions. Another copy with the inner polygons which gets splitted for the higher resolutions. The copies could be marked with some mkgmap internal tag and used later.
May I propose to move the whole multipolygon handling to the filter chain? Then there is _no need_ for additional tags and duplicated polygons and possible remerging of them. The filter chain is run for each resolution level. With each run the poylgons could be handled accordingly.
I don't think, your ideas are wrong. I appreciate your work. But I think its made more complicated than actually needed.
Interesting idea! I am not very deep in the filter things, so please let me know if I am on the complete wrong way. Some thoughts about moving mulitpolygon handling to the filter chain: * Computation time for multipolygon handling will be multiplied by the number of resolutions. Probably this is ok as the current implementation seems to be quite quick. * At which point should the multipolygon filter run? This might be a problem. Example: 1st - before the SizeFilter: As before the mp code splits large polygons to smaller pieces that might be removed by size filter (or the dp filter?) 2nd - after the SizeFilter: The size filter removes small lines(?) and polygons that otherwise would be composed to larger polygons by the mp code. Mmh, 1st solution seems to be ok. In low resolutions mp code only cuts out large inner holes. In this case it shouldn't matter if some small pieces are cut from the large outer polygon. WanMil
Another idea (don't know if this is possible):
You have a big multipolygon forest. You could duplicate it. One copy without small inner polygons for the low resolutions. Another copy with the inner polygons which gets splitted for the higher resolutions. The copies could be marked with some mkgmap internal tag and used later.
May I propose to move the whole multipolygon handling to the filter chain? Then there is _no need_ for additional tags and duplicated polygons and possible remerging of them. The filter chain is run for each resolution level. With each run the poylgons could be handled accordingly.
I don't think, your ideas are wrong. I appreciate your work. But I think its made more complicated than actually needed.
Interesting idea!
I am not very deep in the filter things, so please let me know if I am on the complete wrong way. Some thoughts about moving mulitpolygon handling to the filter chain:
* Computation time for multipolygon handling will be multiplied by the number of resolutions. Probably this is ok as the current implementation seems to be quite quick.
This is true. So maybe you should only move the splitting task to the filter chain and not the multipolygon handling. This would however mean that the multipolygon handling is done for all levels and it would not be possible to take at different levels the polygon without holes.
* At which point should the multipolygon filter run? This might be a problem. Example: 1st - before the SizeFilter: As before the mp code splits large polygons to smaller pieces that might be removed by size filter (or the dp filter?)
I dont think the dp filter does remove anything as whole. It removes single points from the polygon thereby make nearly straight lines exactly straight.
2nd - after the SizeFilter: The size filter removes small lines(?) and polygons that otherwise would be composed to larger polygons by the mp code.
For your information: There are two diferent filter chains. One for lines (ways, etc. ) and one for polygons. Both of them uses instances of SizeFilter, PolygonSplitter, etc. with different settings. So the filter chain for polygons will never remove small lines. What do you mean by mo code composign larger polygons? As far as I understand the thing, it combines an outer poylgon with an inner polygon to a poygon with an hole. But by definition the inner polygon has to be always smaller than the outer polygon. (BTW: What happens, if this is not the case, caused by wrong osm data??) So what will happen? If the inner polygon is small enough, then it will not be stamped out. This seems okay to me. If both of them are filtered out, then its ok too.
Mmh, 1st solution seems to be ok. In low resolutions mp code only cuts out large inner holes. In this case it shouldn't matter if some small pieces are cut from the large outer polygon.
I think, 1st solution is exactly what we have now?? mp code is exectued before filter chain and therefore before size filter. I would prefer strongly 2nd solution. With this even small polygons are deleted before they are cut out from the bigger one. But I see a technical problem arise: In the filter chain there aren't any more tags or other information on how polygons are connected. There are only the raw polygon objects with coordinate data. The whole process of mkgmap is a two stage process. First the osm data (or mp data) gets parsed and imported into internal objects. While parsing more ore less complicated filtering/merging/sorting/generating of pois/cleanup of the osm data is done. This is the stage where you are working at the moment with your multipolygon code. At the end of it, there should be a cleaned representation of the map with independent objects. In the second stage this objects needs to be transfered into the garmin img format and the different levels. There are some limitations in the format, e.g. a polygon could not have more than 250 points. So it has to be splitted. And at very low zooms you cant all details of the polygon. So it could be simplified by the dp filter to save resources. In my very private opinion the multipolygon handling should be done in the first stage, at it is now, and the splitting should be done in the filter chain after size and dp filter. But I see, that this could be problematic, as the splitting has given some performance boost to the MP code, so it will not be easy to extract this part of it. Hmm, more thinking required... Regards, Johann
WanMil _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev .
Johann, thank you for you good explanations to the filter chain. It gives me a good overview how it works!
What do you mean by mo code composign larger polygons? As far as I understand the thing, it combines an outer poylgon with an inner polygon to a poygon with an hole. But by definition the inner polygon has to be always smaller than the outer polygon. (BTW: What happens, if this is not the case, caused by wrong osm data??)
Oh, I was wrong. Polygons are not composed to larger polygons. Single unclosed lines are composed to polygons. The error case: If the inner polygon touches or cuts the outer polygon nothing is done so far. Only a warning message is issued. This might be changed in future, so that the area of the inner polygon is removed from the outer polygon.
So what will happen? If the inner polygon is small enough, then it will not be stamped out. This seems okay to me. If both of them are filtered out, then its ok too.
Mmh, 1st solution seems to be ok. In low resolutions mp code only cuts out large inner holes. In this case it shouldn't matter if some small pieces are cut from the large outer polygon.
I think, 1st solution is exactly what we have now??
Not exactly. The current mp code removes tags from the single ways that are composed to polygons. While I am writing these lines I get the idea that I should change that. If a way has polygon tags they will not be used (is that right?). But if it has way related tags like highway=unclassified they are used and are missing if I am removing them.
But I see a technical problem arise: In the filter chain there aren't any more tags or other information on how polygons are connected. There are only the raw polygon objects with coordinate data.
Do you mean the multipolygon information which polygons belong to the mulitpolygon relation is not available? Or do you mean that there are no tags (like natural=forest) available?
In my very private opinion the multipolygon handling should be done in the first stage, at it is now, and the splitting should be done in the filter chain after size and dp filter. But I see, that this could be problematic, as the splitting has given some performance boost to the MP code, so it will not be easy to extract this part of it.
Extracting this part should not be the problem. But I cannot say anything about performance. This has to be tested. At the moment I will try to finish the mp code where it is. This should improve the situation very much compared to the current trunk. After that we can start to move the splitting code to the filter chain which sounds like a good idea. WanMil
But I see a technical problem arise: In the filter chain there aren't any more tags or other information on how polygons are connected. There are only the raw polygon objects with coordinate data.
Do you mean the multipolygon information which polygons belong to the mulitpolygon relation is not available? Or do you mean that there are no tags (like natural=forest) available?
At this stage there are no tags and not relations. This information has gone. It is converted to single independent polygons which should be displayed in the map. They are represented as java objects of given type (MapLine?, MapArea? Sorry, haven't the correct names in mind) This elements have only information of how to be encoded in garmin types.
In my very private opinion the multipolygon handling should be done in the first stage, at it is now, and the splitting should be done in the filter chain after size and dp filter. But I see, that this could be problematic, as the splitting has given some performance boost to the MP code, so it will not be easy to extract this part of it.
Extracting this part should not be the problem. But I cannot say anything about performance. This has to be tested.
At the moment I will try to finish the mp code where it is. This should improve the situation very much compared to the current trunk.
I agree with you.
After that we can start to move the splitting code to the filter chain which sounds like a good idea.
I think Steve is right with his suggestion to introduce a new map element 'multipolygon'. This seems to be a reasonable way. Regards, Johann
Hi When mkgmap was started relations had not been invented and so I think it is very valid to re-think the processing steps and data structures. Mkgmap is separated in three layers: 1. The reader layer (package ..mkgmap.reader.osm) which deals in concepts from osm such as nodes/ways/relations etc. 2. There is the general intermediate layer, which is a full detail idealised representation of the map (package ..mkgmap.general) from which the individual map layers are derived. 3. The actual Garmin map layers and elements (packages under imgfmt). I would suggest that we are missing a multi-polygon element in the general package. So instead of converting to the final garmin format too early on, keep the full multi-polygon (with separate inner and outer parts). The filter stages would then not need to deal with artefacts such as cuts between the inner and outer polygons. The cuts would then get added when you finally convert to the img format elements. As this is done for each layer separately you could then handle cases where you want to suppress the inner polygons altogether (because they would be too small for example) more easily as you would just drop it and create the outer polygon(s). ..Steve
participants (7)
-
Clinton Gladstone -
Felix Hartmann -
Johann Gail -
Ralf Kleineisel -
Steve Ratcliffe -
Thilo Hannemann -
WanMil