Как нанести точку на искаженную сетку
-
05-07-2019 - |
Вопрос
Допустим, у вас есть набор точек с координатами в декартовой системе координат.
Вы хотите построить другую точку, и вы знаете ее координаты в той же декартовой системе координат.
Однако сюжет, который вы рисуете, искажен по сравнению с оригиналом.Представьте, что вы берете исходную плоскость, печатаете ее на резиновом листе и растягиваете в одних местах и зажимаете в других асимметричным образом (без перекрытия или чего-либо сложного).
(Источник)
Вы знаете растянутые и нерастянутые координаты каждого из вашего набора точек, но не базовую функцию растяжения.Вы знаете нерастянутые координаты новой точки.
Как вы можете оценить, где построить новую точку в растянутых координатах, основываясь на растянутых положениях близлежащих точек?Это не обязательно должно быть точным, поскольку вы не можете определить фактическую функцию растяжения по набору переназначенных точек, если у вас нет дополнительной информации.
другие возможные ключевые слова:деформированная искаженная сетка разворачивание координат плоскости сетки
Решение
Итак, это звучит как искажение изображения.Это то, что вы должны сделать:
Создать Триангуляция Делоне вашей неискаженной сетки и используйте свои знания о соответствиях между искривленной и неискаженной сеткой, чтобы создать триангуляцию для искривленной сетки.Теперь вы знаете соответствующие треугольники на каждом изображении, и поскольку перекрытия нет, вы сможете выполнить следующий шаг без особых трудностей.
Теперь, чтобы найти соответствующую точку
A
, на искаженном изображении:- Найдите треугольник
A
лежит внутри и использует преобразование между треугольником в развернутой сетке и искривленной сеткой, чтобы определить новое положение.
- Найдите треугольник
Это подробно объясняется в явном виде здесь.
Другим (гораздо более сложным) методом является Тонкий Пластинчатый Шлиц (что также объясняется на слайдах выше).
Другие советы
Я понял, что у вас есть взаимно однозначное соответствие между обернутыми и развернутыми точками сетки.И я предполагаю, что деформация не настолько велика, чтобы у вас могли быть пересекающиеся линии сетки (как на изображении, которое вы показываете).
Стратегия - это именно то, что предлагает Джейкоб:Триангулируйте две сетки таким образом, чтобы между треугольниками было взаимно однозначное соответствие, найдите точку, которая будет отображена в триангуляции, а затем используйте барицентрические координаты в соответствующем треугольнике для вычисления нового местоположения точки.
Предварительная обработка
- Сгенерируйте Триангуляция Делоне из точек обернутой сетки давайте назовем это
WT
. - Для каждого треугольника в
WT
добавьте треугольник между соответствующими вершинами в развернутой сетке.Это дает триангуляциюUWT
из развернутых точек.
Нанесите на карту точку p
в обернутую сетку
- Найдите треугольник
T(p1,p2,p3)
вUWT
который содержитp
. - Вычислить барицентрические координаты
(b1,b2,b3)
изp
вT(p1,p2,p3)
- Пусть
Tw(q1,q2,q3)
быть треугольником вWT
соответствующийT(p1,p2,p3)
.Новая должность - этоb1 * q1 + b2 * q2 + b3 * q3
.
Замечания Это дает функцию деформации в виде линейный сплайн.Для более плавного поведения можно было бы использовать ту же триангуляцию, но сделать аппроксимацию более высокого порядка, что привело бы к немного более сложным вычислениям вместо барицентрических координат.
Другие ответы великолепны.Единственное, что я бы добавил, это то, что вы, возможно, захотите взглянуть на Деформация свободной формы как способ описания деформаций.
Если это полезно, то вполне возможно подогнать деформационную сетку к вашим известным парам, и тогда у вас есть очень быстрый метод деформации будущих точек.
Многое зависит от того, сколько у вас уже есть очков.Если у вас есть только одна точка, вы мало что можете с ней сделать - вы можете сместить вторую точку на ту же величину в том же направлении, но у вас недостаточно данных, чтобы действительно добиться большего.
Если у вас есть достаточное количество существующих точек, вы можете выполнить подгонку поверхности по этим точкам и использовать это для приблизительного определения правильного положения новой точки.Учитывая N точек, вы всегда можете получить идеальную подгонку, используя полином порядка N, но вы редко хотите это делать - вместо этого вы обычно предполагаете, что функция stretch является функцией довольно низкого порядка (напримерквадратичный или кубический) и подогнать поверхность к точкам на этой основе.Затем вы размещаете свою новую точку на основе функции для вашей подогнанной поверхности.