Как нанести точку на искаженную сетку

Question

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

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

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

(Источник)

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

Предварительная обработка

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

Нанесите на карту точку p в обернутую сетку

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

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

Answer 3

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

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

Answer 4

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

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