Optimization of a distance calculation function

StackOverflow https://stackoverflow.com/questions/615206

  •  03-07-2019
  •  | 
  •  

Question

In my code I have to do a lot of distance calculation between pairs of lat/long values.

the code looks like this:

double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));

(lat2rad e.g. is latitude converted to radians).

I have identified this function as the performance bottleneck of my application. Is there any way to improve this?

(I cannot use look-up tables since the coordinates are varying). I have also looked at this question where a lookup scheme like a grid is suggested, which might be a possibility.

Thanks for your time! ;-)

Was it helpful?

Solution

If your goal is to rank (compare) distances, then approximations (sin and cos table lookups) could drastically reduce your amount of computations required (implement quick reject.)

Your goal is to only proceed with the actual trigonometric computation if the difference between the approximated distances (to be ranked or compared) falls below a certain threshold.

E.g. using lookup tables with 1000 samples (i.e. sin and cos sampled every 2*pi/1000), the lookup uncertainty is at most 0.006284. Using uncertainty calculation for the parameter to ACos, the cumulated uncertainty, also be the threshold uncertainty, will be at most 0.018731.

So, if evaluating Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) using sin and cos lookup tables for two coordinate-set pairs (distances) yields a certain ranking (one distance appears greater than the other based on the approximation), and the difference's modulus is greater than the threshold above, then the approximation is valid. Otherwise proceed with the actual trigonometric calculation.

OTHER TIPS

Would the CORDIC algorithm work for you (in regards to speed/accuracy)?

Using inspiration from @Brann I think you can reduce the calculation a bit (Warning its a long time since I did any of this and it will need to be verified). Some sort of lookup of precalculated values probably the fastest though

You have :

1: ACOS( SIN A SIN B + COS A COS B COS(A-B) )

but 2: COS(A-B) = SIN A SIN B + COS A COS B

which is rewritten as 3: SIN A SIN B = COS(A-B) - COS A COS B

replace SIN A SIN B in 1. you have :

4: ACOS( COS(A-B) - COS A COS B + COS A COS B COS(A-B) )

You pre-calculate X = COS(A-B) and Y = COS A COS B and you put the values into 4

to give:

ACOS( X - Y + XY )

4 trig calculations instead of 6 !

Change the way you store long/lat:

struct LongLat
{
  float
    long,
    lat,
    x,y,z;
}

When creating a long/lat, also compute the (x,y,z) 3D point that represents the equivalent position on a unit sphere centred at the origin.

Now, to determine if point B is nearer to point A than point C, do the following:

// is B nearer to A than C?
bool IsNearer (LongLat A, LongLat B, LongLat C)
{
  return (A.x * B.x + A.y * B.y + A.z * B.z) < (A.x * C.x + A.y * C.y + A.z * C.z);
}

and to get the distance between two points:

float Distance (LongLat A, LongLat B)
{
  // radius is the size of sphere your mapping long/lats onto
  return radius * acos (A.x * B.x + A.y * B.y + A.z * B.z);
}

You could remove the 'radius' term, effectively normalising the distances.

Switching to lookup tables for sin/cos/acos. Will be faster, there are alot of c/c++ fixed point libraries that also include those.

Here is code from someone else on Memoization. Which might work if the actual values used are more clustered.

Here is an SO question on Fixed Point.

What is the bottle neck? Is the the sine/cosine function calls or the arcsine call?

If your sine/cosine calls are slow, you could use the following theorem to prevent so many calls:

1 = sin(x)^2 + cos(x)^2
cos(x) = sqrt(1 - sin(x)^2)

But I like the mapping idea so that you don't have to recompute values you've already computed. Although be careful as the map could get very large very quickly.

How exact do you need the values to be?

If you round your values a bit then you could store the result of all lookups and check if thay have been used befor each calculation?

Well, since lat and lon are garenteed to be within a certain range, you could try using some form of a lookup table for you Math.* method calls. Say, a Dictionary<double,double>

I would argue that you may want to re-examine how you found that function to be the bottleneck. (IE did you profile the application?)

The equation to me seems very light weight and shouldn't cause any trouble. Granted, I don't know your application and you say you do a lot of these calculations.

Nevertheless it is something to consider.

As someone else pointed out, are you sure this is your bottleneck?

I've done some performance testing of a similar application I'm building where I call a simple method to return a distance between two points using standard trig. 20,000 calls to it shoves it right at the top of the profiling output, yet there's no way I can make it faster... It's just the shear # of calls.

In this case, I need to reduce the # calls to it... Not that this is the bottleneck.

I use a different algorithm for calculating distance between 2 lati/longi positions, it could be lighter than yours since it only does 1 Cos call and 1 Sqrt call.

public static double GetDistanceBetweenTwoPos(double lat1, double long1, double lat2, double long2)
{
  double distance = 0;
  double x = 0;
  double y = 0;

  x = 69.1 * (lat1 - lat2);
  y = 69.1 * (long1 - long2) * System.Math.Cos(lat2 / 57.3);

  //calculation base : Miles
  distance = System.Math.Sqrt(x * x + y * y);

  //Distance calculated in Kilometres
  return distance * 1.609;
}

someone has already mentioned memoisation and this is a bit similar. if you comparing the same point to many other points then it is better to precalculate parts of that equation.

instead of 

double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));

have:

double result = Math.Acos(lat2rad.sin * lat1rad.sin 
+ lat2rad.cos * lat1rad.cos * (lon2rad.cos * lon1rad.cos + lon1rad.sin * lon2rad.sin));

and i think that's the same formula as someone else has posted because part of the equation will disappear when you expand the brackets:)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top