views:

3329

answers:

11

I want to calculate the average of a set of angles. For example, I might have several samples from the reading of a compass. The problem of course is how to deal with the wraparound. The same algorithm might be useful for a clockface.

The actual question is more complicated - what do statistics mean on a sphere or in an algebraic space which "wraps round", eg the additive group mod n. The answer may not be unique, eg the average of 359 degrees and 1 degree could be 0 degrees or 180, but statistically 0 looks better.

This is a real programming problem for me and I'm trying to make it not look like just a Math problem.

[Edit: to resolve all the confusion, when I refer to angles you can assume I mean bearings]

+20  A: 

Compute unit vectors from the angles and take the angle of their average.

starblue
That does not work if the vectors cancel each other out. Average could still be meaningful in this case, depending on its exact definition.
David Hanak
@David, the average direction of two bearings 180 degrees out is undefined. This doesn't make starblue's answer wrong, it's just an exceptional case, as occurs in many geomteric problems.
Shane MacLaughlin
I don't think there is a meaningful definition which takes into account circularity when the vectors cancel out.
starblue
@smacl: I agree, if angles represent directions. But if you think of complex numbers, for example, and define average as "what is the argument of c, such that c*c == a*b", where a and b have a modulus of 1, then the average of 0 and 180 is 90.
David Hanak
By the way this is also a great answer because it gives an obvious extension to weighted average if you trust some samples more than others.
Nick Fortescue
The average of 0,0,90 won't come 30!
Lior Kogan
@starblue: atan( (sin(0)+sin(0)+sin(90)) / (cos(0)+cos(0)+cos(90)) ) = atan(1/2)= 26.56 deg
Lior Kogan
+4  A: 

You have to define average more accurately. For the specific case of two angles, I can think of two different scenarios:

  1. The "true" average, i.e. (a + b) / 2 % 360.
  2. The angle that points "between" the two others while staying in the same semicircle, e.g. for 355 and 5, this would be 0, not 180. To do this, you need to check if the difference between the two angles is larger than 180 or not. If so, increment the smaller angle by 360 before using the above formula.

I don't see how the second alternative can be generalized for the case of more than two angles, though.

David Hanak
While the question refers to angles, it is better thought of as mean direction, and is a common navigation issue.
Shane MacLaughlin
Good points, David. For instance, what is the average of a 180º angle and a 540º angle? Is it 360º or 180º?
Baltimark
@Baltimark, I guess it depends on what you are doing. If its navigation, probably the latter. If it's a fancy snowboarding jump, maybe the former ;)
Shane MacLaughlin
So the "true" average of 1 and 359 is (360 / 2) % 360 = 180?? I think not.
Die in Sente
@Die in Sente: numerically speaking, definitely. For example, if angles represent turns, not directions, then the average of 359 and 1 is surely 180. It's all a matter of interpretation.
David Hanak
+5  A: 

I see the problem - for example, if you have a 45' angle and a 315' angle, the "natural" average would be 180', but the value you want is actually 0'.

I think Starblue is onto something. Just calculate the (x, y) cartesian coordinates for each angle, and add those resulting vectors together. The angular offset of the final vector should be your required result.

x = y = 0
foreach angle {
    x += cos(angle)
    y += sin(angle)
}
average_angle = atan2(y, x)

I'm ignoring for now that a compass heading starts at north, and goes clockwise, whereas "normal" cartesian coordinates start with zero along the X axis, and then go anti-clockwise. The maths should work out the same way regardless.

Alnitak
Your maths library probably uses Radians for angles. Remember to convert.
Martin Beckett
+1  A: 

Here's an idea: build the average iteratively by always calculating the average of the angles that are closest together, keeping a weight.

Another idea: find the largest gap between the given angles. Find the point that bisects it, and then pick the opposite point on the circle as the reference zero to calculate the average from.

John the Statistician
I don't recommend my answer, but instead starblue's highly ranked answer. The key observation there is to think of the center of the compass as the 0,0 point.
John the Statistician
+1  A: 

