Re: [mkgmap-dev] Overview map: tiny patch/review series
Hi Mark, Am 16.06.2009 um 08:33 schrieb Mark Burton: Recently, Coord.distance() was replaced with a much speedier implementation because a lot of cpu cycles were being wasted there. The newer function appears to be accurate enough for our purposes. The DP code contains another distance calculation. What you must calculate there is the distance of one point to a line. The Coord.distance() is used in that formula, but I do not understand the formula itself. Maybe it's some genius trick to simplify the calculation, but I do not get it. The only thing I see is that when I reduce the error distance the simplified ways look nicer. But the preset error distance of one half of the resolution should be small enough already. So my assumption is that the actual error distance is much larger than expected, which may be due to a bug in the code. Regards Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
Hi Thilo, The DP code contains another distance calculation. What you must calculate there is the distance of one point to a line. The Coord.distance() is used in that formula, but I do not understand the formula itself. Maybe it's some genius trick to simplify the calculation, but I do not get it. The only thing I see is that when I reduce the error distance the simplified ways look nicer. But the preset error distance of one half of the resolution should be small enough already. So my assumption is that the actual error distance is much larger than expected, which may be due to a bug in the code. At the distances we're (mostly) interested in, the curvature of the earth's surface has a tiny effect (much less than the effect of hills valleys) so I guess (hope) that leaving out that factor is OK. I know that this isn't your code but it's as good a place as any to comment about it: looking at the DP code (for the first time), I immediately see that the loop that finds the max distance is (potentially) doing many more sqrts and divisions than it needs to. So even if the code is correct, it could be somewhat faster which would be worthwhile given that it gets called for every line. Eg, it could be changed to look like this: // Find point with highest distance. // Loop runs downwards, as the list length gets modified while running 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 dd = abpa * (abpa-ab) * (abpa-ap) * (abpa-bp); if (dd maxDistance) { maxDistance = dd; maxIndex = i; } } maxDistance = 2 * Math.sqrt(maxDistance) / ab; Also - you get a division by zero if ab is 0, perhaps adding a test for that before the loop would be advisable. Another minor nit - the comment is inaccurate as the list length doesn't change in this loop. Cheers, Mark ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
Hi Mark, Am 16.06.2009 um 09:18 schrieb Mark Burton: At the distances we're (mostly) interested in, the curvature of the earth's surface has a tiny effect (much less than the effect of hills valleys) so I guess (hope) that leaving out that factor is OK. The curvature may have a tiny effect, but nonetheless you should consider the coordinate system you are using. Interpreting lat and lon as cartesian coordinates (don't know whether you are really doing that) will give large errors at high latitudes. I know that this isn't your code but it's as good a place as any to comment about it: looking at the DP code (for the first time), I immediately see that the loop that finds the max distance is (potentially) doing many more sqrts and divisions than it needs to. So even if the code is correct, it could be somewhat faster which would be worthwhile given that it gets called for every line. Eg, it could be changed to look like this: // Find point with highest distance. // Loop runs downwards, as the list length gets modified while running 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 dd = abpa * (abpa-ab) * (abpa-ap) * (abpa-bp); if (dd maxDistance) { maxDistance = dd; maxIndex = i; } } maxDistance = 2 * Math.sqrt(maxDistance) / ab; Also - you get a division by zero if ab is 0, perhaps adding a test for that before the loop would be advisable. Do you understand that formula for the distance calculation? If so could you explain it for me? I don't get it. Another minor nit - the comment is inaccurate as the list length doesn't change in this loop. It is accurate, because the list length does get changed by the way the recursion works. It is not obvious, therefore this comment is really needed! Another question, just out of curiosity: Does it really mattern in Java how many sqrts or sin or cos I do? Doesn't that kind of difference get swamped by all that interpretation and memory allocation things etc. going on? With modern FPUs that kind of operation isn't that expensive (if it is done native). I would start working on the DP code if it makes sense. If somebody understands that distance formula and could explain it it would be very much appreciated. Otherwise I will have to make up my own formula (sigh...) Regards Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
Hi Thilo, At the distances we're (mostly) interested in, the curvature of the earth's surface has a tiny effect (much less than the effect of hills valleys) so I guess (hope) that leaving out that factor is OK. The curvature may have a tiny effect, but nonetheless you should consider the coordinate system you are using. Interpreting lat and lon as cartesian coordinates (don't know whether you are really doing that) will give large errors at high latitudes. I have to admit that I'm not much of a mathematician so I am quite happy to take advice as to the soundness of the current algorithm. I did test it against what we were using before and for the latitudes I was using, it appeared to work OK. I know that this isn't your code but it's as good a place as any to comment about it: looking at the DP code (for the first time), I immediately see that the loop that finds the max distance is (potentially) doing many more sqrts and divisions than it needs to. So even if the code is correct, it could be somewhat faster which would be worthwhile given that it gets called for every line. Eg, it could be changed to look like this: // Find point with highest distance. // Loop runs downwards, as the list length gets modified while running 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 dd = abpa * (abpa-ab) * (abpa-ap) * (abpa-bp); if (dd maxDistance) { maxDistance = dd; maxIndex = i; } } maxDistance = 2 * Math.sqrt(maxDistance) / ab; Also - you get a division by zero if ab is 0, perhaps adding a test for that before the loop would be advisable. Do you understand that formula for the distance calculation? If so could you explain it for me? I don't get it. Sorry, no. Another minor nit - the comment is inaccurate as the list length doesn't change in this loop. It is accurate, because the list length does get changed by the way the recursion works. It is not obvious, therefore this comment is really needed! The loop I mention does not contain any recursion. The loop in doFilter() does (it is adorned with a similar comment). Another question, just out of curiosity: Does it really mattern in Java how many sqrts or sin or cos I do? Doesn't that kind of difference get swamped by all that interpretation and memory allocation things etc. going on? With modern FPUs that kind of operation isn't that expensive (if it is done native). You're quite possibly right but some maths ops are hideously slow (i.e. acos which is used in the original distance() method). In the example above, I would argue that taking the sqrt and division outside of the loop doesn't make the code harder to understand and may yield some speedup. I would start working on the DP code if it makes sense. If somebody understands that distance formula and could explain it it would be very much appreciated. Otherwise I will have to make up my own formula (sigh...) Well, I think Johann wrote the code so maybe he will enlighten you! Cheers, Mark ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
On Tue, 16 Jun 2009 17:19:21 +0100 Mark Burton ma...@ordern.com wrote: In the example above, I would argue that taking the sqrt and division outside of the loop doesn't make the code harder to understand and may yield some speedup. Well, a quick test showed a barely perceptible gain so may as well leave the code as it is. Cheers, Mark ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
--- Mar 16/6/09, Mark Burton ma...@ordern.com ha scritto: Da: Mark Burton ma...@ordern.com Oggetto: Re: [mkgmap-dev] Overview map: tiny patch/review series A: mkgmap-dev@lists.mkgmap.org.uk Data: Martedì 16 giugno 2009, 18:19 Hi Thilo, At the distances we're (mostly) interested in, the curvature of the earth's surface has a tiny effect (much less than the effect of hills valleys) so I guess (hope) that leaving out that factor is OK. The curvature may have a tiny effect, but nonetheless you should consider the coordinate system you are using. Interpreting lat and lon as cartesian coordinates (don't know whether you are really doing that) will give large errors at high latitudes. I have to admit that I'm not much of a mathematician so I am quite happy to take advice as to the soundness of the current algorithm. I did test it against what we were using before and for the latitudes I was using, it appeared to work OK. I know that this isn't your code but it's as good a place as any to comment about it: looking at the DP code (for the first time), I immediately see that the loop that finds the max distance is (potentially) doing many more sqrts and divisions than it needs to. So even if the code is correct, it could be somewhat faster which would be worthwhile given that it gets called for every line. Eg, it could be changed to look like this: // Find point with highest distance. // Loop runs downwards, as the list length gets modified while running 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 dd = abpa * (abpa-ab) * (abpa-ap) * (abpa-bp); if (dd maxDistance) { maxDistance = dd; maxIndex = i; } } maxDistance = 2 * Math.sqrt(maxDistance) / ab; Also - you get a division by zero if ab is 0, perhaps adding a test for that before the loop would be advisable. Do you understand that formula for the distance calculation? If so could you explain it for me? I don't get it. Sorry, no. Just speculation: I've a and b that defines a line. I look for the distance between a point p and the line. Given the triangle p-a-b where p is the vertex and a-b is the base, the area of the triangle can be calculated from the lenght of its 3 sides (pa, pb, ab). After that, since the area is also base x height / 2 we can calculate the height = area / base * 2 well, the height is exactly the distance of the point p from the line a-b Maybe... Another minor nit - the comment is inaccurate as the list length doesn't change in this loop. It is accurate, because the list length does get changed by the way the recursion works. It is not obvious, therefore this comment is really needed! The loop I mention does not contain any recursion. The loop in doFilter() does (it is adorned with a similar comment). Another question, just out of curiosity: Does it really mattern in Java how many sqrts or sin or cos I do? Doesn't that kind of difference get swamped by all that interpretation and memory allocation things etc. going on? With modern FPUs that kind of operation isn't that expensive (if it is done native). You're quite possibly right but some maths ops are hideously slow (i.e. acos which is used in the original distance() method). In the example above, I would argue that taking the sqrt and division outside of the loop doesn't make the code harder to understand and may yield some speedup. I would start working on the DP code if it makes sense. If somebody understands that distance formula and could explain it it would be very much appreciated. Otherwise I will have to make up my own formula (sigh...) Well, I think Johann wrote the code so maybe he will enlighten you! Cheers, Mark ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
On Tue, Jun 16, 2009 at 07:58:24AM +0200, Thilo Hannemann wrote: Hi Elrond, [...] The problem of distorted polygons does not only appear in the overview map, it appears at all zoom levels. [...] Hi, Okay, about the DP code, I have some speculation, why it performs bad. It's a variation on what happens for the overview map in general. Rounding. Okay, let me make up an example. Let's assume, that current resolution will round to full units (you might think degree). And lets assume mathematical rounding (1.4 - 1, 1.5 - 2) A: (0.2, 2.4) B: (1.2, 2.4) C: (1.2, 2.5) so the bare inter-vectors are: A-B: (1.0, 0.0) B-C: (0.0, 0.2) Looking at that, it seems, that B is not far off from A-C. So we drop B. Now let's see, what the rounding makes out of the whole story: a = round(A): (0, 2) b = round(B): (1, 2) c = round(C): (1, 3) So for not dropping B: a-b: (1, 0) b-c: (0, 1) For dropping B: a-c: (1, 1) The distance of b to a-c is sqrt(2)/2 (0.707), so more than unit/2. Greetings Elrond ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
Am 16.06.2009 um 18:33 schrieb Marco Certelli: Just speculation: I've a and b that defines a line. I look for the distance between a point p and the line. Given the triangle p-a-b where p is the vertex and a-b is the base, the area of the triangle can be calculated from the lenght of its 3 sides (pa, pb, ab). After that, since the area is also base x height / 2 we can calculate the height = area / base * 2 well, the height is exactly the distance of the point p from the line a-b Maybe... You are right. It is Heron's formula. And from what I see the implementation is correct. Even the coordinates on the sphere are no problem, because the formula itself doesn't use lat and lon and we can assume the triangle to be flat locally. So I think the implementation is quite clever indeed. Okay. But that still doesn't explain why the map looks better if I reduce the error distance setting for the Douglas-Peucker filter. The error should be already invisible at the default setting. Regards Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
Hi Elrond, there seem to be some problems with the simplification right now. But instead of simply de-activating the simplification I think we should debug the code. Of course it's fine to de-activate it for debugging :) The problem of distorted polygons does not only appear in the overview map, it appears at all zoom levels. One problem I could identify is that the Douglas-Peucker code does remove the closing node of a polygon, but doesn't put it back after simplification. This might be ok for filled polygons, but for contour lines it is a problem. I've attached the patch that I use to solve that problem. decrease_douglas_peucker_error.patch Description: Binary data That patch also sets the error distance for the Douglas-Peucker algorithm to 1/8th of the resolution instead of one half. In my opinion this gives much nicer results. The question here is why it is so, because you shouldn't be able to see such small errors. From looking at the Douglas-Peucker code I can not put my finger on any bug. What I do not understand is the distance calculation. Anybody with insight cares to have a look at it (or explain how it works?). I'd assume that a distance calculation on a spherical surface would involve lots of trigonometric functions - which the formula in the code doesn't. Take care Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev