Hi all, since a few days I am trying to find out why I see so many white stripes in the sea in the screenshots provided by Klaus: http://gis.19327.n5.nabble.com/Norway-not-buildable-with-the-no-trim-option-... I am able to reproduce the problem and I see the same white lines in QLandkarte GT. Depending on the zoom level the white areas disappear or change to small white lines, so I assume it has to do with rounding. I tried all kinds of parameters to reduce these errors, but without success. My question: Are these errors normal? Gerd -- View this message in context: http://gis.19327.n5.nabble.com/White-stripes-in-the-sea-tp5742281.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
On Wed, Jan 02, 2013 at 06:24:17AM -0800, GerdP wrote:
Are these errors normal?
I would say yes. When using generate-sea=polygons, mkgmap will make a 'jigsaw puzzle' around each island in the natural=coastline polygon, using horizontal and vertical lines. Perhaps it could try to minimize the length of the lines, by using diagonal lines, attaching the islands to each other as a tree or graph, instead of attaching each island to the coastline. Marko
Marko Mäkelä wrote
On Wed, Jan 02, 2013 at 06:24:17AM -0800, GerdP wrote:
Are these errors normal?
I would say yes. When using generate-sea=polygons, mkgmap will make a 'jigsaw puzzle' around each island in the natural=coastline polygon, using horizontal and vertical lines. Perhaps it could try to minimize the length of the lines, by using diagonal lines, attaching the islands to each other as a tree or graph, instead of attaching each island to the coastline.
oh, yes, I see this also in the precompiled sea tiles. It tends to creates ways that describe thin areas. Any rounding of these thin areas can lead to empty areas which are then thrown away. I'll try to find a better solution for that. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/White-stripes-in-the-sea-tp5742281p5742312.ht... Sent from the Mkgmap Development mailing list archive at Nabble.com.
On Wed, Jan 02, 2013 at 06:24:17AM -0800, GerdP wrote:
Are these errors normal?
I would say yes. When using generate-sea=polygons, mkgmap will make a 'jigsaw puzzle' around each island in the natural=coastline polygon, using horizontal and vertical lines. Perhaps it could try to minimize the length of the lines, by using diagonal lines, attaching the islands to each other as a tree or graph, instead of attaching each island to the coastline.
Marko
Marko, I am quite sure you mixup generate-sea=polygons with generate-sea=multipolygon. When using the polygon variant mkgmap creates a big sea rectangle covering the whole tile tagged with natural=sea and adds additionally all land polygons tagged with natural=land. So the land polygons covers the sea "background". You should not see any white line using this variant. The disadvantage is that you have a sea background so under each land polygon you also have a sea polygon. When using generate-sea=multipolygon the land and sea areas are distinct because the sea and land areas are built up by one big multipolygon. And mkgmap cuts out the inner (land) parts by cutting the outer polygon into two halves by a horizontal or vertical cut. The mp algorithm favours cuts at multiples of 2^n which improved the artefacts. Of course the whole algorithm can be improved but I didn't find a better solution which does not result in *very* *very* long calculations. But that does not mean that someone else won't find a better solution. Some ideas: 1. Double short cut An inner polygons could be cut out by adding the same short short twice to the outer polygon. I try some ASCII art: MP looks like (o = outer, i = inner) ooooooooooooooooo o o o o o iiii o o i i o o iiii ooo o o o o ooooooooooooooo Then we can add a short cut from o to i by adding the short cut and the lines of i to o. So o is going around i. ooooooooooooooooo o o o oooooo o o oiiiio o ooooi io o ooooiiiio ooo o oooooo o o o ooooooooooooooo Up to now this doesn't work because all filters that are applied later use the java.awt.geom.Area class to cut polygons into two halves. And the Area class removes the short cut. So if the usage of Area could be removed this would be a possible solution (although I haven' tried if it looks better...) 2. Better multipolygon cuts Instead of cutting the multipolygon by a complete vertical or horizontal cut one could cut out a short corner. ooooooooooooooooo o o o o oo o ooooiiii o o i i o o iiii ooo o o o o ooooooooooooooo So as a result: When you want to remove the sea artefacts you must improve the multipolygon cutting. WanMil
On Wed, Jan 02, 2013 at 07:47:22PM +0100, WanMil wrote:
I am quite sure you mixup generate-sea=polygons with generate-sea=multipolygon.
Right, I am sorry about that. I have always used generate-sea=multipolygon (well, since March 2010).
Of course the whole algorithm can be improved but I didn't find a better solution which does not result in *very* *very* long calculations.
Right. I guess that there could be some heuristics, with some reasonable threshold values so that the calculation time does not explode (and some artifacts will remain). An example: To cut out a group of islands from a multipolygon, split the outer polygon between the islands if the islands are close enough to each other. This would of course require some search index to be efficient. The proximity of the inner polygons could be computed based on a spatial index of some 'center of gravity' points, to save some memory. Once a pair of 'close' polygons is found, the nearest point of each polygon would be determined and the line would be cut between these nearest points.
2. Better multipolygon cuts Instead of cutting the multipolygon by a complete vertical or horizontal cut one could cut out a short corner.
Perhaps this could be combined with the above idea. But, I guess that some experiments would be needed to determine if the artefacts get better or worse with the more flexible cuts. Marko
Hi WanMil, WanMil wrote
So as a result: When you want to remove the sea artefacts you must improve the multipolygon cutting.
just to make sure: I already see the small stripes in the precompiled sea tile when I open it in JOSM: (after converting to xml format) sea.png <http://gis.19327.n5.nabble.com/file/n5742357/sea.png> I think the multipolygons algorithm just adds these ways, it doesn't combine them to one area which is then "destroyed" by the polygon split algorithm. So, the question for me is : Could we change the PrecompSeaGenerator or would it help to recombine the areas after reading the preocompiled sea files? Gerd -- View this message in context: http://gis.19327.n5.nabble.com/White-stripes-in-the-sea-tp5742281p5742357.ht... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi WanMil,
WanMil wrote
So as a result: When you want to remove the sea artefacts you must improve the multipolygon cutting.
just to make sure: I already see the small stripes in the precompiled sea tile when I open it in JOSM: (after converting to xml format)
sea.png <http://gis.19327.n5.nabble.com/file/n5742357/sea.png>
What you see is the result of the multipolygon algorithm that cuts the sea areas into distinct polygons to cut out the land area. The white stripes are the polygon lines. But there is no space between the polygons. So obviously that should not the problem. The problem is that Garmins draw algorithm seems to create the white lines.
I think the multipolygons algorithm just adds these ways, it doesn't combine them to one area which is then "destroyed" by the polygon split algorithm.
It's the mp algorithm task to cut the big sea polygon with holes into several polygons without holes. Holes in polygons are not supported by the Garmin format (as far as we know?).
So, the question for me is : Could we change the PrecompSeaGenerator or would it help to recombine the areas after reading the preocompiled sea files?
It would be possible to recombine some polygons that are cut too much due to the non optimal mp algorithm. But I guess it is better to improve the mp algorithm itself (as I described in my post). Once again: It does not make sense to improve the PrecompSeaGenerator because the main task it does is to calculate the multipolygons. And so the only thing that could be improved is the mp algorithm itself. WanMil
Hi WanMil,
What you see is the result of the multipolygon algorithm that cuts the sea areas into distinct polygons to cut out the land area. The white stripes are the polygon lines. But there is no space between the polygons. So obviously that should not the problem. The problem is that Garmins draw algorithm seems to create the white lines.
well, sorry, I meant the thin areas, not the white stripes between. These thin areas are likely to be thrown away when coordinates are rounded. I think this explains the white stripes that I see in the QLandkarte GT screenshot.
Once again: It does not make sense to improve the PrecompSeaGenerator because the main task it does is to calculate the multipolygons. And so the only thing that could be improved is the mp algorithm itself.
yes, I agree. So I'll try to find a better mp algorithm. Gerd
Hi WanMil,
What you see is the result of the multipolygon algorithm that cuts the sea areas into distinct polygons to cut out the land area. The white stripes are the polygon lines. But there is no space between the polygons. So obviously that should not the problem. The problem is that Garmins draw algorithm seems to create the white lines.
well, sorry, I meant the thin areas, not the white stripes between. These thin areas are likely to be thrown away when coordinates are rounded. I think this explains the white stripes that I see in the QLandkarte GT screenshot.
Ok, so you mean areas that are too thin are not drawn? The mp algorithm tries to do as few cuts as possible. So it cuts at that horizontal or vertical line where it can cut the most inner polygons. It does not check if the cutting line is longer or not (because it doesn't know and it's hard to estimate without implementing your own cut algorithm). As a first quick hack it would be possible to add a check if an area is too thin and to revert this cut. That leads to the question: Is there a definition for "too thin"?
Once again: It does not make sense to improve the PrecompSeaGenerator because the main task it does is to calculate the multipolygons. And so the only thing that could be improved is the mp algorithm itself.
yes, I agree. So I'll try to find a better mp algorithm.
All you have to do is to improve the private List<Way> cutOutInnerPolygons(Way outerPolygon, List<Way> innerPolygons) method in class MultipolygonRelation. Good luck! WanMil
Gerd
Ok, so you mean areas that are too thin are not drawn?
yes, I added a few system.out.println and found that a lot of sea or land polygons are completely dropped by the filters, for example a polygon with 14 points was reduced two 3 points by the RoundCoordsFilter and then thrown away by another.
The mp algorithm tries to do as few cuts as possible. So it cuts at that horizontal or vertical line where it can cut the most inner polygons. It does not check if the cutting line is longer or not (because it doesn't know and it's hard to estimate without implementing your own cut algorithm).
As a first quick hack it would be possible to add a check if an area is too thin and to revert this cut. That leads to the question: Is there a definition for "too thin"?
In the tile splitter I decided that a ratio of 1:4 or less is nice, but I have no theory for that.
yes, I agree. So I'll try to find a better mp algorithm.
All you have to do is to improve the private List<Way> cutOutInnerPolygons(Way outerPolygon, List<Way> innerPolygons) method in class MultipolygonRelation. Good luck!
OK, thanks. Let's see... Gerd
Ok, so you mean areas that are too thin are not drawn?
yes, I added a few system.out.println and found that a lot of sea or land polygons are completely dropped by the filters, for example a polygon with 14 points was reduced two 3 points by the RoundCoordsFilter and then thrown away by another.
After a quick check of the RoundCoordsFilter I guess the problem is not only too thin areas but also too small areas? Without having understood the filter in deep detail it seems that it rounds the coord according the shift which I think is another word for resolution/level. That also means if you have a big area that is split into many small areas the RoundCoordsFilter will all remove them and it is possible that you don't see the big area at all. Some ASCII art for a better understanding: The big rectangular area is divided into several small subareas (o): ooooooooo ooooooooo ooooooooo ooooooooo ooooooooo The RoundCoordsFilter removes all small areas o because they are too small for the given resolution. So the whole area disappears although it is big enough for the resolution to be displayed. I know that it would be nonsense to split the big area in the small subareas but in fact that's the same problem you will get with any mp algorithm that cuts the multipolygon into distinct singular areas. As a result we maybe have to break out an idea from the beginning of the mp implementation. It would be possible to do the cutting at a later position in the mkgmap chain. At the moment the cutting is done once for all resolutions. It would be better to do the cutting separate for each resolution. This would enable that in lower resolutions small inner polygons could be removed from the mp cutting because the inner area is so small that it is not displayed at that resolution. That's an interesting idea and I guess it would improve the look of the mkgmap generated maps quite a lot. At the same time I guess that it doesn't make much sense trying to improve the mp cut algorithm because you will reach similar problems again (one exception: the non java.awt.geom.Area compatible algorithm might work because it does not change the bounding box size of each polygon) WanMil
WanMil wrote
As a result we maybe have to break out an idea from the beginning of the mp implementation. It would be possible to do the cutting at a later position in the mkgmap chain. At the moment the cutting is done once for all resolutions. It would be better to do the cutting separate for each resolution. This would enable that in lower resolutions small inner polygons could be removed from the mp cutting because the inner area is so small that it is not displayed at that resolution.
That's an interesting idea and I guess it would improve the look of the mkgmap generated maps quite a lot. At the same time I guess that it doesn't make much sense trying to improve the mp cut algorithm because you will reach similar problems again (one exception: the non java.awt.geom.Area compatible algorithm might work because it does not change the bounding box size of each polygon)
I agrree in all points. Do you have a concrete idea how we could change the mkgmap chain? All the filter algorithms do only see type and sub-type values and points, but no information like sea or land. I don't see an easy way to do the cutting of inner polygons with this information. If we read the TYP file we know the drawing order, maybe that is enough? Would it be possible to define a TYP for a sea area that has many small islands and then automatically detect this for areas like the baltic sea? Else we have to find an algo to decide whether such a mixed area should be displayed as sea or land, esp. for the low resulutions. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/White-stripes-in-the-sea-tp5742281p5742390.ht... Sent from the Mkgmap Development mailing list archive at Nabble.com.
WanMil wrote
As a result we maybe have to break out an idea from the beginning of the mp implementation. It would be possible to do the cutting at a later position in the mkgmap chain. At the moment the cutting is done once for all resolutions. It would be better to do the cutting separate for each resolution. This would enable that in lower resolutions small inner polygons could be removed from the mp cutting because the inner area is so small that it is not displayed at that resolution.
That's an interesting idea and I guess it would improve the look of the mkgmap generated maps quite a lot. At the same time I guess that it doesn't make much sense trying to improve the mp cut algorithm because you will reach similar problems again (one exception: the non java.awt.geom.Area compatible algorithm might work because it does not change the bounding box size of each polygon)
I agrree in all points. Do you have a concrete idea how we could change the mkgmap chain? All the filter algorithms do only see type and sub-type values and points, but no information like sea or land. I don't see an easy way to do the cutting of inner polygons with this information.
I see many possible solutions. Two of them are: 1. At the moment multipolygons are cut into pieces just after reading from the input file. The first solution would not move that but the multipolygon code does the cutting for each resolution and tags the result with mkgmap:resolution=N. So there will be a copy of each polygon for each resolution. The style converter checks this tag and filters out the objects that does not match this resolution. The mp cutting code is changed in such a way that it uses the RoundCoordsFilter to check if a polygon is visible in the given resolution. If not it is not used in this resolution. This variant seems to be quite easy to implement and gives a good impression if that improves the whole story. It is not optimal due to the high number of additional polygons that must be kept in memory. But for a prototyping test it seems to be great. 2. The mp cut algorithm could be moved to the resolution dependant processing of mkgmap. That's somewhere between the StyledConverter and the subdivision splitting. This is a bit cleaner but I am not sure how many effort this needs.
If we read the TYP file we know the drawing order, maybe that is enough?
Would it be possible to define a TYP for a sea area that has many small islands and then automatically detect this for areas like the baltic sea? Else we have to find an algo to decide whether such a mixed area should be displayed as sea or land, esp. for the low resulutions.
I have no idea how to use a TYP file to avoid such problems. The algorithm to decide if a mixed are should be displayed as sea or land is the resolution dependant mp cut algorithm as described above. WanMil
Gerd
I see many possible solutions. Two of them are:
1. At the moment multipolygons are cut into pieces just after reading from the input file. The first solution would not move that but the multipolygon code does the cutting for each resolution and tags the result with mkgmap:resolution=N. So there will be a copy of each polygon for each resolution. The style converter checks this tag and filters out the objects that does not match this resolution. The mp cutting code is changed in such a way that it uses the RoundCoordsFilter to check if a polygon is visible in the given resolution. If not it is not used in this resolution.
This variant seems to be quite easy to implement and gives a good impression if that improves the whole story. It is not optimal due to the high number of additional polygons that must be kept in memory. But for a prototyping test it seems to be great.
Yes, that sounds like a good idea for the start. I also have some ideas how to improve the cutOutInnerPolygons() method.
2. The mp cut algorithm could be moved to the resolution dependant processing of mkgmap. That's somewhere between the StyledConverter and the subdivision splitting. This is a bit cleaner but I am not sure how many effort this needs.
Probably a lot more, but maybe I change my mind when I know the code a bit better.
I have no idea how to use a TYP file to avoid such problems. The algorithm to decide if a mixed are should be displayed as sea or land is the resolution dependant mp cut algorithm as described above.
Well, I don't yet have an idea how to handle the case when many small islands cover - lets say - 70% of the area, but all of them are too small to be displayed. I fear we will only display see in that case. Anyhow, this problem has to be solved later. Gerd
I have no idea how to use a TYP file to avoid such problems. The algorithm to decide if a mixed are should be displayed as sea or land is the resolution dependant mp cut algorithm as described above.
Well, I don't yet have an idea how to handle the case when many small islands cover - lets say - 70% of the area, but all of them are too small to be displayed. I fear we will only display see in that case. Anyhow, this problem has to be solved later.
So in ASCII art it's the following situation: (s = sea polygon, each l = single small land polygon) ssssssssssssssssss slllllllllllllllls slllllllllllllllls slllllllllllllllls ssssssssssssssssss In the end it is also a problem of the resolution dependant mp cut algorithm. At first it would remove all small single land polygons. But in an improved algorithm it could try to merge the land polygons. I guess merging will be quite complex: - What should be done if two small mergable polygons have some tags in common but also some different tags? How is the merged polygon tagged? - How should the algorithm detect that two polygons can be merged when they are not connected to each other? It could calculate fractions for each resolution dependant "pixel". So on one pixel the sea might be 30% and land 70% and therefore land wins and the pixel is assigned as land. This requires a good merging algorithm for pixels... - ??? WanMil
So in ASCII art it's the following situation: (s = sea polygon, each l = single small land polygon)
ssssssssssssssssss slllllllllllllllls slllllllllllllllls slllllllllllllllls ssssssssssssssssss
In the end it is also a problem of the resolution dependant mp cut algorithm. At first it would remove all small single land polygons. But in an improved algorithm it could try to merge the land polygons.
I guess merging will be quite complex: - What should be done if two small mergable polygons have some tags in common but also some different tags? How is the merged polygon tagged? - How should the algorithm detect that two polygons can be merged when they are not connected to each other? It could calculate fractions for each resolution dependant "pixel". So on one pixel the sea might be 30% and land 70% and therefore land wins and the pixel is assigned as land. This requires a good merging algorithm for pixels... - ???
Well, let's postpone this for now, if it can be done we can do it later. I've just realized that cutOutInnerPolygons() is called before the StyledConverter. Will the style system be able to handle data that is repeated for each resolution? I wonder if the coastline data is really a good reason to change the program logic that much. I think it is a special case and maybe it would be better not to pass the data through the same routines? Gerd
So in ASCII art it's the following situation: (s = sea polygon, each l = single small land polygon)
ssssssssssssssssss slllllllllllllllls slllllllllllllllls slllllllllllllllls ssssssssssssssssss
In the end it is also a problem of the resolution dependant mp cut algorithm. At first it would remove all small single land polygons. But in an improved algorithm it could try to merge the land polygons.
I guess merging will be quite complex: - What should be done if two small mergable polygons have some tags in common but also some different tags? How is the merged polygon tagged? - How should the algorithm detect that two polygons can be merged when they are not connected to each other? It could calculate fractions for each resolution dependant "pixel". So on one pixel the sea might be 30% and land 70% and therefore land wins and the pixel is assigned as land. This requires a good merging algorithm for pixels... - ???
Well, let's postpone this for now, if it can be done we can do it later. I've just realized that cutOutInnerPolygons() is called before the StyledConverter. Will the style system be able to handle data that is repeated for each resolution?
That's what I tried to explain some posts ago with the mkgmap:resolution=N tag. Some more details about that: You have two resolutions, e.g. 18 and 24. So as an example mp might create the following polygons p1 [mkgmap:resolution=18;natural=sea] p2 [mkgmap:resolution=24;natural=sea] p3 [mkgmap:resolution=24;natural=sea] p4 [mkgmap:resolution=24;natural=land] There are three polygons for resolution 24 but only one for resolution 18 because the inner land polygon p4 would not be visible in resolution 18. The style has the two rules: (Don't know if 0x31 is a good code for land but it's just an example) natural=land [0x31 resolution 10] natural=sea [0x32 resolution 10] p1 to p4 is processed by the style and therefore you would get four internal GType objects: g1 0x32 minResolution=10; maxResolution=24 g2 0x32 minResolution=10; maxResolution=24 g3 0x32 minResolution=10; maxResolution=24 g4 0x31 minResolution=10; maxResolution=24 But mkgmap:resolution is set therefore the given resolution is used as mask on the GType resolutions: g1 0x32 minResolution=18; maxResolution=18 g2 0x32 minResolution=24; maxResolution=24 g3 0x32 minResolution=24; maxResolution=24 g4 0x31 minResolution=24; maxResolution=24
I wonder if the coastline data is really a good reason to change the program logic that much. I think it is a special case and maybe it would be better not to pass the data through the same routines?
It is a general problem of the mp cutting so I think it should be solved there. Anyhow I think it's good idea to define an interface for the cut method within the MultipolygonRelation. That makes it easier to play with different cut algorithms and if required one could use different cut algorithms for sea and normal mps. I have created a branch mp_cut to start with the work. WanMil
I have created a branch mp_cut to start with the work.
Ok, I have created the interface for the multipolygon cut algorithm and I have also implemented the usage for the tag mkgmap:resolution. I could not test yet but the changes were not too complicated so possibly it works ;-) What is missing now is to create a resolution dependent cut algorithm. That's a bit more work but it should not take too much time. Hopefully I can try that during the weekend. Gerd, if you like feel free to add your own cut algorithm(s). WanMil
WanMil wrote
I have created a branch mp_cut to start with the work.
Ok, I have created the interface for the multipolygon cut algorithm and I have also implemented the usage for the tag mkgmap:resolution.
I could not test yet but the changes were not too complicated so possibly it works ;-)
What is missing now is to create a resolution dependent cut algorithm. That's a bit more work but it should not take too much time. Hopefully I can try that during the weekend.
Gerd, if you like feel free to add your own cut algorithm(s).
okay, it will take a while because I am busy with other things during the next days. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/White-stripes-in-the-sea-tp5742281p5742619.ht... Sent from the Mkgmap Development mailing list archive at Nabble.com.
On Wed, Jan 02, GerdP wrote:
Depending on the zoom level the white areas disappear or change to small white lines, so I assume it has to do with rounding. I tried all kinds of parameters to reduce these errors, but without success. My question: Are these errors normal?
Yes and No. I see them since a very long time, and I think I saw them the first time when rounding in mkgmap was changed to fix routing across tiles. But since some time I see them only very seldom, so it could be very well that the change had nothing to do with this, only I haven't really noticed it before. Did never had the time to really check if my observation is really true. But I got several reports, that this "errors" are very prominent visible on some maps on nearly invisible on other maps. But even that didn't lead me to any new idea. Thorsten -- Thorsten Kukuk, Project Manager/Release Manager SLES SUSE LINUX Products GmbH, Maxfeldstr. 5, D-90409 Nuernberg GF: Jeff Hawn, Jennifer Guild, Felix Imendörffer, HRB 16746 (AG Nürnberg)
participants (5)
-
Gerd Petermann -
GerdP
-
Marko Mäkelä -
Thorsten Kukuk -
WanMil