help needed

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

help needed

Gerd Petermann
Hi all,

I am still trying to find a better solution for the problem
posted by Roger Calvert:
http://gis.19327.n5.nabble.com/Incorrect-compilation-of-grid-lines-tp5809502.html

We are using some approximations to speed up calculations,
most of them work fine as long as distances are rather short.

On the other hand, mkgmap doesn't check if distances are short,
so in some cases we have rather large errors.

I found two sources for formulas:
http://www.movable-type.co.uk/scripts/latlong.html
and
http://williams.best.vwh.net/avform.htm

The latter gives an example to verify the code. I've coded
some lines in Java and got similar results as in the "worked example".
I've then tried to verify the example in JOSM,
esp. the cross-track-error.
Unfortunately, when I try to draw a (nearly) perpendicular
line from point A to line LAX-JFK, JOSM says the line is ~27.7 km
long, while the example calculations are near 13.8 km or
about 50% of the JOSM value.

What am I getting wrong?

Gerd


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

JFX-LAX.osm (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: help needed

popej
Hi Gerd,

I have looked at your example file in QGIS and Global Mapper and they
show distance like JOSM. I don't know why there is so big difference. My
guess is that it could be caused by spherical versus ellipsoidal model
of the Earth. Maybe you could test algorithms based on Vincenty's
formulae? See for example:

http://www.gavaghan.org/blog/free-source-code/geodesy-library-vincentys-formula-java/

http://geographiclib.sourceforge.net/html/java/

--
Best regards,
Andrzej
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

Gerd Petermann
Hi Andrzej,

thanks for the hints, I'll have a look at them tomorrow. I think
"Spherical versus ellipsoidal model" as a reason is unlikely, the difference should
be < 1 %, not ~50%
Today I looked at various webpages which calculate the distance between
two points, e.g. airports. It is quite funny how different the results are,
probably because some are using R=6371 km and others 6378.135 m or
values between.

Gerd
 

popej wrote
Hi Gerd,

I have looked at your example file in QGIS and Global Mapper and they
show distance like JOSM. I don't know why there is so big difference. My
guess is that it could be caused by spherical versus ellipsoidal model
of the Earth. Maybe you could test algorithms based on Vincenty's
formulae? See for example:

http://www.gavaghan.org/blog/free-source-code/geodesy-library-vincentys-formula-java/

http://geographiclib.sourceforge.net/html/java/

--
Best regards,
Andrzej
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

Bill
Gerd,
I tried to confirm a couple of things, and ran out of time, but thought
the ideas might be of use to you.
1) Are you sure that both the algorithm and JOSM are drawing the same
line between LAX and JFK.  For example, one could be using a great
circle route, and the other using a direct heading.  This would result
in a different distance between A and the line.
2) Have you tried using a two points for the reference line that are
directly North/South of each other, or on the equator as these should
result in the reference line being the same regardless of the method of
determining it.

   Bill

p.s. Thank you, and everyone else who is continuing to improve and
support mkgmap.


On 07/31/2014 09:41 AM, GerdP wrote:

> Hi Andrzej,
>
> thanks for the hints, I'll have a look at them tomorrow. I think
> "Spherical versus ellipsoidal model" as a reason is unlikely, the difference
> should
> be < 1 %, not ~50%
> Today I looked at various webpages which calculate the distance between
> two points, e.g. airports. It is quite funny how different the results are,
> probably because some are using R=6371 km and others 6378.135 m or
> values between.
>
> Gerd
>  
>
>
> popej wrote
>> Hi Gerd,
>>
>> I have looked at your example file in QGIS and Global Mapper and they
>> show distance like JOSM. I don't know why there is so big difference. My
>> guess is that it could be caused by spherical versus ellipsoidal model
>> of the Earth. Maybe you could test algorithms based on Vincenty's
>> formulae? See for example:
>>
>> http://www.gavaghan.org/blog/free-source-code/geodesy-library-vincentys-formula-java/
>>
>> http://geographiclib.sourceforge.net/html/java/
>>
>> --
>> Best regards,
>> Andrzej
>> _______________________________________________
>> mkgmap-dev mailing list
>> mkgmap-dev@.org
>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
>
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/help-needed-tp5813164p5813323.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

Gerd Petermann
Hi Bill,

> I tried to confirm a couple of things, and ran out of time, but thought
> the ideas might be of use to you.
> 1) Are you sure that both the algorithm and JOSM are drawing the same
> line between LAX and JFK. For example, one could be using a great
> circle route, and the other using a direct heading. This would result
> in a different distance between A and the line.

I think JOSM does it right.

> 2) Have you tried using a two points for the reference line that are
> directly North/South of each other, or on the equator as these should
> result in the reference line being the same regardless of the method of
> determining it.

