CODEWITHSUNDEEP
mathlanguage-agnosticgpsgeospatial
Bartosz Kołodziej
Bartosz Kołodziej

Reputation: 133

How to calculate distance between two coordinates (without floats)?

I need to calculate distance between two coordinates (lon,lat) on embedded system which doesn't have floating point type (only integers available, so no trigonometric functions and no floating point operations like sqrt).

The points are very close to each other so accuracy is not an issue.

So I can not use Haversine formula. I also can not use this simple algorithm based on Pythagoras’ theorem and equirectangular projection:

x = Δlon * cos(lat)
y = Δlat
d = R * √(x² + y²)

Because I don't have cos and sqrt functions. Maybe I could implement them somehow, but this algorithm have to be fast (embedded system).

My best bet is Pythagoras’ theorem but how to get from degrees to meters without trigonometric functions (and without sqrt)?

Upvotes: 4

Views: 2694

Answers (4)

a barking spider
a barking spider

Reputation: 633

Actually, you do have the sqrt function available to you. Check out Newton's method. It's not perfect, given that you've apparently got just integers to work with, which I'm taking to mean that your mantissas'll get chopped off at each step, but it's an option. There are also other square root approximations out there, as well. (To implement the cosine function, perhaps you could use a Taylor approximation, but I'm not sure how well that'd work here.)

Upvotes: 2

High Performance Mark
High Performance Mark

Reputation: 78316

Traditionally mariners would use Traverse Tables for this sort of computation -- see Chapter 24 of the American Practical Navigator. Which suggests that if trig and sqrt are out of the equation you might implement a lookup table -- trading space for complexity. Depending on your precise needs you may only need a partial traverse table for the latitudes you are interested in.

Upvotes: 3

Markus
Markus

Reputation: 1636

Depending on your usecase, taxicab / cityblock distance may be helpfull: https://en.wikipedia.org/wiki/Taxicab_geometry

Upvotes: 0

Christy Herron
Christy Herron

Reputation: 714

Each degree on earth is 111133.333 metres.

How you can get there without sqrt is another matter! I am at a bit of a loss to think what system/software are you using which doesn't have this basic mathematical functionality?

You can get around the floating point issue by raising everything to the power of say 1000. That's what we used to have to do with Java ME (if I remember correctly!!!)

Upvotes: -1

Related Questions