Алгоритм для 2D интерполяции
У меня есть две формы, которые являются сечениями канала. Я хочу вычислить сечение промежуточной точки между двумя определенными точками. Что является самым простым (относительно простой?) алгоритм для использования в этой ситуации?
P.S.: Я столкнулся с несколькими алгоритмами как естественный сосед и Пуассон, который казался сложным. Я ищу простое решение, которое могло быть реализовано быстро.
Править: Я удалил слово "Simplest" из заголовка, так как это могло бы вводить в заблуждение
3 ответа
Это просто:
- На каждом поперечном сечении постройте N точек через равномерные интервалы вдоль границы сечения.
- Проведите прямые линии от n-ой точки на сечении 1 до n-ой точки на сечении 2.
- Отложите новое сечение на желаемом расстоянии между старыми сечениями.
Еще проще:
- Используйте одно из существующих сечений без изменений.
Это второе предложение может быть слишком простым, я полагаю, но я готов поспорить, что никто не предложит более простого!
EDIT после комментария ОП: (слишком много для повторного комментария)
Ну, вы же просили простой метод! Я не уверен, что вижу ту же проблему с первым методом, что и вы. Если сечения не слишком странные (возможно, лучше всего, если это выпуклые многоугольники), и вы не делаете ничего странного, например, не привязываете левую сторону одного сечения к правой стороне другого (тем самым создавая множество пересекающихся линий), то метод должен дать какое-то разумное сечение. В предложенном вами случае треугольника и прямоугольника, предположим, что треугольник сидит на своем основании, одна вершина находится в вершине. Отметьте эту точку, скажем, в левом верхнем углу прямоугольника, затем проведите в том же направлении (по часовой стрелке или против часовой стрелки) вокруг границ обоих сечений, соединяя соответствующие точки. Я не вижу никаких пересекающихся линий, и я вижу четко определенную форму на любом расстоянии между двумя сечениями.
Обратите внимание, что в ответах High Performance Mark есть некоторые двусмысленности, которые вам, вероятно, нужно будет устранить, и которые будут определять качество вывода его метода. Самый важный из них: когда вы рисуете точки n на обоих поперечных сечениях, какое соответствие вы определяете между ними, то есть если вы делаете это так, как предлагал High Performance Mark, то порядок маркировки точек становится важным.
Я предлагаю вращать (ортогональную) плоскость одновременно через оба поперечных сечения, тогда набор точек, которые пересекают эту плоскость на одном поперечном сечении, просто нужно сопоставить с набором точек, которые пересекают эту плоскость на другом поперечном сечении. Гипотетически нет ограничения на количество точек в этих множествах, но это, безусловно, снижает сложность проблемы соответствия в исходной ситуации.
Вот еще одна попытка решения проблемы, которая, на мой взгляд, намного лучше. .
Учитывая два сечения C_1 , C_2
Поместите каждое C_i в глобальную систему отсчета с системой координат (x, y) , так что их относительное расположение имеет смысл. Разделите каждый C_i на верхнюю и нижнюю кривые U_i и L_i . Идея состоит в том, что вы захотите непрерывно деформировать кривую U_1 в U_2 и L_1 в L_2 . (Обратите внимание, что вы можете расширить этот метод, чтобы разбить каждую кривую C_i на кривые м , если хотите.)
Это можно сделать следующим образом. Для каждого T_i = U_i или L_i выборки n точек и определяют интерполирующий полином P {T_i} (x) . Как кто-то должным образом заметил ниже, интерполирующие полиномы подвержены колебаниям, особенно в конечных точках. Вместо интерполирующего полинома можно использовать полином аппроксимации методом наименьших квадратов, который был бы намного более надежным. Затем определите деформацию многочлена P {U_1} (x) = a_0 + a_1 * x + ... + a_n * x ^ n в P {U_2} (x) = b_0 + b_1 * x + ... + b_n * x ^ n как Q {P {U_1}, P {U_2}} (x, t) = (t * a_0 + (1 - t) b_0) + ... + (t * a_n + (1-t) * b_n) * x ^ n , где деформация Q определяется как 0 <= t <= 1 , где t определяет, в какой точке находится деформация (т.е. в t = 0 мы находимся в U_2 , а в t = 1 мы находимся в U_1 и каждый другой t мы находимся в некоторой непрерывной деформации обоих.)
То же самое следует для Q {P {L_1}, P {L_2}} (x, t) . Эти две деформации создают непрерывное представление между двумя поперечными сечениями, которое вы можете выбрать при любом t .
Обратите внимание, что все, что это действительно делает, - это линейная интерполяция коэффициентов интерполяционных полиномов двух частей обоих поперечных сечений. Также обратите внимание на то, что при разделении поперечных сечений вы, вероятно, должны установить ограничение, что они должны быть разделены в конечных точках, которые совпадают, иначе у вас могут быть «дыры» в вашей деформации.
Надеюсь, это ясно.
править: рассмотрена проблема колебаний в интерполяционных полиномах.