Hi WanMil, WanMil wrote
1. RoundCoordsFilter creates an invalid polygon with hole 2. PolygonSplitterFilter might split the polygon because it is too
large. It converts the polygon to a java.awt.geom.Area object, splits it into two halves and converts it back in the method PolygonSplitterBase.areaToShapes(..) method. This method does not check the orientation of the returned polygons and therefore converts the hole to same type the polygon has - in other words the hole is removed.
I thought about this again and I think it might be the solution for the mp-cut problem: We don't have to cut out inner polygons, instead we can connect each inner polygon with the outer one. We have to find two points: p1, a point on the outer way that is close to a point of the inner polygon, which is then called p2. Now, we have to split the outer way at p1, draw a line to p2, add the points of the inner polygon, and draw a way back from p2 to p1. It works (QLandkarte shows the polygon with a hole), but only when none of the filters destroys the added ways between p1 and p2. I don't know yet how multiple nested polygons look like, but I think it is a promising approach. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
On Sat, Jan 19, 2013 at 01:00:08AM -0800, GerdP wrote:
I don't know yet how multiple nested polygons look like, but I think it is a promising approach.
It should be simple. A line is both an inner member of the outer multipolygon, and the outer member of an inner multipolygon. So, basically you have two non-intersecting and non-overlapping multipolygons. There are some lakes with islands with lakes in Finland. One is Partalansaari, if I remember correctly. You could also have small patches of forest in the middle of a field in the middle of a forest, or vice versa. Marko
Hi WanMil,
WanMil wrote
1. RoundCoordsFilter creates an invalid polygon with hole 2. PolygonSplitterFilter might split the polygon because it is too
large. It converts the polygon to a java.awt.geom.Area object, splits it into two halves and converts it back in the method PolygonSplitterBase.areaToShapes(..) method. This method does not check the orientation of the returned polygons and therefore converts the hole to same type the polygon has - in other words the hole is removed.
I thought about this again and I think it might be the solution for the mp-cut problem: We don't have to cut out inner polygons, instead we can connect each inner polygon with the outer one. We have to find two points: p1, a point on the outer way that is close to a point of the inner polygon, which is then called p2. Now, we have to split the outer way at p1, draw a line to p2, add the points of the inner polygon, and draw a way back from p2 to p1. It works (QLandkarte shows the polygon with a hole), but only when none of the filters destroys the added ways between p1 and p2.
I don't know yet how multiple nested polygons look like, but I think it is a promising approach.
Gerd
Hi Gerd, that was the original approach how MPs were handeled in mkgmap but I changed it because of many problems. 1. You talked about the filter problem. Any use of the java Area object must be replaced. That might be possible but I expect a performance problem. 2. Finding a connection between inner and outer is not so easy as it sounds. You also have to check that the connection of inner and outer does not intersect any other inner/outer polygon. Also it must be checked that it does not intersect the same polygon. Look at the following mp (drawn partially): i i 7 1iiiiiii2 o o 8ooooooooooooooooooooooo3 o o o ooooooo6 5oooooooooooo4 o o ooooo o o o oooooooooooooooooooooooooooooooo o = outer polygon; i = inner polygon 7 is connected with 8 somwhere above my drawing Using the closest approach you would cut between point 6 and 1. But this intersects the outer polygon so it's not a good idea... So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance... So if you can realize it it probably will be a good approach. The algorithms are a bit more complex than it seems on a first sight. WanMil
So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance...
Performing a quick search I haven't found an algorithm but the problem is very similar to the visibility problems described in wikipedia: http://en.wikipedia.org/wiki/Visibility_%28geometry%29 http://en.wikipedia.org/wiki/Isovist http://en.wikipedia.org/wiki/Visibility_graph http://en.wikipedia.org/wiki/Art_gallery_problem WanMil
Hi WanMil, WanMil wrote
So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance...
Performing a quick search I haven't found an algorithm but the problem is very similar to the visibility problems described in wikipedia: http://en.wikipedia.org/wiki/Visibility_%28geometry%29 http://en.wikipedia.org/wiki/Isovist http://en.wikipedia.org/wiki/Visibility_graph http://en.wikipedia.org/wiki/Art_gallery_problem
thanks for the input. So, it seems I have to find an algo that finds the closest line. I have no idea reg. performance yet, but I think I can use Line2D.ptSegDistSq() which calculates the squared distance between the a point and a line seqment. I'll try to implement that in the PolygonSplitterBase.split() method because it is clearly an error that this method cuts areas without holes into areas that have holes. ciao, Gerd -- View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424p5745593.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi WanMil, WanMil wrote
So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance...
Performing a quick search I haven't found an algorithm but the problem is very similar to the visibility problems described in wikipedia: http://en.wikipedia.org/wiki/Visibility_%28geometry%29 http://en.wikipedia.org/wiki/Isovist http://en.wikipedia.org/wiki/Visibility_graph http://en.wikipedia.org/wiki/Art_gallery_problem
I have an algo now and performance seems to be quite ok. I did not yet try to place it into the mp-cut branch because I see NPE when I use the version as is: java.lang.NullPointerException at uk.me.parabola.mkgmap.reader.osm.mp.FewCutOptimizedAlgorithm.createAreas(FewCutOptimizedAlgorithm.java:431) at uk.me.parabola.mkgmap.reader.osm.mp.FewCutOptimizedAlgorithm.cutOutInnerPolygons(FewCutOptimizedAlgorithm.java:262) at uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation.processElements(MultiPolygonRelation.java:982) at uk.me.parabola.mkgmap.reader.osm.ElementSaver.addRelation(ElementSaver.java:167) ... Anyway, I want to make sure that we plan the same changes. As you already pointed out, the filter chain for shapes is probably not in the right order. Here is my proposal in pseudo-code: for each polygon (including holes){ for each resolution{ distinguish inner/outer smooth lines (eg. round coords, use Douglas-Peucker) of outer if outer is big enough for the selected resolution{ for each inner { smooth lines if inner is big enough: save it in list } if (list not empty): cutOutInnerPolygons(outer, list of inner) } cut shapes into pieces with max. 250 points } } The method MapBuilder.processShapes() should not change the shapes. Do you think the same way? Ciao, Gerd -- View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424p5746085.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi WanMil,
WanMil wrote
So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance...
Performing a quick search I haven't found an algorithm but the problem is very similar to the visibility problems described in wikipedia: http://en.wikipedia.org/wiki/Visibility_%28geometry%29 http://en.wikipedia.org/wiki/Isovist http://en.wikipedia.org/wiki/Visibility_graph http://en.wikipedia.org/wiki/Art_gallery_problem
I have an algo now and performance seems to be quite ok.
Great! Which algorithm did you implement? Do you use connect the inner polygon by one line in both directions with the outer polygon? How did you implement the visibility graph (which I think is required to ensure that the cutting line does not intersect with any other polygon)? I remember that I used some library to test the usage of such a graph. It was ok for small mps but for sea multipolygons with large polygons and lots of inner polygons it was performance trash! But maybe one can cut down the visibility graph to the required information which might also improve the performance.
I did not yet try to place it into the mp-cut branch because I see NPE when I use the version as is: java.lang.NullPointerException at uk.me.parabola.mkgmap.reader.osm.mp.FewCutOptimizedAlgorithm.createAreas(FewCutOptimizedAlgorithm.java:431) at uk.me.parabola.mkgmap.reader.osm.mp.FewCutOptimizedAlgorithm.cutOutInnerPolygons(FewCutOptimizedAlgorithm.java:262) at uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation.processElements(MultiPolygonRelation.java:982) at uk.me.parabola.mkgmap.reader.osm.ElementSaver.addRelation(ElementSaver.java:167) ...
Arghh, I've fixed that in my working copy but didn't commit it... It should be working now :-)
Anyway, I want to make sure that we plan the same changes. As you already pointed out, the filter chain for shapes is probably not in the right order. Here is my proposal in pseudo-code: for each polygon (including holes){ for each resolution{ distinguish inner/outer smooth lines (eg. round coords, use Douglas-Peucker) of outer if outer is big enough for the selected resolution{ for each inner { smooth lines if inner is big enough: save it in list } if (list not empty): cutOutInnerPolygons(outer, list of inner) } cut shapes into pieces with max. 250 points } }
The method MapBuilder.processShapes() should not change the shapes. Do you think the same way?
Do you want to move the mp calculation to the filter chain or do you describe the resolution based cutting of mps by reusing parts of the filter chain? I guess you mean the second. That's what I am trying to do. If you mean the first it's another approach. That's ok but I first wanted to test with the mp_cut branch if it helps to use resolution dependend mp cutting algorithms. In any case it's worthy to have a look on the existing filter chain. Any improvement in the concept or in real implementation will help fixing the mp cut problem with disappearing small polygons. In my concept I am not sure if it is required to use the whole filter chain in the mp processing. But I have also learned that applying filters like the RoundCoordsFilter before cutting also gives new problems to be solved. For example: A simple polygon might contain a hole if its coords are mapped to another resolution: res=24: ------ ------ / \ | | | / | | | / | | | \--- | | | | | ---------------- might be transformed to res=16 ---------------- | | | --- | | | | | | --- | | | ---------------- The existing mp cut algorithm must not handle this problem. So this is new thing to be solved in the resolution dependend mp cutting. Maybe not a big thing but there are some other things I didn't expect or I do not understand so far. That's the reason why there seem to be no progress in the last weeks.
Ciao, Gerd
Have fun! WanMil
Hi WanMil,
Date: Thu, 24 Jan 2013 21:02:11 +0100 From: wmgcnfg@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] shapes with holes
Hi WanMil,
WanMil wrote
So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance...
Performing a quick search I haven't found an algorithm but the problem is very similar to the visibility problems described in wikipedia: http://en.wikipedia.org/wiki/Visibility_%28geometry%29 http://en.wikipedia.org/wiki/Isovist http://en.wikipedia.org/wiki/Visibility_graph http://en.wikipedia.org/wiki/Art_gallery_problem
I have an algo now and performance seems to be quite ok.
Great! Which algorithm did you implement? Do you use connect the inner polygon by one line in both directions with the outer polygon? How did you implement the visibility graph (which I think is required to ensure that the cutting line does not intersect with any other polygon)? I remember that I used some library to test the usage of such a graph. It was ok for small mps but for sea multipolygons with large polygons and lots of inner polygons it was performance trash! But maybe one can cut down the visibility graph to the required information which might also improve the performance. I did not try with huge polygons containing many large inner polygons, I assume this will be the worst case. In short, I calculate the the distance between each line segment of the outer polygon to each point of the inner polygons. For each inner polygon, the combination with the smallest dist is kept. Next, these values are sorted so that the smallest dist comes first. then, for each inner polygons I try to find a point in an other inner polygon that is closer than the outer polygon. Finally, I connect the inner polygons with the outer in the order that was retrieved by the sort. This should make sure that I don't cross lines, but I am not yet 100% sure.
I did not yet try to place it into the mp-cut branch because I see NPE when I use the version as is: java.lang.NullPointerException at uk.me.parabola.mkgmap.reader.osm.mp.FewCutOptimizedAlgorithm.createAreas(FewCutOptimizedAlgorithm.java:431) at uk.me.parabola.mkgmap.reader.osm.mp.FewCutOptimizedAlgorithm.cutOutInnerPolygons(FewCutOptimizedAlgorithm.java:262) at uk.me.parabola.mkgmap.reader.osm.MultiPolygonRelation.processElements(MultiPolygonRelation.java:982) at uk.me.parabola.mkgmap.reader.osm.ElementSaver.addRelation(ElementSaver.java:167) ...
Arghh, I've fixed that in my working copy but didn't commit it... It should be working now :-)
Anyway, I want to make sure that we plan the same changes. As you already pointed out, the filter chain for shapes is probably not in the right order. Here is my proposal in pseudo-code: for each polygon (including holes){ for each resolution{ distinguish inner/outer smooth lines (eg. round coords, use Douglas-Peucker) of outer if outer is big enough for the selected resolution{ for each inner { smooth lines if inner is big enough: save it in list } if (list not empty): cutOutInnerPolygons(outer, list of inner) } cut shapes into pieces with max. 250 points } }
The method MapBuilder.processShapes() should not change the shapes. Do you think the same way?
Do you want to move the mp calculation to the filter chain or do you describe the resolution based cutting of mps by reusing parts of the filter chain?
I guess you mean the second. That's what I am trying to do. Yes, I think the filters have not enough information to decide how the simplified shape should look like. That has to be done in the mp-cut algorithm.
So, I think we work in the same direction. I'll continue testing the algo. I guess I should find worse cases in the polygons created by the SeaGenerator. Ciao, Gerd
Hi WanMil, WanMil wrote
Using the closest approach you would cut between point 6 and 1. But this intersects the outer polygon so it's not a good idea... So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance...
So if you can realize it it probably will be a good approach. The algorithms are a bit more complex than it seems on a first sight.
yes, it turned out that the Line2D.ptSegDistSq() method used with the mapunit values is fast enough, but much too imprecise. I found uk.me.parabola.util.QuadTree.distanceToSegment() which gives much better results, but is very CPU consuming. I still don't fully understand why the spherical calculation is needed since I only search for the smallest distance, not the real value :-( Attached is the result of a split of a semi complex relation: http://www.openstreetmap.org/browse/relation/108513 mpcut-connect.zip <http://gis.19327.n5.nabble.com/file/n5746915/mpcut-connect.zip> I am now looking for a simple way to reduce the costly calculations of point to line seqment distances. Maybe some Voronoi diagram can help, but I fear that this all ends up in a lot of code with many special cases :-( Gerd -- View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424p5746915.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi WanMil,
WanMil wrote
Using the closest approach you would cut between point 6 and 1. But this intersects the outer polygon so it's not a good idea... So you have to add some costly checks which point is directly connectable. There is an algorithm (I don't remember the name) that calculates which points are directly visible from a given point. If you want to implement it would work. Just search Wikipedia and the polygon algorithms. You will find it. I guss it's not very nice to the performance...
So if you can realize it it probably will be a good approach. The algorithms are a bit more complex than it seems on a first sight.
yes, it turned out that the Line2D.ptSegDistSq() method used with the mapunit values is fast enough, but much too imprecise. I found uk.me.parabola.util.QuadTree.distanceToSegment() which gives much better results, but is very CPU consuming. I still don't fully understand why the spherical calculation is needed since I only search for the smallest distance, not the real value :-(
Attached is the result of a split of a semi complex relation: http://www.openstreetmap.org/browse/relation/108513
mpcut-connect.zip <http://gis.19327.n5.nabble.com/file/n5746915/mpcut-connect.zip>
I am now looking for a simple way to reduce the costly calculations of point to line seqment distances. Maybe some Voronoi diagram can help, but I fear that this all ends up in a lot of code with many special cases :-(
Gerd
Hi Gerd, looks nice. Some notes: I don't understand why you calculate the distance between a point and a segment and not between two points? Of course you can create your own distance calculation without the spherical part. It is required in the Quadtree because it checks if the checked point is more far away than a given gap. Another reason is that one Garmin map unit does not have a constant length. Was that your problem with Line2D.ptSegDistSq()? Your cut procedure still requires that all parts of mkgmap that use the resulting ways do not use the java.awt.geom.Area class. So another hard second part of the implementation is to find an adequate replacement for this. WanMil
Some notes: I don't understand why you calculate the distance between a point and a segment and not between two points? In the sea generator, the outer polygon is a big bbox. If I connect the points all inner shapes are connected to the corners of the bbox (if I don't care about visibility). My idea is that if I create the connection with the shortest line it is impossible that another shape is crossed. WanMil wrote
Of course you can create your own distance calculation without the spherical part. It is required in the Quadtree because it checks if the checked point is more far away than a given gap. Another reason is that one Garmin map unit does not have a constant length. Was that your problem with Line2D.ptSegDistSq()?
I really don't know. I find completely different nodes for the connections when I use the simple calculation. I'll sleep again about this ;-) WanMil wrote
Your cut procedure still requires that all parts of mkgmap that use the resulting ways do not use the java.awt.geom.Area class. So another hard second part of the implementation is to find an adequate replacement for this.
Yes, I have to find a way to split the resulting polygon into parts with less than 250 nodes. I don't yet have a good idea how to do this. Ciao, Gerd -- View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424p5746923.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
Some notes: I don't understand why you calculate the distance between a point and a segment and not between two points? In the sea generator, the outer polygon is a big bbox. If I connect the points all inner shapes are connected to the corners of the bbox (if I don't care about visibility). My idea is that if I create the connection with the shortest line it is impossible that another shape is crossed.
Yes, that should work - good.
WanMil wrote
Of course you can create your own distance calculation without the spherical part. It is required in the Quadtree because it checks if the checked point is more far away than a given gap. Another reason is that one Garmin map unit does not have a constant length. Was that your problem with Line2D.ptSegDistSq()?
I really don't know. I find completely different nodes for the connections when I use the simple calculation. I'll sleep again about this ;-)
WanMil wrote
Your cut procedure still requires that all parts of mkgmap that use the resulting ways do not use the java.awt.geom.Area class. So another hard second part of the implementation is to find an adequate replacement for this.
Yes, I have to find a way to split the resulting polygon into parts with less than 250 nodes. I don't yet have a good idea how to do this.
I think it is not a good idea to focus on the 250 nodes limit. This creates an implicit rule about the further processing after the multipolygon has been calculated. And that will fail at some time in future. (e.g. the java Area object is also used in the AreaClipper) Without changing the splitting with the java Area object you might also change the cutting procedure a little bit. Instead of completely surrounding the inner polygons you might create singular polygons without holes by partly surrounding the inner polygons. The algorithm should not too complex if you have the information about the shortest distances. I have implemented a similar algorithm a long time ago when I tried a similar approach. But I abandoned because the calculations of the shortest distances took much too long (I used a visibility graph calculated by an external library). This change makes it possible to keep the java Area calculations until we find a good replacement. WanMil
Ciao, Gerd
WanMil wrote
I think it is not a good idea to focus on the 250 nodes limit. This creates an implicit rule about the further processing after the multipolygon has been calculated. And that will fail at some time in future. (e.g. the java Area object is also used in the AreaClipper)
Without changing the splitting with the java Area object you might also change the cutting procedure a little bit. Instead of completely surrounding the inner polygons you might create singular polygons without holes by partly surrounding the inner polygons. The algorithm should not too complex if you have the information about the shortest distances. I have implemented a similar algorithm a long time ago when I tried a similar approach. But I abandoned because the calculations of the shortest distances took much too long (I used a visibility graph calculated by an external library).
This change makes it possible to keep the java Area calculations until we find a good replacement.
I wanted to implement that, but I did not find an efficient way to calculate equally sized areas. If I just cut somewhere it is likely to have again small stripes. That's why I think that we should not use java Area for this, but I agree that a replacement isn't hard to find. Looks so easy and is so complicated ;-) Gerd Gerd -- View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424p5747089.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
WanMil wrote
I think it is not a good idea to focus on the 250 nodes limit. This creates an implicit rule about the further processing after the multipolygon has been calculated. And that will fail at some time in future. (e.g. the java Area object is also used in the AreaClipper)
Without changing the splitting with the java Area object you might also change the cutting procedure a little bit. Instead of completely surrounding the inner polygons you might create singular polygons without holes by partly surrounding the inner polygons. The algorithm should not too complex if you have the information about the shortest distances. I have implemented a similar algorithm a long time ago when I tried a similar approach. But I abandoned because the calculations of the shortest distances took much too long (I used a visibility graph calculated by an external library).
This change makes it possible to keep the java Area calculations until we find a good replacement.
I wanted to implement that, but I did not find an efficient way to calculate equally sized areas. If I just cut somewhere it is likely to have again small stripes. That's why I think that we should not use java Area for this, but I agree that a replacement isn't hard to find. Looks so easy and is so complicated ;-)
Gerd
I wonder if it is less important to find big enough areas with this algorithm. The old problem are white stripes which are ugly. Using the described new algorithm there is also a chance that some cuttings are too small. But the probability of a small aspect ratio is much higher than in the old algorithm. Having a smaller aspect ratio the little parts that are missing are also smaller. So I think a small aspect ratio might be a kind of indicator how visible the missing parts are. Maybe it is worthy to try that out. (I am sure at least this algorithm is better than the existing :-) WanMil
WanMil wrote
I wonder if it is less important to find big enough areas with this algorithm. The old problem are white stripes which are ugly. Using the described new algorithm there is also a chance that some cuttings are too small. But the probability of a small aspect ratio is much higher than in the old algorithm. Having a smaller aspect ratio the little parts that are missing are also smaller. So I think a small aspect ratio might be a kind of indicator how visible the missing parts are. Maybe it is worthy to try that out. (I am sure at least this algorithm is better than the existing :-)
I agree that it would be better. I am still fighting with the precision (= performance) problems. When that is solved I try to find a algorithm that really cuts. Ciao, Gerd -- View this message in context: http://gis.19327.n5.nabble.com/shapes-with-holes-tp5745424p5747099.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
participants (4)
-
Gerd Petermann -
GerdP
-
Marko Mäkelä -
WanMil