Multipolygons and basic question on polygons with holes
Dear all, I still have the feeling that the cause of the problems with multipolygons may be due to the representation of "polygons with holes" in the img file. If I'm not mistaken, the multipolygon code connects the inner and outer polylines forming the multipolygon which either leads to spurious lines ("triangles", see sea polygons in mp-mode) or to vanishing inner polylines. Is this really the correct representation of "polygons with holes" in the img file? BTW: There is also still a problem with the rendering of polygons with holes in the polish format. The attached mp-file is displayed correctly in gpsmapedit, but the generated img file is broken. The polish format seems to add "inner" polygons as extra data lines, but these additional lines are not handled in a special way. Best wishes Christian
On 01/01/10 13:15, Christian Gawron wrote:
I still have the feeling that the cause of the problems with multipolygons may be due to the representation of "polygons with holes" in the img file. If I'm not mistaken, the multipolygon code connects the inner and outer polylines forming the multipolygon which either leads to spurious lines ("triangles", see sea polygons in mp-mode) or to vanishing inner polylines.
Yes that is what it does.
Is this really the correct representation of "polygons with holes" in the img file?
I've no idea, I've been wondering too. It could be that the way Mark is doing the sea/island polygons is the right way, except that if I'm not mistaken his method only works with a TYP file, whereas it is clearly possible to do this without since the MetroEurope maps don't have a typ tile. I am going to look into some examples, if not today then tomorrow. : There is also still a problem with the rendering of polygons with
holes in the polish format. The attached mp-file is displayed correctly
Yes that case is just not implemented as far as I know. Happy 2010 to everybody. ..Steve
Hi Steve,
I've no idea, I've been wondering too. It could be that the way Mark is doing the sea/island polygons is the right way, except that if I'm not mistaken his method only works with a TYP file, whereas it is clearly possible to do this without since the MetroEurope maps don't have a typ tile.
Yes, my alternative scheme for sea/land does require a TYP file so it can't be the method used in the Garmin maps. What would be very useful is if the IMG format supported a polygon type that cut a hole in the polygon below it. Are we sure that such a beast does not exist? How about trying to find an unlocked Garmin map that contains sea with islands and examine it carefully? Cheers, Mark
On 01/01/10 13:43, Mark Burton wrote:
Yes, my alternative scheme for sea/land does require a TYP file so it can't be the method used in the Garmin maps.
OK
What would be very useful is if the IMG format supported a polygon type that cut a hole in the polygon below it. Are we sure that such a beast does not exist? How about trying to find an unlocked Garmin map that contains sea with islands and examine it carefully?
I've looked at one of my maps and it works just in the way that the multipolygon code works in that there is a single polygon with a cut between the hole and the outer polygon. Some observations 1. The sea polygon is probably cut up into small enough pieces first, before the "cuts" to the hole are made. 2. Because we do things the other way round, we make the cut a slight wedge shape, as you cannot send polygons that have touching segments to the polygon splitting code. This is what makes things look bad. 3. If you split a sea polygon with a line that goes "through" (around) a hole then you don't need to add a cut. 4. Its probably easier to do it by hand, but that might just reflect my lack of knowledge of GIS algorithms in this area... I realise that it would be easier if I made a drawing so look at http://www.mkgmap.org.uk/tmp/islands.png In nicely working maps A and B are coincident, as are C and D. In our maps C and D are not, our original code also made them coincident, but this failed when the polygon was big enough to need splitting. This is why I suggest attempting to split large polygons first. Point 3 is illustrated by the second diagram, where a sea polygon is split into X and Y and avoids the need for a DABC cut as in the first. It may not be easy to take advantage of this with an algorithm, but I'd probably make use of that a lot if doing it by hand. Cheers, ..Steve
Am 02.01.2010 00:19, schrieb Steve Ratcliffe:
[...] Some observations
1. The sea polygon is probably cut up into small enough pieces first, before the "cuts" to the hole are made. 2. Because we do things the other way round, we make the cut a slight wedge shape, as you cannot send polygons that have touching segments to the polygon splitting code. This is what makes things look bad. 3. If you split a sea polygon with a line that goes "through" (around) a hole then you don't need to add a cut. 4. Its probably easier to do it by hand, but that might just reflect my lack of knowledge of GIS algorithms in this area...
I think it should not be too hard to create an algorithm that decomposes a polygon with holes into polygons without holes. I googled for "polygon decomposition" and found a paper describing an algorithm to decompose a polygon with holes into convex polygons, but this seems to be more than we need (and too complex computationally). Right now I have some time so I will have a look at it. Best wishes Christian
Am 02.01.2010 15:18, schrieb Christian Gawron:
Am 02.01.2010 00:19, schrieb Steve Ratcliffe:
[...] Some observations
1. The sea polygon is probably cut up into small enough pieces first, before the "cuts" to the hole are made. 2. Because we do things the other way round, we make the cut a slight wedge shape, as you cannot send polygons that have touching segments to the polygon splitting code. This is what makes things look bad. 3. If you split a sea polygon with a line that goes "through" (around) a hole then you don't need to add a cut. 4. Its probably easier to do it by hand, but that might just reflect my lack of knowledge of GIS algorithms in this area...
I think it should not be too hard to create an algorithm that decomposes a polygon with holes into polygons without holes. I googled for "polygon decomposition" and found a paper describing an algorithm to decompose a polygon with holes into convex polygons, but this seems to be more than we need (and too complex computationally). Right now I have some time so I will have a look at it.
Best wishes Christian
Christian, I think it's a good idea to change the strategy from the old "polygon with holes" to "simple polygons". The old strategy does not work with the PolygonSplitter and seems to be too complex. I have some requirements to the new strategy: * It should handle most of possible cases. Otherwise we will always have complaints about not supported multipolygons. * It should take not too much performance. The current findCpa method is a performance killer for polygons with lots of points. * It should work with the current PolygonSplitter. This is achieved by creating simple polygons. At the moment I am using your idea of simple polygons and try a new implementation using the java.awt.Area class that is also used in the PolygonSplitter. I hope this will achieve the requirements. WanMil
I'm not involved in the multipolygon code at all, but some comments:
I realise that it would be easier if I made a drawing so look at http://www.mkgmap.org.uk/tmp/islands.png
In nicely working maps A and B are coincident, as are C and D. In our maps C and D are not, our original code also made them coincident, but this failed when the polygon was big enough to need splitting. This is why I suggest attempting to split large polygons first.
Reading this, it means for me, that the splitting code ist the source of the problems. Maybe we need an more complex code for splitting, which handles concave polygons well. I imagine something like cut it with a pair of scissors. But I have no algorithm at hand.
Point 3 is illustrated by the second diagram, where a sea polygon is split into X and Y and avoids the need for a DABC cut as in the first. It may not be easy to take advantage of this with an algorithm, but I'd probably make use of that a lot if doing it by hand.
Sorry, but I can't see the difference. The picture on the right side shows a splitted polygon, but there are two places with parallel lines. Both polygons have concave segments too. So there is the same need for a DABC cut. Where is my misunderstanding? Regards, Johann
Am 02.01.2010 22:32, schrieb Johann Gail:
Point 3 is illustrated by the second diagram, where a sea polygon is
split into X and Y and avoids the need for a DABC cut as in the first. It may not be easy to take advantage of this with an algorithm, but I'd probably make use of that a lot if doing it by hand.
Sorry, but I can't see the difference. The picture on the right side shows a splitted polygon, but there are two places with parallel lines. Both polygons have concave segments too. So there is the same need for a DABC cut. Where is my misunderstanding?
Dear Johann, the problem in the splitter does AFAIK only occur when the overlapping segments are in the _same_ polygon. So the second diagram should (hopefully) be handled correctly by the splitter. The splitter uses java.awt.geom.Area to do the hard stuff, so I think it's not so easy to fix it. Best wishes Christian
participants (5)
-
Christian Gawron -
Johann Gail -
Mark Burton -
Steve Ratcliffe -
WanMil