Let's represent these angles with points on the circumference of the circle.

Can we assume that all these points fall on the same half of the circle? (Otherwise, there is no obvious way to define the "average angle". Think of two points on the diameter, e.g. 0 deg and 180 deg --- is the average 90 deg or 270 deg? What happens when we have 3 or more evenly spread out points?)

With this assumption, we pick an arbitrary point on that semicircle as the "origin", and measure the given set of angles with respect to this origin (call this the "relative angle"). Note that the relative angle has an absolute value strictly less than 180 deg. Finally, take the mean of these relative angles to get the desired average angle (relative to our origin of course).

Zach Scrivena
+7  A: 
Nick Fortescue
which is also much the same as the algorithm I posted at the same time as you. You would need to use atan2 rather than a plain atan, though, since otherwise you can't tell which quadrant the answer is in.
Alnitak
You can still end up with some indeterminate answers. Like in the 0, 180 sample. So you still have to check for edge cases. Also, there is usually an atan2 function available which might be faster in your case.
Loki
A: 

Alnitak has the right solution. Nick Fortescue's solution is functionally the same.

For the special case of where

( sum(x_component) = 0.0 && sum(y_component) = 0.0 ) // e.g. 2 angles of 10. and 190. degrees ea.

use 0.0 degrees as the sum

Computationally you have to test for this case since atan2(0. , 0.) is undefined and will generate an error.

jeffD
on glibc 'atan2' is defined for (0, 0) - the result is 0
Alnitak
A: 

The average angle phi_avg should have the property that sum_i|phi_avg-phi_i|^2 becomes minimal, where the difference has to be in [-Pi, Pi) (because it might be shorter to go the other way around!). This is easily achieved by normalizing all input values to [0, 2Pi), keeping a running average phi_run and choosing normalizing |phi_i-phi_run| to [-Pi,Pi) (by adding or subtractin 2Pi). Most suggestions above do something else that does not have that minimal property, i.e., they average something, but not angles.

+2  A: 

FOR THE SPECIAL CASE OF TWO ANGLES:

The answer ( (a + b) mod 360 ) / 2 is WRONG. For angles 350 and 2, the closest point is 356, not 176.

The unit vector and trig solutions may be too expensive.

What I've got from a little tinkering is:

diff = ( ( a - b + 180 + 360 ) mod 360 ) - 180
angle = (360 + b + ( diff / 2 ) ) mod 360
  • 0, 180 -> 90 (two answers for this: this equation takes the clockwise answer from a)
  • 180, 0 -> 270 (see above)
  • 180, 1 -> 90.5
  • 1, 180 -> 90.5
  • 20, 350 -> 5
  • 350, 20 -> 5 (all following examples reverse properly too)
  • 10, 20 -> 15
  • 350, 2 -> 356
  • 359, 0 -> 359.5
  • 180, 180 -> 180
darron
This could further be optimized by the use of BAMS: http://stackoverflow.com/questions/1048945/getting-the-computer-to-realise-360-degrees-0-degrees-rotating-a-gun-turret/1049285#1049285
darron
Not bad. The first line computes the relative angle of a with respect to b in the range [-180, 179], the second computes the middle angle from that. I'd use b + diff/2 instead of a - diff/2 for clarity.
starblue
Try it with 20 and 210 and you should get 295 NOT 115 !!!
Stecy
Am I missing something? I *DO* get 295.
darron
Ah.. I get it. Matlab's mod operator wraps -10 to 350. I'll change the code. It's a simple additional 360.
darron
+1  A: 

I would go the vector way using complex numbers. My example is in Python, which has built-in complex numbers:

import cmath # complex math

def average_angle(list_of_angles):

    # make a new list of vectors
    vectors= [cmath.rect(1, angle) # length 1 for each vector
        for angle in list_of_angles]

    vector_sum= sum(vectors)

    # no need to average, we don't care for the modulus
    return cmath.phase(vector_sum)

Note that Python does not need to build a temporary new list of vectors, all of the above can be done in one step; I just chose this way to approximate pseudo-code applicable to other languages too.

ΤΖΩΤΖΙΟΥ
+3  A: 

ackb is right that these vector based solutions cannot be considered true averages of angles, they are only an average of the unit vector counterparts. However, ackb's suggested solution does not appear to mathematically sound.

The following is a solution that is mathematically derived from the goal of minimising (angle[i] - avgAngle)^2 (where the difference is corrected if necessary), which makes it a true arithmetic mean of the angles.

First, we need to look at exactly which cases the difference between angles is different to the difference between their normal number counterparts. Consider angles x and y, if y >= x - 180 and y <= x + 180, then we can use the difference (x-y) directly. Otherwise, if the first condition is not met then we must use (y+360) in the calculation instead of y. Corresponding, if the second condition is not met then we must use (y-360) instead of y. Since the equation of the curve we are minimising only changes at the points where these inequalities change from true to false or vice versa, we can separate the full [0,360) range into a set of segments, separated by these points. Then, we only need to find the minimum of each of these segments, and then the minimum of each segment's minimum, which is the average.

Here's an image demonstrating where the problems occur in calculating angle differences. If x lies in the gray area then there will be a problem.

i3.photobucket.com/albums/y69/02williamsa6/angle_comparisons.png

(couldn't make it a link because I don't have enough reputation)

To minimise a variable, depending on the curve, we can take the derivative of what we want to minimise and then we find the turning point (which is where the derivative = 0).

Here we will apply the idea of minimise the squared difference to derive the common arithmetic mean formula: sum(a[i])/n. The curve y = sum((a[i]-x)^2) can be minimised in this way:

y = sum((a[i]-x)^2)
= sum(a[i]^2 - 2*a[i]*x + x^2)
= sum(a[i]^2) - 2*x*sum(a[i]) + n*x^2

dy\dx = -2*sum(a[i]) + 2*n*x

for dy/dx = 0:
-2*sum(a[i]) + 2*n*x = 0
-> n*x = sum(a[i])
-> x = sum(a[i])/n

Now applying it to curves with our adjusted differences:

b = subset of a where the correct (angular) difference a[i]-x c = subset of a where the correct (angular) difference (a[i]-360)-x cn = size of c d = subset of a where the correct (angular) difference (a[i]+360)-x dn = size of d

y = sum((b[i]-x)^2) + sum(((c[i]-360)-b)^2) + sum(((d[i]+360)-c)^2)
= sum(b[i]^2 - 2*b[i]*x + x^2)
  + sum((c[i]-360)^2 - 2*(c[i]-360)*x + x^2)
  + sum((d[i]+360)^2 - 2*(d[i]+360)*x + x^2)
= sum(b[i]^2) - 2*x*sum(b[i])
  + sum((c[i]-360)^2) - 2*x*(sum(c[i]) - 360*cn)
  + sum((d[i]+360)^2) - 2*x*(sum(d[i]) + 360*dn)
  + n*x^2
= sum(b[i]^2) + sum((c[i]-360)^2) + sum((d[i]+360)^2)
  - 2*x*(sum(b[i]) + sum(c[i]) + sum(d[i]))
  - 2*x*(360*dn - 360*cn)
  + n*x^2
= sum(b[i]^2) + sum((c[i]-360)^2) + sum((d[i]+360)^2)
  - 2*x*sum(x[i])
  - 2*x*360*(dn - cn)
  + n*x^2

dy/dx = 2*n*x - 2*sum(x[i]) - 2*360*(dn - cn)

for dy/dx = 0:
2*n*x - 2*sum(x[i]) - 2*360*(dn - cn) = 0
n*x = sum(x[i]) + 360*(dn - cn)
x = (sum(x[i]) + 360*(dn - cn))/n

This alone is not quite enough to get the minimum, while it works for normal values, that has an unbounded set, so the result will definitely lie within set's range and is therefore valid. We need the minimum within a range (defined by the segment). If the minimum is less than our segment's lower bound then the minimum of that segment must be at the lower bound (because quadratic curves only have 1 turning point) and if the minimum is greater than our segment's upper bound then the segment's minimum is at the upper bound. After we have the minimum for each segment, we simply find the one that has the lowest value for what we're minimising (sum((b[i]-x)^2) + sum(((c[i]-360)-b)^2) + sum(((d[i]+360)-c)^2)).

Here is an image to the curve, which shows how it changes at the points where x=(a[i]+180)%360. The data set is in question is {65,92,230,320,250}.

http://i3.photobucket.com/albums/y69/02williamsa6/curve.png

Here is an implementation of the algorithm in Java, including some optimisations, its complexity is O(nlogn). It can be reduced to O(n) if you replace the comparison based sort with a non comparison based sort, such as radix sort.

static double varnc(double _mean, int _n, double _sumX, double _sumSqrX)
{
    return _mean*(_n*_mean - 2*_sumX) + _sumSqrX;
}
//with lower correction
static double varlc(double _mean, int _n, double _sumX, double _sumSqrX, int _nc, double _sumC)
{
    return _mean*(_n*_mean - 2*_sumX) + _sumSqrX
            + 2*360*_sumC + _nc*(-2*360*_mean + 360*360);
}
//with upper correction
static double varuc(double _mean, int _n, double _sumX, double _sumSqrX, int _nc, double _sumC)
{
    return _mean*(_n*_mean - 2*_sumX) + _sumSqrX
            - 2*360*_sumC + _nc*(2*360*_mean + 360*360);
}

static double[] averageAngles(double[] _angles)
{
    double sumAngles;
    double sumSqrAngles;

    double[] lowerAngles;
    double[] upperAngles;

    {
        List<Double> lowerAngles_ = new LinkedList<Double>();
        List<Double> upperAngles_ = new LinkedList<Double>();

        sumAngles = 0;
        sumSqrAngles = 0;
        for(double angle : _angles)
        {
            sumAngles += angle;
            sumSqrAngles += angle*angle;
            if(angle < 180)
                lowerAngles_.add(angle);
            else if(angle > 180)
                upperAngles_.add(angle);
        }


        Collections.sort(lowerAngles_);
        Collections.sort(upperAngles_,Collections.reverseOrder());


        lowerAngles = new double[lowerAngles_.size()];
        Iterator<Double> lowerAnglesIter = lowerAngles_.iterator();
        for(int i = 0; i < lowerAngles_.size(); i++)
            lowerAngles[i] = lowerAnglesIter.next();

        upperAngles = new double[upperAngles_.size()];
        Iterator<Double> upperAnglesIter = upperAngles_.iterator();
        for(int i = 0; i < upperAngles_.size(); i++)
            upperAngles[i] = upperAnglesIter.next();
    }

    List<Double> averageAngles = new LinkedList<Double>();
    averageAngles.add(180d);
    double variance = varnc(180,_angles.length,sumAngles,sumSqrAngles);

    double lowerBound = 180;
    double sumLC = 0;
    for(int i = 0; i < lowerAngles.length; i++)
    {
        //get average for a segment based on minimum
        double testAverageAngle = (sumAngles + 360*i)/_angles.length;
        //minimum is outside segment range (therefore not directly relevant)
        //since it is greater than lowerAngles[i], the minimum for the segment
        //must lie on the boundary lowerAngles[i]
        if(testAverageAngle > lowerAngles[i]+180)
            testAverageAngle = lowerAngles[i];

        if(testAverageAngle > lowerBound)
        {
            double testVariance = varlc(testAverageAngle,_angles.length,sumAngles,sumSqrAngles,i,sumLC);

            if(testVariance < variance)
            {
                averageAngles.clear();
                averageAngles.add(testAverageAngle);
                variance = testVariance;
            }
            else if(testVariance == variance)
                averageAngles.add(testAverageAngle);
        }

        lowerBound = lowerAngles[i];
        sumLC += lowerAngles[i];
    }
    //Test last segment
    {
        //get average for a segment based on minimum
        double testAverageAngle = (sumAngles + 360*lowerAngles.length)/_angles.length;
        //minimum is inside segment range
        //we will test average 0 (360) later
        if(testAverageAngle < 360 && testAverageAngle > lowerBound)
        {
            double testVariance = varlc(testAverageAngle,_angles.length,sumAngles,sumSqrAngles,lowerAngles.length,sumLC);

            if(testVariance < variance)
            {
                averageAngles.clear();
                averageAngles.add(testAverageAngle);
                variance = testVariance;
            }
            else if(testVariance == variance)
                averageAngles.add(testAverageAngle);
        }
    }


    double upperBound = 180;
    double sumUC = 0;
    for(int i = 0; i < upperAngles.length; i++)
    {
        //get average for a segment based on minimum
        double testAverageAngle = (sumAngles - 360*i)/_angles.length;
        //minimum is outside segment range (therefore not directly relevant)
        //since it is greater than lowerAngles[i], the minimum for the segment
        //must lie on the boundary lowerAngles[i]
        if(testAverageAngle < upperAngles[i]-180)
            testAverageAngle = upperAngles[i];

        if(testAverageAngle < upperBound)
        {
            double testVariance = varuc(testAverageAngle,_angles.length,sumAngles,sumSqrAngles,i,sumUC);

            if(testVariance < variance)
            {
                averageAngles.clear();
                averageAngles.add(testAverageAngle);
                variance = testVariance;
            }
            else if(testVariance == variance)
                averageAngles.add(testAverageAngle);
        }

        upperBound = upperAngles[i];
        sumUC += upperBound;
    }
    //Test last segment
    {
        //get average for a segment based on minimum
        double testAverageAngle = (sumAngles - 360*upperAngles.length)/_angles.length;
        //minimum is inside segment range
        //we test average 0 (360) now           
        if(testAverageAngle < 0)
            testAverageAngle = 0;

        if(testAverageAngle < upperBound)
        {
            double testVariance = varuc(testAverageAngle,_angles.length,sumAngles,sumSqrAngles,upperAngles.length,sumUC);

            if(testVariance < variance)
            {
                averageAngles.clear();
                averageAngles.add(testAverageAngle);
                variance = testVariance;
            }
            else if(testVariance == variance)
                averageAngles.add(testAverageAngle);
        }
    }


    double[] averageAngles_ = new double[averageAngles.size()];
    Iterator<Double> averageAnglesIter = averageAngles.iterator();
    for(int i = 0; i < averageAngles_.length; i++)
        averageAngles_[i] = averageAnglesIter.next();


    return averageAngles_;
}