Good idea! I thought I did that before, but maybe with wrong values.
I found that the formula (or my implementation) is wrong.
Now I can try to find the reason...

Gerd

>
> Bill
>
> p.s. Thank you, and everyone else who is continuing to improve and
> support mkgmap.
>
>
> On 07/31/2014 09:41 AM, GerdP wrote:
> > Hi Andrzej,
> >
> > thanks for the hints, I'll have a look at them tomorrow. I think
> > "Spherical versus ellipsoidal model" as a reason is unlikely, the difference
> > should
> > be < 1 %, not ~50%
> > Today I looked at various webpages which calculate the distance between
> > two points, e.g. airports. It is quite funny how different the results are,
> > probably because some are using R=6371 km and others 6378.135 m or
> > values between.
> >
> > Gerd
> >
> >
> >
> > popej wrote
> >> Hi Gerd,
> >>
> >> I have looked at your example file in QGIS and Global Mapper and they
> >> show distance like JOSM. I don't know why there is so big difference. My
> >> guess is that it could be caused by spherical versus ellipsoidal model
> >> of the Earth. Maybe you could test algorithms based on Vincenty's
> >> formulae? See for example:
> >>
> >> http://www.gavaghan.org/blog/free-source-code/geodesy-library-vincentys-formula-java/
> >>
> >> http://geographiclib.sourceforge.net/html/java/
> >>
> >> --
> >> Best regards,
> >> Andrzej
> >> _______________________________________________
> >> mkgmap-dev mailing list
> >> mkgmap-dev@.org
> >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >
> >
> >
> >
> > --
> > View this message in context: http://gis.19327.n5.nabble.com/help-needed-tp5813164p5813323.html
> > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > _______________________________________________
> > mkgmap-dev mailing list
> > [hidden email]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

Gerd Petermann
Hi all,

I think my problem is solved.
JOSM doesn't display the so called great circle which is the shortest line between two
points on a spere. I am not sure what exactly JOSM displays, but obviously
I can't use it to verify the calculations.

Thanks for the hints!

Gerd

GerdP wrote
Hi Bill,

> I tried to confirm a couple of things, and ran out of time, but thought
> the ideas might be of use to you.
> 1) Are you sure that both the algorithm and JOSM are drawing the same
> line between LAX and JFK.  For example, one could be using a great
> circle route, and the other using a direct heading.  This would result
> in a different distance between A and the line.

I think JOSM does it right.

> 2) Have you tried using a two points for the reference line that are
> directly North/South of each other, or on the equator as these should
> result in the reference line being the same regardless of the method of
> determining it.

Good idea! I thought I did that before, but maybe with wrong values.
I found that the formula (or my implementation) is wrong.
Now I can try to find the reason...

Gerd

>
>    Bill
>
> p.s. Thank you, and everyone else who is continuing to improve and
> support mkgmap.
>
>
> On 07/31/2014 09:41 AM, GerdP wrote:
> > Hi Andrzej,
> >
> > thanks for the hints, I'll have a look at them tomorrow. I think
> > "Spherical versus ellipsoidal model" as a reason is unlikely, the difference
> > should
> > be < 1 %, not ~50%
> > Today I looked at various webpages which calculate the distance between
> > two points, e.g. airports. It is quite funny how different the results are,
> > probably because some are using R=6371 km and others 6378.135 m or
> > values between.
> >
> > Gerd
> >  
> >
> >
> > popej wrote
> >> Hi Gerd,
> >>
> >> I have looked at your example file in QGIS and Global Mapper and they
> >> show distance like JOSM. I don't know why there is so big difference. My
> >> guess is that it could be caused by spherical versus ellipsoidal model
> >> of the Earth. Maybe you could test algorithms based on Vincenty's
> >> formulae? See for example:
> >>
> >> http://www.gavaghan.org/blog/free-source-code/geodesy-library-vincentys-formula-java/
> >>
> >> http://geographiclib.sourceforge.net/html/java/
> >>
> >> --
> >> Best regards,
> >> Andrzej
> >> _______________________________________________
> >> mkgmap-dev mailing list
> >> mkgmap-dev@.org
> >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >
> >
> >
> >
> > --
> > View this message in context: http://gis.19327.n5.nabble.com/help-needed-tp5813164p5813323.html
> > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > _______________________________________________
> > mkgmap-dev mailing list
> > [hidden email]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
     
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

popej
Hi Gerd,

 > JOSM doesn't display the so called great circle

It's a bit disappointing that QGIS and Global Mapper don't use great
circles either. Probably for faster redraw.

Global Mapper can use great circle for distance tool. Drawing all lines
with this tool I can estimate distance to about 14km. Funny is that
great circle comes 14km above point D, while rhumb line is 29km below D.
Your reference was correct saying, that D is right of course.

