Putting the DP code under the microscope
Hi, As today's topic is the DP code, I thought I would take a close look. Not sure, but is the i-- on line 93 erroneous? As i will be decremented at the end of the loop anyway, it seems to me that the extra decrement will give rise to the possibility that a Coord won't be tested to see if it's a CoordNode and so it will get zapped if it's not outside the error tolerance? Do we care? Cheers, Mark
Hi Mark, Am 16.06.2009 um 23:48 schrieb Mark Burton:
Not sure, but is the i-- on line 93 erroneous? As i will be decremented at the end of the loop anyway, it seems to me that the extra decrement will give rise to the possibility that a Coord won't be tested to see if it's a CoordNode and so it will get zapped if it's not outside the error tolerance? Do we care?
I vote for "bug" here. I've removed the "i--" on line 93 and I see no problems when compiling a map. Regards Thilo
Not sure, but is the i-- on line 93 erroneous? As i will be decremented at the end of the loop anyway, it seems to me that the extra decrement will give rise to the possibility that a Coord won't be tested to see if it's a CoordNode and so it will get zapped if it's not outside the error tolerance? Do we care?
I vote for "bug" here. I've removed the "i--" on line 93 and I see no problems when compiling a map.
The original code was from me. This additional i-- was some sort of optimization. Example: Line with 10 points Point 5 is a node. So the segment between 5 and 10 gets straightened. Afterwards I would test point 4. But between point 4 and 5 is only a straight line, so it doesn't make sense to test them. I can continue with segment 3 to 5. But you are right. If point 4 is a CoordNode then the endpoint should not be zapped. So it is a small bug, but will probably not help at the overview map. Well watched. Please commit that change. Regards, Johann
Hi Johann,
But you are right. If point 4 is a CoordNode then the endpoint should not be zapped. So it is a small bug, but will probably not help at the overview map. Well watched. Please commit that change.
OK, I will remove the --i and commit that change. What are your thoughts on the patch (I think it was by Thilo) that replaces the lost last point in each polygon? Seems like a good idea to me. Cheers, Mark
What are your thoughts on the patch (I think it was by Thilo) that replaces the lost last point in each polygon? Seems like a good idea to me.
I have looked at the patch only one minute. Seems correct. May thoughts was that the last segment ist not needed, if it is a polygon which gets filled. But with only contours there will arise problems. Right. In my private working copy I have tested another solution in the meanwhile. Do not remove the first point. Instead divide the line in two parts and simplify both of them. Could not say if it works better or not. Sorry, I'm in a hurry, no more time left to create a patch. // Create a new list to rewrite the points into. Don't alter the original one List<Coord> coords = new ArrayList<Coord>(n); coords.addAll(points); //Handle Polygons different + if (element instanceof MapShape) { + int middle = n/2; + douglasPeucker(coords, middle, n, maxErrorDistance); + douglasPeucker(coords, 0, middle, maxErrorDistance); + + } + else { // For now simplify all points, which are not nodes // and no start and no end point // Loop runs downwards, as the list length gets modified while running int endIndex = coords.size()-1; for(int i = endIndex-1; i > 0; i--) { Regards, Johann
Hi Johann,
What are your thoughts on the patch (I think it was by Thilo) that replaces the lost last point in each polygon? Seems like a good idea to me.
I have looked at the patch only one minute. Seems correct. May thoughts was that the last segment ist not needed, if it is a polygon which gets filled. But with only contours there will arise problems. Right.
In my private working copy I have tested another solution in the meanwhile.
Do not remove the first point. Instead divide the line in two parts and simplify both of them. Could not say if it works better or not.
I think I like this idea better. Perhaps folks can test both fixes and decide which is best.
Sorry, I'm in a hurry, no more time left to create a patch.
No problem, I'm sure the team can do that. Cheers, Mark
// Create a new list to rewrite the points into. Don't alter the original one List<Coord> coords = new ArrayList<Coord>(n); coords.addAll(points);
//Handle Polygons different + if (element instanceof MapShape) { + int middle = n/2; + douglasPeucker(coords, middle, n, maxErrorDistance); + douglasPeucker(coords, 0, middle, maxErrorDistance); + + } + else { // For now simplify all points, which are not nodes // and no start and no end point // Loop runs downwards, as the list length gets modified while running int endIndex = coords.size()-1; for(int i = endIndex-1; i > 0; i--) {
Regards, Johann _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Here is another approach to the "lost last point". The Douglas Peucker filter is improved so that it can deal with identical start- and endpoints. If the start- and the endpoint are identical, the algorithm calculates the distance between these identical points and the point p. So the polygon is not split at point N/2, but at the point that has the greatest distance from the start-/endpoint. Dealing with the problem in the Douglas Peucker algorithm itself has the advantage that it will also work for a pathological polygon or way that has identical, non-consecutive points in the middle of it. Index: src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java =================================================================== --- src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java (revision 1067) +++ src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java (working copy) @@ -60,20 +60,11 @@ MapLine line = (MapLine) element; + // Create a new list to rewrite the points into. Don't alter the original one List<Coord> points = line.getPoints(); - int n = points.size()-1; - - // Create a new list to rewrite the points into. Don't alter the original one - List<Coord> coords = new ArrayList<Coord>(n); + List<Coord> coords = new ArrayList<Coord>(points.size()); coords.addAll(points); - // If the first point is identic with the last one (a polygon), drop it - // Otherwise douglasPeucker will not work! - while ((n > 0) && coords.get(0).equals(coords.get(n))) { - coords.remove(n); - n--; - } - //#if (Node version) //Dont touch Coords, which are nodes. //So points at croosings will not be moved @@ -129,18 +120,33 @@ Coord b = points.get(endIndex); double ab = a.distance(b); - // Find point with highest distance. - for(int i = endIndex-1; i > startIndex; i--) { - Coord p = points.get(i); - double ap = p.distance(a); - double bp = p.distance(b); - double abpa = (ab+ap+bp)/2; - double distance = 2 * Math.sqrt(abpa * (abpa-ab) * (abpa-ap) * (abpa-bp)) / ab; - if (distance > maxDistance) { - maxDistance = distance; - maxIndex = i; + if (ab == 0) { // Start- and endpoint are the same + // Find point with highest distance to start- and endpoint + for (int i = endIndex-1; i > startIndex; i--) { + Coord p = points.get(i); + double distance = p.distance(a); + if (distance > maxDistance) { + maxDistance = distance; + maxIndex = i; + } } + } else { + // Find point with highest distance to line between start- and endpoint + for(int i = endIndex-1; i > startIndex; i--) { + // Calculate the area of the triangle a-b-p using Heron's formular. The height of + // that triangle is the distance we look for. + Coord p = points.get(i); + double ap = p.distance(a); + double bp = p.distance(b); + double abpa = (ab+ap+bp)/2; + double distance = 2 * Math.sqrt(abpa * (abpa-ab) * (abpa-ap) * (abpa-bp)) / ab; + if (distance > maxDistance) { + maxDistance = distance; + maxIndex = i; + } + } } + if (maxDistance > allowedError) { // Call recursive for both parts douglasPeucker(points, maxIndex, endIndex, allowedError); @@ -148,6 +154,12 @@ } else { // All points in tolerance, delete all of them. + + // Remove the endpoint if it is the same as the startpoint + if (ab == 0) + points.remove(endIndex); + + // Remove the points in between for(int i = endIndex-1; i > startIndex; i--) { points.remove(i); }
Thilo Hannemann schrieb:
Here is another approach to the "lost last point". The Douglas Peucker filter is improved so that it can deal with identical start- and endpoints. If the start- and the endpoint are identical, the algorithm calculates the distance between these identical points and the point p. So the polygon is not split at point N/2, but at the point that has the greatest distance from the start-/endpoint.
Dealing with the problem in the Douglas Peucker algorithm itself has the advantage that it will also work for a pathological polygon or way that has identical, non-consecutive points in the middle of it.
Yes, I like this idea too. It is better to search the point with the highst distance instead of simply asume N/2. Regards, Johann
Thilo Hannemann schrieb:
Here is another approach to the "lost last point". The Douglas Peucker filter is improved so that it can deal with identical start- and endpoints. If the start- and the endpoint are identical, the algorithm calculates the distance between these identical points and the point p. So the polygon is not split at point N/2, but at the point that has the greatest distance from the start-/endpoint.
Dealing with the problem in the Douglas Peucker algorithm itself has the advantage that it will also work for a pathological polygon or way that has identical, non-consecutive points in the middle of it.
Hi Thilo, I was just trying to get your patch working and would like to test it afterwards. In general I find it a good one. But I'm not sure about the last lines of your patch. If you delete the endpoint in case of ab==0 then you introduce the original problem again. The problem was polygons loosing their start or endpoints. What are your thoughts about it? Greetings, Johann
@@ -148,6 +154,12 @@ } else { // All points in tolerance, delete all of them. + + // Remove the endpoint if it is the same as the startpoint + if (ab == 0) + points.remove(endIndex); + + // Remove the points in between for(int i = endIndex-1; i > startIndex; i--) { points.remove(i); }
Hi Johann, it is actually not what it seems to be. The douglasPeucker function is called recursively. If the condition (maxDistance < allowedError) is fulfilled, the current part of the way can be reduced to a line (in case start- and endpoint are different points) or a point (in case start- and endpoint are the same). So the "if (ab == 0) points.remove(endIndex)" does not remove the endpoint of the whole polygon, but only prevents the polygon to have consecutive identical nodes if the original way has small "loops" in it. Wouldn't be that uncommon for contour lines btw. Closed polygons stay closed unless they are smaller than the allowedError, in which case they will reduce to a single point and will be dropped later anyway. Some other observation about the DP code: I'm currently using the "Straight version" instead of the "Node version" and I think the maps look much nicer if zoomed out. I would recommend this as the standard setting. The problem of T-crossings not lining up isn't that prominent, because in resolution 24 the DP won't be applied at all and in the other resolutions it is not that much noticeable (for me at least). Regards Thilo Am 24.07.2009 um 23:11 schrieb Johann Gail:
Thilo Hannemann schrieb:
Here is another approach to the "lost last point". The Douglas Peucker filter is improved so that it can deal with identical start- and endpoints. If the start- and the endpoint are identical, the algorithm calculates the distance between these identical points and the point p. So the polygon is not split at point N/2, but at the point that has the greatest distance from the start-/endpoint.
Dealing with the problem in the Douglas Peucker algorithm itself has the advantage that it will also work for a pathological polygon or way that has identical, non-consecutive points in the middle of it.
Hi Thilo,
I was just trying to get your patch working and would like to test it afterwards. In general I find it a good one. But I'm not sure about the last lines of your patch. If you delete the endpoint in case of ab==0 then you introduce the original problem again. The problem was polygons loosing their start or endpoints.
What are your thoughts about it?
Greetings, Johann
@@ -148,6 +154,12 @@ } else { // All points in tolerance, delete all of them. + + // Remove the endpoint if it is the same as the startpoint + if (ab == 0) + points.remove(endIndex); + + // Remove the points in between for(int i = endIndex-1; i > startIndex; i--) { points.remove(i); }
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Johann,
it is actually not what it seems to be. The douglasPeucker function is called recursively. If the condition (maxDistance < allowedError) is fulfilled, the current part of the way can be reduced to a line (in case start- and endpoint are different points) or a point (in case start- and endpoint are the same). So the "if (ab == 0) points.remove(endIndex)" does not remove the endpoint of the whole polygon, but only prevents the polygon to have consecutive identical nodes if the original way has small "loops" in it. Wouldn't be that uncommon for contour lines btw. Closed polygons stay closed unless they are smaller than the allowedError, in which case they will reduce to a single point and will be dropped later anyway.
Ok, with your explanation it seems reasonable to me. I will gave it a try later.
Some other observation about the DP code: I'm currently using the "Straight version" instead of the "Node version" and I think the maps look much nicer if zoomed out. I would recommend this as the standard setting. The problem of T-crossings not lining up isn't that prominent, because in resolution 24 the DP won't be applied at all and in the other resolutions it is not that much noticeable (for me at least).
I've played with both versions and both of them have different advantages. This was the reason I included both of them into the patch. The straight line was the first attempt and does a good work with the default settings. Later I increased the allowed error distance to reduce data more and speedup drawing speed of my etrex. In my working copy I increased the error distance this far, so that the line can differ one or two pixels on the display. With this the crossings doesn't match exactly anymore. Therefore I introduced the node version, which doesn't zap nodes of crossings. A further development would be, to consider only nodes which are visible crossings at the current zoom level. I.e. if a residential connects to a big road and the residential is not visible at the current zoom level, then it is allowed to zap this node. This would straighten out lines at low zooms much more. But at the DP filter code I don't have this information available. Btw.: there is another patch around, which merges lines before DP filtering them. This is reasonable for the highways at very low zoom levels, which could be simplified often to a sinlge line in the overview maps. (But only if they are not cut in segments from exit to exit). If I find some time I will release an updated patch for it. Regards, Johann
Hi Johann, Am 25.07.2009 um 10:54 schrieb Johann Gail:
A further development would be, to consider only nodes which are visible crossings at the current zoom level. I.e. if a residential connects to a big road and the residential is not visible at the current zoom level, then it is allowed to zap this node. This would straighten out lines at low zooms much more. But at the DP filter code I don't have this information available.
Yes, that would be the best way. But one would need to change a lot of the underlying code to make it happen, as currently only the number of highways that use a node is stored, but no reference to which highways that are. Changing this would be a major act unfortunately. About the error distance: What I still experience is that the lower resolutions look bad in the maps. It seems that the ways get too much simplified for lower resolutions. It seems almost like a scaling problem with respect to the resolution. I reduced the error distance to 1/8th of the resolution and that brought some improvement in the higher resolutions (20, 22). But if I look at the lower resolutions (down to 12) it gets worse and worse. Looking at the DP code I can't find any hint why that should happen, so it might happen somewhere else? I have no clue.
Btw.: there is another patch around, which merges lines before DP filtering them. This is reasonable for the highways at very low zoom levels, which could be simplified often to a sinlge line in the overview maps. (But only if they are not cut in segments from exit to exit). If I find some time I will release an updated patch for it.
this is very interesting. I was planning to implement something likes this for some time, but didn't get around to do it. But not so much for display, but for routing. I think the routing could be much improved if we would merge ways, especially for bicycle routing, where the cycleways consist of tiny bits here and there. The routing algorithm in the Garmin units then won't find a nice route, because it gives up trying to wiggle its way through the short bits. Instead it takes a long way that goes into the general direction of the destination. Which often happens to be a major road that you don't really want to use while cycling. The cycleway going alongside it isn't used, because the routing algorithm doesn't find it. So if you have that patch available please post it. Even if it doesn't work against the current trunk I'll happily try to make it work. Regards Thilo
Yeah, merging roads if possible would be great. Even more important would however be smoothing of curves. i.e. make serpentine corners on mountain streets more smooth, because otherwise if there is a say 160° corner, it will add a big time penalty, which in a car is more or less correct, but on a bicycle overrated. However, how do you want to do the merging without loosing attributes (i.e. roadname changes, bridge, etc..), I think this could only work by running after the main processing, and merging everything identical if possible. Otherwise before merging there needs to be a check whether there is not a rule in the style-file that would change either the name of the road OR the type (0x??) of a road. If both not changed then merge it. Nice to see some work on it. On 25/07/2009, Thilo Hannemann <thannema@gmx.de> wrote:
Hi Johann,
Am 25.07.2009 um 10:54 schrieb Johann Gail:
A further development would be, to consider only nodes which are visible crossings at the current zoom level. I.e. if a residential connects to a big road and the residential is not visible at the current zoom level, then it is allowed to zap this node. This would straighten out lines at low zooms much more. But at the DP filter code I don't have this information available.
Yes, that would be the best way. But one would need to change a lot of the underlying code to make it happen, as currently only the number of highways that use a node is stored, but no reference to which highways that are. Changing this would be a major act unfortunately.
About the error distance: What I still experience is that the lower resolutions look bad in the maps. It seems that the ways get too much simplified for lower resolutions. It seems almost like a scaling problem with respect to the resolution. I reduced the error distance to 1/8th of the resolution and that brought some improvement in the higher resolutions (20, 22). But if I look at the lower resolutions (down to 12) it gets worse and worse. Looking at the DP code I can't find any hint why that should happen, so it might happen somewhere else? I have no clue.
Btw.: there is another patch around, which merges lines before DP filtering them. This is reasonable for the highways at very low zoom levels, which could be simplified often to a sinlge line in the overview maps. (But only if they are not cut in segments from exit to exit). If I find some time I will release an updated patch for it.
this is very interesting. I was planning to implement something likes this for some time, but didn't get around to do it. But not so much for display, but for routing. I think the routing could be much improved if we would merge ways, especially for bicycle routing, where the cycleways consist of tiny bits here and there. The routing algorithm in the Garmin units then won't find a nice route, because it gives up trying to wiggle its way through the short bits. Instead it takes a long way that goes into the general direction of the destination. Which often happens to be a major road that you don't really want to use while cycling. The cycleway going alongside it isn't used, because the routing algorithm doesn't find it.
So if you have that patch available please post it. Even if it doesn't work against the current trunk I'll happily try to make it work.
Regards Thilo
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Felix, Am 25.07.2009 um 13:05 schrieb Felix Hartmann:
Yeah, merging roads if possible would be great. Even more important would however be smoothing of curves. i.e. make serpentine corners on mountain streets more smooth, because otherwise if there is a say 160° corner, it will add a big time penalty, which in a car is more or less correct, but on a bicycle overrated.
This is actually not that difficult, because you can do it with an additional filter for the ways. It is a local modification for each way.
However, how do you want to do the merging without loosing attributes (i.e. roadname changes, bridge, etc..), I think this could only work by running after the main processing, and merging everything identical if possible.
Otherwise before merging there needs to be a check whether there is not a rule in the style-file that would change either the name of the road OR the type (0x??) of a road. If both not changed then merge it.
The trick would be to do the merging on the data just before it is converted into the Garmin format, after the style files are applied. Then you have the final settings of all attributes and the name and can merge only those ways that are identical in that respect. This is also the point when the filters get applied to the ways. The problem here is that the filters see only each way in turn, so they can only perform modifications on a single way. Unfortunately it is not that easy to find a place in the source code where you could apply the merging of ways, which is the reason why I haven't had a go at it yet. Regards Thilo
However, how do you want to do the merging without loosing attributes (i.e. roadname changes, bridge, etc..), I think this could only work by running after the main processing, and merging everything identical if possible.
Otherwise before merging there needs to be a check whether there is not a rule in the style-file that would change either the name of the road OR the type (0x??) of a road. If both not changed then merge it.
The trick would be to do the merging on the data just before it is converted into the Garmin format, after the style files are applied. Then you have the final settings of all attributes and the name and can merge only those ways that are identical in that respect. This is also the point when the filters get applied to the ways. The problem here is that the filters see only each way in turn, so they can only perform modifications on a single way. Unfortunately it is not that easy to find a place in the source code where you could apply the merging of ways, which is the reason why I haven't had a go at it yet.
Find attached an patch of my working copy. It is based mainly on my old simplifyWays patch. Its diffed against the current R1102. The main idea is to merge the lines directly before input them to the filters. It improves drawing speed on my etrex considerably on very low zooms. I'm not sure, if it is the optimal place to do the merging, but it seems to work. Its not a clean patch for now, but the diff of my working copy.
On Sat, Jul 25, 2009 at 3:55 PM, Johann Gail<johann.gail@gmx.de> wrote:
Find attached an patch of my working copy. It is based mainly on my old simplifyWays patch. Its diffed against the current R1102.
The main idea is to merge the lines directly before input them to the filters. It improves drawing speed on my etrex considerably on very low zooms. I'm not sure, if it is the optimal place to do the merging, but it seems to work.
I tested this patch, and it seems to work well. I have not yet thoroughly tested it, and I have not done a speed comparison, but I think the patch is quite worthwhile. Are you considering further work on it, or getting it committed? Cheers and Thanks.
I'm currently working on it. Have you tried the patch together with routing? In my trials the routing was completely broken after applying the patch. That is because the merging is done *after* all the routing info is generated. So if two ways are merged into one, the references in the routing part of the map point nowhere. Also the turn restrictions break, because they also refer to the unmerged ways. I'm trying to apply the merging *before* the routing info and the turn restrictions are generated, but up to now I run into all kinds of trouble doing that. I hope I get it working soon, but if you like to work on it as well I can post my current diffs. Regards Thilo Am 12.08.2009 um 17:10 schrieb Clinton Gladstone:
On Sat, Jul 25, 2009 at 3:55 PM, Johann Gail<johann.gail@gmx.de> wrote:
Find attached an patch of my working copy. It is based mainly on my old simplifyWays patch. Its diffed against the current R1102.
The main idea is to merge the lines directly before input them to the filters. It improves drawing speed on my etrex considerably on very low zooms. I'm not sure, if it is the optimal place to do the merging, but it seems to work.
I tested this patch, and it seems to work well. I have not yet thoroughly tested it, and I have not done a speed comparison, but I think the patch is quite worthwhile. Are you considering further work on it, or getting it committed?
Cheers and Thanks. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
On Wed, Aug 12, 2009 at 8:01 PM, Thilo Hannemann<thannema@gmx.de> wrote:
I'm currently working on it. Have you tried the patch together with routing? In my trials the routing was completely broken after applying the patch.
I have tried this with routing, but not yet noticed a significant difference. This leads me to strongly believe that I have either incorrectly applied the patch or that I am incorrectly using the command line options. I will check this again later.
I hope I get it working soon, but if you like to work on it as well I can post my current diffs.
Since I neither have much time to work on this, nor do I have the necessary knowledge, I think you can save yourself the effort of posting your diffs. ;-) But once again, thank you very much. Cheers.
Thilo Hannemann schrieb:
Here is another approach to the "lost last point". The Douglas Peucker filter is improved so that it can deal with identical start- and endpoints. If the start- and the endpoint are identical, the algorithm calculates the distance between these identical points and the point p. So the polygon is not split at point N/2, but at the point that has the greatest distance from the start-/endpoint.
I've tested this patch and think it is ok. I attached an patch for the recent revision, as the one from Thilo didn't work for me. I think it is ok to commit it.
participants (5)
-
Clinton Gladstone -
Felix Hartmann -
Johann Gail -
Mark Burton -
Thilo Hannemann