The arithmetic mean of a set of angles may not agree with your intuitive idea of what the average should be. For example, the arithmetic mean of the set {179,179,0,181,181} is 216 (and 144). The answer you immediately think of is probably 180, however it is well known that the arithmetic mean is heavily affected by edge values. You should also remember that angles are not vectors, as appealing as that may seem when dealing with angles sometimes.

This algorithm does of course also apply to all quantities that obey modular arithmetic (with minimal adjustment), such as the time of day.

I would also like to stress that even though this is a true average of angles, unlike the vector solutions, that does not necessarily mean it is the solution you should be using, the average of the corresponding unit vectors may well be the value you actually should to be using.

Nimble
Excellent work! I also tried to minimize (angle[i] - avgAngle)^2 but I wasn't sure how to do it.
Lior Kogan
The important fact is that you you have 3 methods, for different situations: (1) the measurement-device is accurate, but you are measuring independant discrete events - here your suggested method should be used. (2) the measurement-device is accurate, but you are measuring a continuously-changing property - you should use Mitsuta method (3) the measured value is constant, but your measurement-device has an inaccuracy with a Von Mises distribution - you should use vector average.
Lior Kogan
I still don't know how to measure the average when both the measured property changes, and the measurement-device is inaccurate...
Lior Kogan
The Mitsuta method actually gives the starting angle + the average of the rotations from the starting angle. So to get a similar method, accounting for measurement error then you'd need to be looking at the rotations happening and estimate the error for those. I think you would need a distribution for the rotations in order to estimate an error for them.
Nimble