Mapsource draws direct routes as great circle, this can be used to
calculate distance too, see attached picture.

--
Best regards,
Andrzej



_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

orto.png (13K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: help needed

osm-9
In reply to this post by popej
I'm not sure if it is of any help, but with http://yournavigation.org 
(which also uses OSM) you can specify which distance algorithm to use.
It uses this PHP class for the calculations:
https://github.com/treffynnon/Geographic-Calculations-in-PHP

Available methods:
Vincenty
Simplified great circle
Haversine
Cosine

Add a &v= parameter to the request to choose the algorithm:
http://wiki.openstreetmap.org/wiki/YOURS#Parameters

/offtopic: I see YOURS should be upgraded with the new class...


On 31/07/2014 18:21, Andrzej Popowski wrote:

> Hi Gerd,
>
> I have looked at your example file in QGIS and Global Mapper and they
> show distance like JOSM. I don't know why there is so big difference. My
> guess is that it could be caused by spherical versus ellipsoidal model
> of the Earth. Maybe you could test algorithms based on Vincenty's
> formulae? See for example:
>
> http://www.gavaghan.org/blog/free-source-code/geodesy-library-vincentys-formula-java/
>
>
> http://geographiclib.sourceforge.net/html/java/
>

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

Gerd Petermann
Hi Lambertus,

thanks again. I want to solve this problem:
In mkgmap we have to calculate the great-circle distance very often,
as well as the cross track error.
We need the values for all kinds of algos (nearest point, DP-Filter,
WrongAngleFixer etc.), not just for the img itself.
Up to now we use those formulas which are fastest,
but as we saw they do not always work.
So I want to find a simple algo to decide whether the fast
formula is good enough.
Always using the highest precision would slow down mkgmap
by ~30 %.

Gerd


Lambertus wrote
I'm not sure if it is of any help, but with http://yournavigation.org 
(which also uses OSM) you can specify which distance algorithm to use.
It uses this PHP class for the calculations:
https://github.com/treffynnon/Geographic-Calculations-in-PHP

Available methods:
Vincenty
Simplified great circle
Haversine
Cosine

Add a &v= parameter to the request to choose the algorithm:
http://wiki.openstreetmap.org/wiki/YOURS#Parameters

/offtopic: I see YOURS should be upgraded with the new class...


On 31/07/2014 18:21, Andrzej Popowski wrote:
> Hi Gerd,
>
> I have looked at your example file in QGIS and Global Mapper and they
> show distance like JOSM. I don't know why there is so big difference. My
> guess is that it could be caused by spherical versus ellipsoidal model
> of the Earth. Maybe you could test algorithms based on Vincenty's
> formulae? See for example:
>
> http://www.gavaghan.org/blog/free-source-code/geodesy-library-vincentys-formula-java/
>
>
> http://geographiclib.sourceforge.net/html/java/
>

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

Gerd Petermann
In reply to this post by popej
Hi Andrzej,

I use MapSource 6.16.3 and it doesn't show the great circle line
when I open the attached gpx file.
What did you did to create your picture?
Up to now I found only one tool which seems to show
the great circle: Google Earth

This is quite important. If Garmin software doesn't care
about the difference, we can remove more (or different)
points from the img file without visible effects.

Ciao,
Gerd


Date: Fri, 1 Aug 2014 13:45:18 +0200
From: [hidden email]
To: [hidden email]
Subject: Re: [mkgmap-dev] help needed

Hi Gerd,

> JOSM doesn't display the so called great circle

It's a bit disappointing that QGIS and Global Mapper don't use great
circles either. Probably for faster redraw.

Global Mapper can use great circle for distance tool. Drawing all lines
with this tool I can estimate distance to about 14km. Funny is that
great circle comes 14km above point D, while rhumb line is 29km below D.
Your reference was correct saying, that D is right of course.

Mapsource draws direct routes as great circle, this can be used to
calculate distance too, see attached picture.

--
Best regards,
Andrzej



_______________________________________________ mkgmap-dev mailing list [hidden email] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

osm-8
In reply to this post by Gerd Petermann
Hi Gerd,

as I got it right, in nearly all typical cases the fast algo would be ok
because the error is pretty small. So what about calculating always the
fast algo and if the calculated distance is larger then X, mkgmap
calculates the distance again with the more precise algo.

Henning

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

Gerd Petermann
Hi Henning,

you are probably right, maybe the decision also depends
on the avg. latitude.

FYI:
we are talking about two different distances:
1) The distance between two points on earth
2) The (shortest) distance between a given point
and a (great circle) path between two other points.

The algo for 2) uses the results from 1).
In some cases even very small errors in 1) result
in rather big errors in 2). The same problem
occurs when we calculate angles.

Gerd

osm-8 wrote
Hi Gerd,

