I tried to implement the Haversine formula in Pd which should give you the distance in km between two lat long coordinates.
https://en.wikipedia.org/wiki/Haversine_formula http://www.movable-type.co.uk/scripts/latlong.html
One huge obstacle is the imprecision of the 32bit floats, but even without that I can't get the formula to work. I kept 3 failed implementations in the test-case.
http://rosettacode.org/wiki/Haversine_formula
Could someone give me a hand please?
hello,
pow 2 did not like negative number. use "t f f" and "*" in order to compute the square of a number.
i correct 2 of your formula according to what i found in your link. they both gives the same result : 11805 the same value computed with your 2nd link gives 12210. for other value, it also look close. so i guess the difference is number precision.
cheers c
Le 06/06/2015 20:18, Max a écrit :
I tried to implement the Haversine formula in Pd which should give you the distance in km between two lat long coordinates.
https://en.wikipedia.org/wiki/Haversine_formula http://www.movable-type.co.uk/scripts/latlong.html
One huge obstacle is the imprecision of the 32bit floats, but even without that I can't get the formula to work. I kept 3 failed implementations in the test-case.
http://rosettacode.org/wiki/Haversine_formula
Could someone give me a hand please?
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Merci Cyrille,
in the formula the intermediate steps are quite small fractions and it seems their precision is important. In the test case the Pd implementation is 8917.74 km off the proper result (2887.26). However I need a precision of about 1m.
So I assume the haversine formula is not implementable in Pd at all? (unless double precision will be there that is)
Or is there a workaround?
m.
On 2015년 06월 07일 05:05, Cyrille Henry wrote:
hello,
pow 2 did not like negative number. use "t f f" and "*" in order to compute the square of a number.
i correct 2 of your formula according to what i found in your link. they both gives the same result : 11805 the same value computed with your 2nd link gives 12210. for other value, it also look close. so i guess the difference is number precision.
cheers c
Le 06/06/2015 20:18, Max a écrit :
I tried to implement the Haversine formula in Pd which should give you the distance in km between two lat long coordinates.
https://en.wikipedia.org/wiki/Haversine_formula http://www.movable-type.co.uk/scripts/latlong.html
One huge obstacle is the imprecision of the 32bit floats, but even without that I can't get the formula to work. I kept 3 failed implementations in the test-case.
http://rosettacode.org/wiki/Haversine_formula
Could someone give me a hand please?
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
On 07/06/15 03:48, Max wrote:
In the test case the Pd implementation is 8917.74 km off the proper result (2887.26). However I need a precision of about 1m.
Circumference of the Earth in meters: 40,075,000 Accuracy of single precision (24bit): 16,777,216
So your input values will already be inaccurate before you even start messing with rounding errors etc.
So I assume the haversine formula is not implementable in Pd at all? (unless double precision will be there that is)
I guess so.
Or is there a workaround?
Not easy at all, but:
Maybe use two floats at different scales 'a' (close to the true value), 'b' (the residual difference from the true value) to express each coordinate 'c', where:
c = a + b
This would give around 48bits, which should be enough. Actually performing the addition would give just 'a', due to limited precision. You have to work with the unpleasant properties of floating point numbers, like "(a + b) - b" not always being equal to "a".
There are a few blog posts out there about using it on GPU with GLSL ("emulated double", "double-single"), and there is the QD package for "double-double" and "quad-double" in C++ and FORTRAN (maybe with C wrappers), there's a Haskell library called "compensated" which might give some ideas also.
You'll probably also need to do some algebraic manipulations with trigonometric identities etc to get accurate results.
See: https://www.thasler.com/blog/blog/glsl-part2-emu http://crd-legacy.lbl.gov/~dhbailey/mpdist/ http://hackage.haskell.org/package/compensated https://en.wikipedia.org/wiki/List_of_trigonometric_identities
Claude
You'll need to do the calculations in an external, where you can use double precision.
And..... TADA! Here's the external. I just copied in the C code from the Rosettacode link you sent. It gives 2887.26 as the result now.
The external code is here: https://github.com/jwmatthys/haversine-pd
I built the linux version already. It should be easy to build others.
Joel
On 06/06/2015 09:48 PM, Max wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Merci Cyrille,
in the formula the intermediate steps are quite small fractions and it seems their precision is important. In the test case the Pd implementation is 8917.74 km off the proper result (2887.26). However I need a precision of about 1m.
So I assume the haversine formula is not implementable in Pd at all? (unless double precision will be there that is)
Or is there a workaround?
m.
On 2015년 06월 07일 05:05, Cyrille Henry wrote:
hello,
pow 2 did not like negative number. use "t f f" and "*" in order to compute the square of a number.
i correct 2 of your formula according to what i found in your link. they both gives the same result : 11805 the same value computed with your 2nd link gives 12210. for other value, it also look close. so i guess the difference is number precision.
cheers c
Le 06/06/2015 20:18, Max a écrit :
I tried to implement the Haversine formula in Pd which should give you the distance in km between two lat long coordinates.
https://en.wikipedia.org/wiki/Haversine_formula http://www.movable-type.co.uk/scripts/latlong.html
One huge obstacle is the imprecision of the 32bit floats, but even without that I can't get the formula to work. I kept 3 failed implementations in the test-case.
http://rosettacode.org/wiki/Haversine_formula
Could someone give me a hand please?
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1
iEYEARECAAYFAlVzsO0ACgkQ3EB7kzgMM6KETQCfRvgOmpqbmyhZaH2Y5hzsRHlC XOgAnR+6lqxJfjTj5k7vR747UU8ATrqA =pBZv -----END PGP SIGNATURE-----
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Le 07/06/2015 04:48, Max a écrit :
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Merci Cyrille,
in the formula the intermediate steps are quite small fractions and it seems their precision is important. In the test case the Pd implementation is 8917.74 km off the proper result (2887.26). However I need a precision of about 1m.
i don't know how you get the 2887.26 km proper result : it's not the value computed by the website you send (using value in the patch).
So I assume the haversine formula is not implementable in Pd at all? (unless double precision will be there that is)
Or is there a workaround?
i'll thing about it. cheers c
m.
On 2015년 06월 07일 05:05, Cyrille Henry wrote:
hello,
pow 2 did not like negative number. use "t f f" and "*" in order to compute the square of a number.
i correct 2 of your formula according to what i found in your link. they both gives the same result : 11805 the same value computed with your 2nd link gives 12210. for other value, it also look close. so i guess the difference is number precision.
cheers c
Le 06/06/2015 20:18, Max a écrit :
I tried to implement the Haversine formula in Pd which should give you the distance in km between two lat long coordinates.
https://en.wikipedia.org/wiki/Haversine_formula http://www.movable-type.co.uk/scripts/latlong.html
One huge obstacle is the imprecision of the 32bit floats, but even without that I can't get the formula to work. I kept 3 failed implementations in the test-case.
http://rosettacode.org/wiki/Haversine_formula
Could someone give me a hand please?
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1
iEYEARECAAYFAlVzsO0ACgkQ3EB7kzgMM6KETQCfRvgOmpqbmyhZaH2Y5hzsRHlC XOgAnR+6lqxJfjTj5k7vR747UU8ATrqA =pBZv -----END PGP SIGNATURE-----
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
some people were saying expr does internal double precision calculation, is it true? i dont think so...
2015-06-07 3:10 GMT-03:00 Cyrille Henry ch@chnry.net:
Le 07/06/2015 04:48, Max a écrit :
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Merci Cyrille,
in the formula the intermediate steps are quite small fractions and it seems their precision is important. In the test case the Pd implementation is 8917.74 km off the proper result (2887.26). However I need a precision of about 1m.
i don't know how you get the 2887.26 km proper result : it's not the value computed by the website you send (using value in the patch).
So I assume the haversine formula is not implementable in Pd at all? (unless double precision will be there that is)
Or is there a workaround?
i'll thing about it. cheers
c
m.
On 2015년 06월 07일 05:05, Cyrille Henry wrote:
hello,
pow 2 did not like negative number. use "t f f" and "*" in order to compute the square of a number.
i correct 2 of your formula according to what i found in your link. they both gives the same result : 11805 the same value computed with your 2nd link gives 12210. for other value, it also look close. so i guess the difference is number precision.
cheers c
Le 06/06/2015 20:18, Max a écrit :
I tried to implement the Haversine formula in Pd which should give you the distance in km between two lat long coordinates.
https://en.wikipedia.org/wiki/Haversine_formula http://www.movable-type.co.uk/scripts/latlong.html
One huge obstacle is the imprecision of the 32bit floats, but even without that I can't get the formula to work. I kept 3 failed implementations in the test-case.
http://rosettacode.org/wiki/Haversine_formula
Could someone give me a hand please?
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1
iEYEARECAAYFAlVzsO0ACgkQ3EB7kzgMM6KETQCfRvgOmpqbmyhZaH2Y5hzsRHlC XOgAnR+6lqxJfjTj5k7vR747UU8ATrqA =pBZv -----END PGP SIGNATURE-----
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Hi,
On 07/06/2015 04:48, Max wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Merci Cyrille,
in the formula the intermediate steps are quite small fractions and it seems their precision is important. In the test case the Pd implementation is 8917.74 km off the proper result (2887.26). However I need a precision of about 1m.
So I assume the haversine formula is not implementable in Pd at all? (unless double precision will be there that is)
I had a go at immplementing it in Pd Vanilla, with a few [expr], and the result seems the one expected... no?
Lorenzo
ahah!! using -118.4 better than 118.4 also gives me the expected result. (2287.26)
all confusion came that i i was using the wrong set of value...
cheer c
Le 08/06/2015 11:10, Lorenzo Sutton a écrit :
Hi,
On 07/06/2015 04:48, Max wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Merci Cyrille,
in the formula the intermediate steps are quite small fractions and it seems their precision is important. In the test case the Pd implementation is 8917.74 km off the proper result (2887.26). However I need a precision of about 1m.
So I assume the haversine formula is not implementable in Pd at all? (unless double precision will be there that is)
I had a go at immplementing it in Pd Vanilla, with a few [expr], and the result seems the one expected... no?
Lorenzo
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Yes, I just realized too. Sorry for the confusion. So it seems it is possible to implement it in Pd! Even with only 32bit floats.
Attached all three working implementations and I added also the equirectangular approximation which should be faster and still accurate for short distances.
Thank you everyone very much!
On 2015년 06월 08일 18:22, Cyrille Henry wrote:
ahah!! using -118.4 better than 118.4 also gives me the expected result. (2287.26)
all confusion came that i i was using the wrong set of value...
cheer c
Le 08/06/2015 11:10, Lorenzo Sutton a écrit :
Hi,
On 07/06/2015 04:48, Max wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Merci Cyrille,
in the formula the intermediate steps are quite small fractions and it seems their precision is important. In the test case the Pd implementation is 8917.74 km off the proper result (2887.26). However I need a precision of about 1m.
So I assume the haversine formula is not implementable in Pd at all? (unless double precision will be there that is)
I had a go at immplementing it in Pd Vanilla, with a few [expr], and the result seems the one expected... no?
Lorenzo
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
-
Alexandre Torres Porres -
Claude Heiland-Allen -
Cyrille Henry -
Joel Matthys -
Lorenzo Sutton -
Max