Алгоритм 2D-интерполяции

Question

У меня есть две формы, которые являются поперечными сечениями канала. Я хочу рассчитать сечение промежуточной точки между двумя определенными точками. Какой самый простой (относительно простой?) Алгоритм использовать в этой ситуации?

П.С .: Я столкнулся с несколькими алгоритмами, такими как естественный сосед и пуассон, которые казались сложными. Я ищу простое решение, которое можно было бы быстро реализовать.

РЕДАКТИРОВАТЬ: я удалил слово "Simplest" из названия, поскольку это может вводить в заблуждение

Answer 1

Это просто:

1. На каждом поперечном сечении нарисуйте N точек с равномерно распределенными интервалами вдоль границы поперечного сечения.
2. Нарисуйте прямые линии от n-й точки в поперечном сечении 1 до n-й точки в поперечном сечении 2.
3. Снимите новое поперечное сечение на желаемом расстоянии между старыми поперечными сечениями.

Все еще проще:

1. Использовать одно из существующих поперечных сечений без изменений.

Полагаю, это второе предложение может быть слишком простым, но держу пари, что никто не предлагает более простого!

РЕДАКТИРОВАТЬ после комментария OP: (слишком много для повторного комментария)

Ну, вы просили простой метод! Я не уверен, что вижу ту же проблему с первым методом, что и вы. Если поперечные сечения не слишком странные (вероятно, лучше всего, если они являются выпуклыми многоугольниками), и вы не делаете ничего странного, например, отображаете левую сторону одного поперечного сечения на правую сторону другого (таким образом вынуждаете множество пересекающихся линий). ) тогда метод должен дать какое-то заметное сечение. В случае, если вы предлагаете треугольник и прямоугольник, предположим, что треугольник сидит на своем основании, одна вершина вверху. Сопоставьте эту точку, скажем, с верхним левым углом прямоугольника, затем продолжайте движение в том же направлении (по часовой стрелке или против часовой стрелки) вокруг границ обоих поперечных сечений, соединяя соответствующие точки. Я не вижу линий пересечения и вижу четкую форму на любом расстоянии между двумя поперечными сечениями.

Answer 2

Вот еще одна попытка решить проблему, которая, на мой взгляд, гораздо лучше.

Учитывая два сечения C_1, C_2

Поместите каждый C_i в глобальную систему отсчета с системой координат (x,y), чтобы их расположение имело смысл. Разделите каждый C_i на верхнюю и нижнюю кривые U_i и L_i. Идея состоит в том, что вы захотите непрерывно деформировать кривую от U_1 до U_2 и L_1 до L_2. (Обратите внимание, что вы можете расширить этот метод, чтобы разделить каждый C_i на m кривые, если хотите.)

Способ сделать это заключается в следующем. Для каждой T_i = U_i, or 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.

Обратите внимание, что все, что на самом деле делает, - это линейная интерполяция коэффициентов интерполяционных полиномов двух частей обоих сечений. Также обратите внимание, что при разделении поперечных сечений вы, вероятно, должны поставить ограничение на то, что они должны быть разделены в конечных точках, которые совпадают, иначе у вас могут быть «дыры» в вашей деформации.

Надеюсь, это понятно.

edit: решена проблема колебаний при интерполяции полиномов.

Answer 3

Обратите внимание, что в ответах High Performance Mark есть некоторые неясности, на которые вам, вероятно, придется обратиться, и они будут определять качество результатов его метода. Наиболее важным из них является то, что когда вы рисуете n точек на обоих поперечных сечениях, какое соответствие вы определяете между ними, то есть, если вы делаете это так, как предлагает High Performance Mark, то порядок маркировки точек становится важным.

Я предлагаю вращать (ортогональную) плоскость одновременно через оба поперечных сечения, тогда множество точек, которые пересекают эту плоскость в одном поперечном сечении, просто необходимо сопоставить с множеством точек, которые пересекают эту плоскость в другом поперечном сечении. Гипотетически, нет ограничений на количество точек в этих множествах, но это, безусловно, уменьшает сложность проблемы соответствия в исходной ситуации.