as I got it right, in nearly all typical cases the fast algo would be ok
because the error is pretty small. So what about calculating always the
fast algo and if the calculated distance is larger then X, mkgmap
calculates the distance again with the more precise algo.

Henning

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

popej
In reply to this post by Gerd Petermann
Hi Gerd,

 > I use MapSource 6.16.3 and it doesn't show the great circle line
 > when I open the attached gpx file.

I can't see your attachment.

Mapsoruce draws great circle for direct routes (select "Use Direct
Routes" in Preferences). I have marked waypoints for LAX an JFK and then
created a route form these points. See gpx attached to my post.

In my opinion you should go for a correct solution regardless of speed
penalty. I would prefer reliable program over a fast one. Later you
probably can optimize some computations, where you know for sure, that
error is small.

--
Best regards,
Andrzej

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

lax-jfk.gpx (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: help needed

Gerd Petermann
Hi Andrzej,

sorry, I forgot the attachment. The difference to yours is that
I created a gpx track, not a route.
Now I can reproduce your results :-)

Reg. Precision:
"Correct" results are an illusion. Even the most complex algos
will use some simplification (earth is a sphere or ellipsoid, but has no mountains),
and when it comes to writing data to the img, we are rounding
so heavily that almost all information gets lost.

Some numbers:
With maps produced by mkgmap, the length of an arc is
saved in units of 4.8m, means, an arcs is 4.8 or 9.6 or 14.4 or ... meter
long.
The bearing is often encoded with only 4 bits, sometimes with 8 bits, means,
we have to accept an error of at least 0.7 degrees, and the device doesn't
care very much about these values.


The problem is that we do also complex calculations based
on the calculated values, and here the rounding errors
as well as the simplifications play a role.
We use the results of these complex calcs to decide
if the line a-b-c can be reduced to a-c because
the distance between b and a-c is so small that it doesn't
matter for the Garmin algos.
This means the Garmin program will show the same map
and calculate the same routes and travel times with and
without point b.

I am now going to find out if Garmin draws the line a-c
(saved in the img) as a great circle or not, depending
on that we have to use different algos.

Do you agree?

Gerd

popej wrote
Hi Gerd,

 > I use MapSource 6.16.3 and it doesn't show the great circle line
 > when I open the attached gpx file.

I can't see your attachment.

Mapsoruce draws great circle for direct routes (select "Use Direct
Routes" in Preferences). I have marked waypoints for LAX an JFK and then
created a route form these points. See gpx attached to my post.

In my opinion you should go for a correct solution regardless of speed
penalty. I would prefer reliable program over a fast one. Later you
probably can optimize some computations, where you know for sure, that
error is small.

--
Best regards,
Andrzej

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

lax-jfk.gpx (3K) <http://gis.19327.n5.nabble.com/attachment/5813453/0/lax-jfk.gpx>
Reply | Threaded
Open this post in threaded view
|

Re: help needed

popej
Hi Gerd,

 > Reg. Precision:
 > "Correct" results are an illusion.

I don't know what exactly the problem is, so my idea was more generic. I
mean that program speed is only a secondary requirements, I wouldn't
hesitate to use a suitable algorithm even if it makes program slower.

 > I am now going to find out if Garmin draws the line a-c
 > (saved in the img) as a great circle or not, depending
 > on that we have to use different algos.

MapSource and BaseCamp display line the same way as JOSM, you can see it
on picture from my previous mail. Orange lines are highways from your
OSM file.

Is it a problem of simplification of long lines that distorted
geographical grid? I think you won't get an easy solution here, since it
could depend on source data.

If source data assume that 2 points create line on great circle, then it
won't be displayed correctly in Mapsource or JOSM. If source data
contains multiple intermediate points on great circle, than
simplification which use great circle distance, will remove intermediate
points and damage correct presentation of lines.

My first idea is to simply leave points, that are far enough form next
points on line. Far enough could be for example 1km, or 1000 times of
simplification distance. This won't increase much map size but preserve
long line shape, regardless of calculation method used for simplification.

Other problem could be splitting of objects, when truncating them to
tile area and TRE subdivisions. Probably here should be used great
circle algorithms.

--
Best regards,
Andrzej
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: help needed

popej
In reply to this post by Gerd Petermann
Hi Gerd,

I have searched a bit and my conclusion is that almost no software use
geodesics (big circle) to connect points. The general idea is, that
shape of a line between points is undefined. Software simply draws
straight line in current projection. It is up to creator of input data
to supply enough nodes to preserve real shape of an object.

cGPSmapper does the same, it split long line as a straight line in WGS84.

I think mkgmap can take the same approach.

Does mkgmap preserve crossing points for non-routable lines? In case of
a grid this should be enough to preserve shape of a grid, assuming that
crossings are included in source data.

--
Best regards,
Andrzej
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev