What code is written behind -[CLLocation distanceFromLocation:] or MKMetersBetweenMapPoints?

Question

I would be thankful to anyone, who could explain to me an algorithm of how one of these methods (or both) work:

I have two CLLocationCoordinate2Ds or two MKMapPoints - what calculations should I perform to calculate a distance beetween them with respect to real-world surface of earth? (Obviously, stand-alone calculation of Euclidean distance is not applicable to this task.)

Background: I want to know if a knowledge of the internals of these methods would help me to optimize some calculations involving large numbers of points on a MapKit map.

Something like [this](http://www.movable-type.co.uk/scripts/latlong.html) or maybe [this](http://stackoverflow.com/questions/27928/how-do-i-calculate-distance-between-two-latitude-longitude-points) or perhaps [the answer to one of these questions](http://gis.stackexchange.com/questions/tagged/distance)? — David Rönnqvist, Jan 20 '14 at 18:58
It seems more helpful to describe the calculations you want to perform on your set of points and ask a question that about optimizations. Currently you are asking about an implementation detail of a framework method that is subject to change and probably not known to people outside of Apple. — Nikolai Ruhe, Jan 20 '14 at 19:40
@DavidRönnqvist, [this one is closer](http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe#Objective_C). — Stanislav Pankevich, Jan 20 '14 at 19:43
@NikolaiRuhe, thanks for the answer. What I am asking here is not about strict implementations of Apple API, but is likely about a _hints_ on how they implement them. Honestly speaking, I felt I had asked a vague question after I posted it. — Stanislav Pankevich, Jan 20 '14 at 19:46

score 1 · Accepted Answer · answered Jan 20 '14 at 20:21

1

The wikipedia article on Geographical distance has some formulae to calculate geodesic distances.

Here is a piece of code I'm currently using that gave me acceptable results:

const float EarthRadius = 6378137.0f;

float SquaredGeodesicDistance(CLLocationCoordinate2D a, CLLocationCoordinate2D b)
{
    float dtheta = (a.latitude - b.latitude) * (M_PI / 180.0);
    float dlambda = (a.longitude - b.longitude) * (M_PI / 180.0);
    float mean_t = (a.latitude + b.latitude) * (M_PI / 180.0) / 2.0;
    float cos_meant = cosf(mean_t);

    return (EarthRadius * EarthRadius) * (dtheta * dtheta + cos_meant * cos_meant * dlambda * dlambda);
}

float GeodesicDistance(CLLocationCoordinate2D a, CLLocationCoordinate2D b)
{
    return sqrtf(SquaredGeodesicDistance(a, b));
}

answered Jan 20 '14 at 20:21

Taum

2,511
18
18

I will test your example tomorrow. For now I can say, that it is very dangerous to use floats when you are dealing with CLLocationCoordinate2Ds which are CLLocationDegrees-based (based on double) - it is most likely that you lose a precision in your calculations. – Stanislav Pankevich Jan 20 '14 at 20:27
Then use double instead I guess? Shouldn't make much of a difference in the algorithm right? Anyway that algorithm is already a rough approximation, but coordinates and distances don't usually need to be precise to the meter (at least in my app) – Taum Jan 20 '14 at 20:29
Also note that this will give you results that are way off for large distances (think >1000km). Like I said if your application needs something more precise look at the wikipedia page I linked to for more complex but more accurate algorithms. – Taum Jan 20 '14 at 20:32
Yes, double or CLLocationDegrees. And it depends on a context whether using CGFloat instead will or will not cause some very hard-to-debug problems as I did face ;). Thanks for your answer. – Stanislav Pankevich Jan 21 '14 at 09:09
I've tested your code. Indeed, it gives acceptable results compared to that of distanceFromLocation: and MKMetersBetweenMapPoints. Two notes to polish your answer: 1) would you mind changing your code to use CLLocationDegrees instead of float 2) Since you use squared earth radius - why not use it as const instead? – Stanislav Pankevich Jan 21 '14 at 11:36
Can you elaborate on the hard-to-debug problems you had in using float instead of double ? I haven't had any issue with that code so far and I believe single-precision floating point computations should be a bit faster than double-precision, also the added precision should not matter since the algorithm is already a fairly rough approximation. As for the constant I'm pretty sure the compiler is going to recognize and optimize it, so I'd rather leave it like that so it refers to a tangible value (earth radius in meters). – Taum Jan 21 '14 at 19:42
My concrete problem raised from accidentally initializing CLLocation from -[NSNumber floatValue] in one place in my code and initializing a CLLocation for the same object using -[NSNumber doubleValue] in some other place, then I used -[CLLocation isEqualToLocation:] and had wrong results so I learned using double-based numbers _always_ when I am on CoreLocation territory as a rule of thumb. But you are probably right that using float may give you some performance benefit - what about casting only the final result to a CLLocationDistance? – Stanislav Pankevich Jan 21 '14 at 20:06
A better rule of thumb IMO would be to never compare floating point values for perfect equality anyway, instead use `fabs(a - b) < EPSILON`. Anyway this is getting out of scope and I feel like it's easy enough for anyone using that code to change float to double or whatever their typedef of choice is :) – Taum Jan 21 '14 at 22:16
Yes, I agree with you. "typedef of choice" sounds nicely. Howerer, I like that these comments will hang here as additional notes to your solution - it works for me and by the way - it is faster than both of distanceFromLocation: and MKMetersBeetweenMapPoints (good!) but gives less approximate results than both of them (not bad in my case!). Thanks again. – Stanislav Pankevich Jan 22 '14 at 05:52

What code is written behind -[CLLocation distanceFromLocation:] or MKMetersBetweenMapPoints?

1 Answers1