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... 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
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-form... http://geographiclib.sourceforge.net/html/java/ -- Best regards, Andrzej
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-form...
http://geographiclib.sourceforge.net/html/java/
-- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- 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.
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-form...
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 mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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-form...
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 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
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-form...
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
mkgmap-dev@.org
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/help-needed-tp5813164p5813383.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
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
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: popej@poczta.onet.pl To: mkgmap-dev@lists.mkgmap.org.uk 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 mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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
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
mkgmap-dev@.org
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>;
-- View this message in context: http://gis.19327.n5.nabble.com/help-needed-tp5813164p5813457.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
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
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
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-form...
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-form...
_______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/help-needed-tp5813164p5813404.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
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
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
mkgmap-dev@.org
-- View this message in context: http://gis.19327.n5.nabble.com/help-needed-tp5813164p5813449.html Sent from the Mkgmap Development mailing list archive at Nabble.com.
participants (6)
-
Andrzej Popowski -
Bill -
Gerd Petermann -
GerdP
-
Henning Scholland -
Lambertus