Как отобразить точку на искривленной сетке

Question

Скажем, у вас есть набор точек с координатами в декартовой системе координат.

Вы хотите построить другую точку и узнать ее координаты в той же декартовой системе координат.

Однако сюжет, на котором вы рисуете, искажен от оригинала. Представьте себе, что вы берете исходную плоскость, распечатываете ее на резиновом листе, растягиваете ее в некоторых местах и ​​зажимаете в других асимметричным образом (без наложения или чего-либо сложного).

( источник )

Вам известны растянутые и нерастянутые координаты каждого из ваших наборов точек, но не основная функция растяжения. Вы знаете нерастянутые координаты новой точки.

Как вы можете оценить, где построить новую точку в растянутых координатах, основываясь на растянутых положениях близлежащих точек? Оно не должно быть точным, поскольку вы не можете определить фактическую функцию растяжения из набора переназначенных точек, если у вас нет дополнительной информации.

другие возможные ключевые слова: деформированная координата плоскости сетки искаженной сетки не развернута

Answer 1

Хорошо, это звучит как искажение изображения. Вот что вы должны сделать:

1. Создайте Триангуляцию Делоне вашей неискаженной сетки и используйте свои знания о соответствии между деформированной и не деформированной сеткой, чтобы создать триангуляцию для деформированной сетки. Теперь вы знаете соответствующие треугольники на каждом изображении, и поскольку перекрытия нет, вы сможете выполнить следующий шаг без особых затруднений.

2. Теперь, чтобы найти соответствующую точку A, на деформированном изображении:

   1. Найдите треугольник A лежит и используйте преобразование между треугольником в не деформированной сетке и деформированной сетке, чтобы выяснить новую позицию.

Это подробно объясняется здесь .

Другим (гораздо более сложным) методом является Сплайн с тонкими пластинами (который также объясняется на слайдах выше).

Answer 2

Другие ответы великолепны. Единственное, что я хотел бы добавить, это то, что вы, возможно, захотите взглянуть на Деформация свободной формы как способ описания деформаций.

Если это полезно, то вполне возможно подогнать сетку / решетку деформации под ваши известные пары, и тогда у вас будет очень быстрый метод деформации будущих точек.

Answer 3

Я понял, что у вас есть взаимно-однозначное соответствие между обернутыми и развернутыми точками сетки. И я предполагаю, что деформация не настолько велика, что у вас могут быть пересекающиеся линии сетки (как на изображении, которое вы показываете).

Стратегия - это именно то, что предлагает Джейкоб: триангулируйте две сетки так, чтобы между треугольниками было взаимно-однозначное соответствие, найдите точку, которая должна быть отображена в триангуляции, а затем используйте барицентрические координаты в соответствующем треугольнике для вычисления местоположение новой точки.

Preprocess

1. Генерируем Триангуляцию Делоне из точек обернутой сетки, назовем ее WT.
2. Для каждого треугольника в WT добавьте треугольник между соответствующими вершинами в развернутой сетке. Это дает триангуляцию UWT развернутых точек.

Отобразить точку p в свернутую сетку

1. Найдите треугольник T(p1,p2,p3) в UWT, который содержит p.
2. Вычислить барицентрические координаты (b1,b2,b3) из p in T(p1,p2,p3)
3. Пусть Tw(q1,q2,q3) будет треугольником в WT, соответствующем T(p1,p2,p3). Новая позиция -
   b1 * q1 + b2 * q2 + b3 * q3.

Примечания Это дает функцию деформации в виде линейного сплайна . Для более плавного поведения можно использовать ту же триангуляцию, но выполнить приближение более высокого порядка, что приведет к несколько более сложным вычислениям вместо барицентрических координат.

Answer 4

Многое зависит от того, сколько у вас очков. Если у вас есть только один, вы мало что можете с ним сделать - вы можете сместить вторую точку на ту же величину в том же направлении, но у вас недостаточно данных, чтобы действительно добиться большего.

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