Я бы использовал метод, предложенный Джастином, с одной настройкой.Он предлагает использовать отображаемую таблицу с дробными индексами, хотя я бы предложил целочисленные индексы.Это может звучать немного математически, но не стыдно читать следующее дважды (мне бы тоже пришлось).Предположим, что точка по индексу i в списке пар A искала самые близкие точки в другом списке B, и эта самая близкая точка находится по индексу j.Чтобы найти ближайшую точку в B к A [i + 1], вы должны рассматривать только точки в B с индексом, равным или большим, чем j.Вероятно, это будет j + 1, но может быть j или j + 2, j + 3 и т. Д., Но никогда не ниже j.Даже если точка, ближайшая к A [i + 1], имеет индекс меньше j, вам все равно не следует использовать эту точку для интерполяции, поскольку это приведет к неожиданному среднему значению и графику.Я возьму момент, чтобы создать пример кода для вас.Я надеюсь, вы видите, что эта оптимизация имеет смысл.
РЕДАКТИРОВАТЬ: При реализации этого я понял, что j не только ограничен снизу (описанным выше методом), но и ограничен сверху.Когда вы пробуете расстояние от A [i + 1] до B [j], B [j + 1], B [j + 2] и т. Д., Вы можете прекратить сравнение, когда расстояние A [i + 1] до B [j +...] перестает уменьшаться.Нет смысла искать дальше в B. Те же рассуждения применимы, как и в случае, когда j ограничен снизу: даже если какая-то точка в другом месте в B будет ближе, это, вероятно, не та точка, с которой вы хотите интерполировать.Это может привести к неожиданному графику, возможно, менее гладкому, чем вы ожидаете.И дополнительным бонусом этой второй границы является улучшенная производительность.Я создал следующий код:
IEnumerable<Tuple<double, double>> Average(List<Tuple<double, double>> A, List<Tuple<double, double>> B)
{
if (A == null || B == null || A.Any(p => p == null) || B.Any(p => p == null)) throw new ArgumentException();
Func<double, double> square = d => d * d;//squares its argument
Func<int, int, double> euclidianDistance = (a, b) => Math.Sqrt(square(A[a].Item1 - B[b].Item1) + square(A[a].Item2 - B[b].Item2));//computes the distance from A[first argument] to B[second argument]
int previousIndexInB = 0;
for (int i = 0; i < A.Count; i++)
{
double distance = euclidianDistance(i, previousIndexInB);//distance between A[i] and B[j - 1], initially
for (int j = previousIndexInB + 1; j < B.Count; j++)
{
var distance2 = euclidianDistance(i, j);//distance between A[i] and B[j]
if (distance2 < distance)//if it's closer than the previously checked point, keep searching. Otherwise stop the search and return an interpolated point.
{
distance = distance2;
previousIndexInB = j;
}
else
{
break;//don't place the yield return statement here, because that could go wrong at the end of B.
}
}
yield return LinearInterpolation(A[i], B[previousIndexInB]);
}
}
Tuple<double, double> LinearInterpolation(Tuple<double, double> a, Tuple<double, double> b)
{
return new Tuple<double, double>((a.Item1 + b.Item1) / 2, (a.Item2 + b.Item2) / 2);
}
Для вашей информации, функция «Среднее» возвращает то же количество интерполированных точек, которые содержит список А, что, вероятно, хорошо, но вы должны подумать об этом для своего конкретногоприложение.Я добавил несколько комментариев, чтобы прояснить некоторые детали, и я описал все аспекты этого кода в тексте выше.Я надеюсь, что это понятно, и в остальном не стесняйтесь задавать вопросы.
ВТОРОЕ РЕДАКТИРОВАНИЕ: Я неправильно прочитал и подумал, что у вас есть только два списка пунктов.Я создал обобщенную функцию вышеупомянутого принятия нескольких списков.Он по-прежнему использует только те принципы, которые описаны выше.
IEnumerable<Tuple<double, double>> Average(List<List<Tuple<double, double>>> data)
{
if (data == null || data.Count < 2 || data.Any(list => list == null || list.Any(p => p == null))) throw new ArgumentException();
Func<double, double> square = d => d * d;
Func<Tuple<double, double>, Tuple<double, double>, double> euclidianDistance = (a, b) => Math.Sqrt(square(a.Item1 - b.Item1) + square(a.Item2 - b.Item2));
var firstList = data[0];
for (int i = 0; i < firstList.Count; i++)
{
int[] previousIndices = new int[data.Count];//the indices of points which are closest to the previous point firstList[i - 1].
//(or zero if i == 0). This is kept track of per list, except the first list.
var closests = new Tuple<double, double>[data.Count];//an array of points used for caching, of which the average will be yielded.
closests[0] = firstList[i];
for (int listIndex = 1; listIndex < data.Count; listIndex++)
{
var list = data[listIndex];
double distance = euclidianDistance(firstList[i], list[previousIndices[listIndex]]);
for (int j = previousIndices[listIndex] + 1; j < list.Count; j++)
{
var distance2 = euclidianDistance(firstList[i], list[j]);
if (distance2 < distance)//if it's closer than the previously checked point, keep searching. Otherwise stop the search and return an interpolated point.
{
distance = distance2;
previousIndices[listIndex] = j;
}
else
{
break;
}
}
closests[listIndex] = list[previousIndices[listIndex]];
}
yield return new Tuple<double, double>(closests.Select(p => p.Item1).Average(), closests.Select(p => p.Item2).Average());
}
}
На самом деле то, что я сделал конкретный случай для двух списков по отдельности, могло бы быть хорошей вещью: это легко объяснить и предлагает шаг до понимания обобщенной версии.Кроме того, квадратный корень может быть удален, так как он не меняет порядок расстояний при сортировке, только длины.
ТРЕТЬЕ РЕДАКТИРОВАНИЕ: В комментариях стало ясно, что может быть ошибка.Я думаю, что нет ничего, кроме упомянутой маленькой ошибки, которая не должна иметь никакого значения, кроме как в конце графиков.В качестве доказательства того, что это действительно работает, это результат этого (пунктирная линия - среднее значение): 