ackb верно, что эти векторные решения не могут считаться истинными средними значениями углов, они являются только средними значениями для единичных векторов. Тем не менее, предложенное решение Акба не кажется математически обоснованным.
Ниже приведено решение, которое математически получено с целью минимизации (angle [i] - avgAngle) ^ 2 (где разница корректируется при необходимости), что делает его истинным средним арифметическим углов.
Во-первых, нам нужно посмотреть, в каких именно случаях разница между углами отличается от разницы между их обычными числами. Рассмотрим углы x и y, если y> = x - 180 и y <= x + 180, то мы можем напрямую использовать разность (x-y). В противном случае, если первое условие не выполняется, мы должны использовать (y + 360) в расчете вместо y. Соответственно, если второе условие не выполнено, тогда мы должны использовать (y-360) вместо y. Поскольку в уравнении кривой мы минимизируем только изменения в точках, где эти неравенства изменяются с истинного на ложное или наоборот, мы можем разделить полный диапазон [0,360) на набор сегментов, разделенных этими точками. Затем нам нужно только найти минимум каждого из этих сегментов, а затем минимум каждого сегмента, который является средним. </p>
Вот изображение, показывающее, где возникают проблемы при расчете угловых разностей. Если х лежит в серой области, тогда возникнет проблема.
Чтобы минимизировать переменную, в зависимости от кривой, мы можем взять производную того, что мы хотим минимизировать, и затем мы найдем точку поворота (где производная = 0).
Здесь мы применим идею минимизации квадрата разности, чтобы вывести общую формулу среднего арифметического: sum (a [i]) / n. Кривая y = sum ((a [i] -x) ^ 2) может быть минимизирована следующим образом:
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
Теперь примените его к кривым с нашими скорректированными отличиями:
b = подмножество a, где правильная (угловая) разница a [i] -x
c = подмножество a, где правильная (угловая) разница (a [i] -360) -x
cn = размер c
d = подмножество a, где правильная (угловая) разница (a [i] +360) -x
dn = размер 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
Одного этого недостаточно для получения минимума, в то время как он работает для нормальных значений, у которых есть неограниченный набор, поэтому результат определенно будет лежать в пределах диапазона набора и, следовательно, действителен. Нам нужен минимум в пределах диапазона (определяемого сегментом). Если минимум меньше нижней границы нашего сегмента, то минимум этого сегмента должен быть на нижней границе (потому что у квадратичных кривых есть только одна точка поворота), а если минимум больше верхней границы нашего сегмента, то минимум сегмента находится на верхняя граница. После того, как у нас есть минимум для каждого сегмента, мы просто находим тот, который имеет наименьшее значение для того, что мы минимизируем (sum ((b [i] -x) ^ 2) + sum (((c [i] -360 ) -b) ^ 2) + sum (((d [i] +360) -c) ^ 2)).
Вот изображение кривой, которое показывает, как оно изменяется в точках, где x = (a [i] +180)% 360. Набор данных находится под вопросом {65,92,230,320,250}.
Вот реализация алгоритма на Java, включающая некоторые оптимизации, его сложность составляет O (nlogn). Его можно уменьшить до O (n), если заменить сортировку, основанную на сравнении, сортировкой, не основанной на сравнении, например радикальной сортировкой.
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_;
}
Среднее арифметическое для набора углов может не соответствовать вашему интуитивному представлению о том, каким должно быть среднее значение. Например, среднее арифметическое для набора {179,179,0,181,181} составляет 216 (и 144). Ответ, о котором вы сразу подумаете, вероятно, равен 180, однако хорошо известно, что среднее арифметическое сильно зависит от значений ребер. Вам также следует помнить, что углы не являются векторами, как это может показаться привлекательным при работе с углами.
Этот алгоритм, конечно, также применим ко всем величинам, которые подчиняются модульной арифметике (с минимальной корректировкой), например, ко времени суток.
Я также хотел бы подчеркнуть, что хотя это истинное среднее углов, в отличие от векторных решений, это не обязательно означает, что это решение, которое вы должны использовать, среднее значение соответствующих единичных векторов может значение, которое вы на самом деле должны использовать.