Re: [mkgmap-dev] Overview map: tiny patch/review series

2009-06-16 Thread Thilo Hannemann

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

2009-06-16 Thread Mark Burton

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

2009-06-16 Thread Thilo Hannemann

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

2009-06-16 Thread Mark Burton

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

2009-06-16 Thread Mark Burton

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

2009-06-16 Thread Marco Certelli



--- 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

2009-06-16 Thread Elrond
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

2009-06-16 Thread Thilo Hannemann


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

2009-06-15 Thread Thilo Hannemann

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