medians for degree measurements

Steve Howell showell30 at yahoo.com
Sat Jan 23 07:09:54 CET 2010


On Jan 22, 5:12 pm, MRAB <pyt... at mrabarnett.plus.com> wrote:
> Steve Howell wrote:
> > I just saw the thread for medians, and it reminded me of a problem
> > that I need to solve.  We are writing some Python software for
> > sailing, and we need to detect when we've departed from the median
> > heading on the leg.  Calculating arithmetic medians is
> > straightforward, but compass bearings add a twist.
>
> > The numerical median of 1, 2, 3, 4, 5, 6, 359 is 4.  But for
> > navigational purposes you would actually order the numbers 359, 1, 2,
> > 3, 4, 5, 6, so the desired median heading of the boat is actually 3.
>
> > Of course, you could express 359 better as -1 degrees to north, then
> > the sequence would be -1, 1, 2, 3, 4, 5, and 6.  And you'd be good.
>
> > But that trick does not generalize if you go south instead, as you
> > have similar issues with -179, 174, 175, 176, 177, 178, and 179.
>
> > Has anybody solved this in Python, either for compass bearings or a
> > different domain?  I can think of kind of a brute force solution where
> > you keep rotating the sequence until the endpoints are closest
> > together mod 360, but I wonder if there is something more elegant.
>
> When you read the headings clockwise the values normally increase and
> you pick the middle one. However, when you cross north the values
> decrease. You can spot whether the set of headings crosses north by
> checking whether the difference between the minimum and maximum is
> greater than 180. If it is then make the westerly headings negative,
> sort the values, and pick the middle one, adding 180 if it's negative.
>
> def compass_median(points):
>      points = sorted(points)
>      if points[-1] - points[0] > 180:
>          points = [(p - 360 if p > 180 else p) for p in points]
>          points.sort()
>      median = points[len(points) // 2]
>      return median + 360 if median < 0 else median

I like this implementation, and it would probably work 99.9999% of the
time for my particular use case.  The only (very contrived) edge case
that I can think of is when you have 10 bearings to SSW, 10 bearings
to SSE, and the two outliers are unfortunately in the NE and NW
quadrants.  It seems like the algorithm above would pick one of the
outliers.

Maybe the refinement to the algorithm above would be to find the mean
first, by summing sines and cosines of the bearings, taking the
quotient, and applying the arctangent.  Then use the resulting angle
as the equivalent of "due north" and adjust angles to be within (-180,
180) respect to the mean, pretty much as you do in the code above,
with minor modifications.

I realize the problem as I stated it as sort of ill-defined.

The way you stated the solution made me realize more deeply that you
basically have a list that needs to be rotated either clockwise or
counterclockwise in certain situations.  Instead of using the 180-
degree check to coarsely (but usually effectively) rotate your frame
of reference, you could instead use the mean to eliminate even more
edge cases.





More information about the Python-list mailing list