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

Wed Jun 17 19:32:24 BST 2009

>>     
>>>> 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.
>>>       
This is correct. The algorithm does not depend on the lat and long 
values. It doesn't work with the internal units. This units are locally 
like kartesian coordinates but with changing scales.
Therfore I call the function distance(), which I expect to return 
distance values in the unit m independent of the lan/lot of the points.

The triangle of the points could be seen as nearly flat. So the distance 
calculation should not return any significant errors.

It should calculate the distance of a point to the line.

>> 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.
>>>>         
Yes, I have thought about some optimasations, but not had the right 
idea. I find it a good idea to extract the sqrt() from the loop or even 
better compare the value to the squared allowedError.
But on the other hand it makes the formula a little more complicated and 
even more programmers ask about the function of it....

I length of zero should not be possible at this point, as it would mean 
two points with the same coordintates. This are filtered out in a 
previous stage. But you are correct, some assertion would be a good idea.
>>> 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...
>
>   

Very well explained. Now I understand the distance formula too :-)

I'm not a mathematician too, but I found this formula on some web page 
and testing it with some example values shows me, that it works correctly.

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

You were correct. At this place the comment is wrong.

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

Yes, the code was from me, but I have only sporadically time for this 
mailing list. So if some important questions arive, write to the list. 
But I cannot garantee fast answer.

Regards,
Johann