Интерполяция движений на плоскости через матр. экспоненту

топ 100 блогов nabbla1 — 27.08.2024 В прошлый раз мы вывели интерполяцию движений на плоскости через некоммутирующие дуальные комплексные числа. По сути, берём конечное положение, делим на начальное, от получившегося частного берём логарифм (он для этих чисел берётся довольно просто), и делим на необходимое число шагов. Затем берём экспоненту (не сильно сложнее обычной формулы Эйлера для комплексных чисел) - и готово, мы получили движение, соответствующее одному шагу.

Сейчас покажу, как того же самого можно добиться в формализме матриц 3х3 и векторов 3х1 вида (x;y;1), через матричную экспоненту.



Формализм достаточно распространённый. Хотя у нас в задаче и два измерения, но матрица 2х2 может выражать лишь поворот. Для описания произвольного движения надо ещё добавить вектор параллельного переноса, но тогда движение будет записываться аж ДВУМЯ операциями: умножить на матрицу и прибавить вектор. Чтобы свести движение к одной операции матричного умножения, добавляют "фиктивную" третью координату, которая всегда равна единице, и тогда матрица произвольного движения выглядит так:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}cos(\alpha)&-sin(\alpha)&\Delta{x}\\sin(\alpha)&cos(\alpha)&\Delta{y}\\0&0&1\end{pmatrix}

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

Когда мы разбирались с некомм. дуал. компл. числами, мы стали находить экспоненту от числа с нулевой действительной частью, по той причине, что действительная часть всё равно коммутирует с любой другой, и потому мы знали, что можем наш ответ (где есть мнимая и дуальная часть, но нет действительной) помножить на экспоненту от действительной части - это и будет экспонента В ОБЩЕМ ВИДЕ.

А вот брать матричную экспоненту от матрицы, указанной выше, мы НЕ БУДЕМ, слишком сложно, да и не нужно! Нам нужно взять её лишь от "генератора произвольного движения". Пусть у нас есть произвольный вектор r вида (x;y;1). Применив к нему бесконечно малое движение, а именно, поворот на угол α и сдвиг на (Δx; Δy), мы получим новый вектор:

Интерполяция движений на плоскости через матр. экспоненту \vec{\mathbf{r}}_1=\vec{\mathbf{r}}+G\vec{\mathbf{r}}=\vec{\mathbf{r}}+\begin{pmatrix}0&-\alpha&\Delta{x}\\\alpha&0&\Delta{y}\\0&0&0\end{pmatrix}\vec{\mathbf{r}}=(E+G)\vec{\mathbf{r}}

(E - единичная матрица 3х3)

Матрица G и будет генератором произвольного движения. Получить её можно, заменив в обычной матрице движения на плоскости cos(α) единицей, sin(α) просто на α, и затем вычесть из получившегося единичную матрицу.

Собственно, E+G - это начало разложения в ряд матрицы exp(G). Для малых движений такого разложения достаточно, а ежели мы хотим перейти уже к "крупным" движениям, нужна честная экспонента.

Легко, к примеру, иллюстрируется матрица 2х2, генерирующую поворот на угол α (назовём её R - rotation). Умножая её на вектор (x;y), получим:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}0&-\alpha\\\alpha&0\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\alpha\begin{pmatrix}-y\\x\end{pmatrix}

Из вектора мы получили касательную к нему, идущую против часовой стрелки (если α положительный), длина которой равна длине дуги, которую этот вектор должен будет описать при повороте на α. В первом приближении, чтобы изобразить этот поворот, нам достаточно прибавить касательную к вектору - вот мы и получим обновлённый вектор.

А если нужно повысить точность, мы можем разбить α на N частей, и применить N последовательных преобразований, т.е найти матрицу:

Интерполяция движений на плоскости через матр. экспоненту (E+\frac{1}{N}\begin{pmatrix}0&-\alpha\\\alpha&0\end{pmatrix})^N

Что как раз напоминает предел, которым можно определить exp(x), надо лишь N устремить к бесконечности. Ещё один способ показать, как экспонента порождает повороты, у меня приведён в ликбезе по кватернионам, глава "запись вращения через кватернионы". Там мы пришли и к ряду, также мы можем сделать и здесь:

Интерполяция движений на плоскости через матр. экспоненту exp(\begin{pmatrix}0&-\alpha\\\alpha&0\end{pmatrix})=E+\begin{pmatrix}0&-\alpha\\\alpha&0\end{pmatrix}+\frac{1}{2}\begin{pmatrix}0&-\alpha\\\alpha&0\end{pmatrix}^2+\frac{1}{6}\begin{pmatrix}0&-\alpha\\\alpha&0\end{pmatrix}^3+\dots

Для такой простой матрицы 2х2 можно найти результат прямо "в лоб", почленно. Возведём её в квадрат:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}0&-\alpha\\\alpha&0\end{pmatrix}^2=\begin{pmatrix}-\alpha^2&0\\0&-\alpha^2\end{pmatrix}=-\alpha^2{E}

И дальше уже соображаем: при возведении матрицы R в чётную степень 2n будем получать единичную матрицу, помноженную на (-1)nα2n, а при возведении в нечётную степень 2n+1 - исходную R, дополнительно помноженную на (-1)nα2n. И получится:

Интерполяция движений на плоскости через матр. экспоненту https://latex.codecogs.com/svg.latex?exp(R)=(1-\frac{\alpha^2}{2}+\frac{\alpha^4}{24}+\dots)E+(\alpha-\frac{\alpha^3}{6}+\frac{\alpha^5}{120}+\dots)\begin{pmatrix}0&-1\\1&0\end{pmatrix}

Первую скобку тут же опознаём как разложение cos(α) в ряд, а вторую скобку - как разложение sin(α), так что:

Интерполяция движений на плоскости через матр. экспоненту exp(R)=cos(\alpha)\begin{pmatrix}1&0\\0&1\end{pmatrix}+sin(\alpha)\begin{pmatrix}0&-1\\1&0\end{pmatrix}=\begin{pmatrix}cos(\alpha)&-sin(\alpha)\\sin(\alpha)&cos(\alpha)\end{pmatrix}

Обычная матрица поворота, кто бы мог подумать!

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

Тут я поначалу испугался подхода "в лоб", полагая, что при последовательном возведении в степень начнётся какой-то лютый песец. И оттого решил сделать "как учили", через Жорданову форму. Первым делом нужно найти собственные значения:

Интерполяция движений на плоскости через матр. экспоненту \begin{vmatrix}-\lambda&-\alpha&\Delta{x}\\\alpha&-\lambda&\Delta{y}\\0&0&-\lambda\end{vmatrix}=-\lambda(\lambda^2+\alpha^2)=0

Если α=0, получим собственное значение 0 с кратностью 3. Тут, согласно теории, начинается что-то страшное в виде "жордановой клетки 3х3" и хитро находимых корневых векторов, но, по счастью, при α=0 мы и "в лоб" сообразим. Ведь тогда G2=0, следовательно, exp(G)=1+G (все последующие слагаемые нулевые), а значит,

Интерполяция движений на плоскости через матр. экспоненту exp\begin{pmatrix}0&0&\Delta{x}\\0&0&\Delta{y}\\0&0&0\end{pmatrix}=\begin{pmatrix}1&0&\Delta{x}\\0&1&\Delta{y}\\0&0&1\end{pmatrix}

Кто бы сомневался: чистый параллельный перенос (без поворотов) работает одинаково хоть на малых значениях, хоть на сколько угодно больших!

Так что разберёмся с "основным" вариантом, когда α≠0. Тогда имеем 3 различных собственных значения: 0 и ±iα. Это очень хорошо: наша Жорданова форма свелась к простой диагональной матрице и базиса из собственных векторов! Для каждого собственного значения надо найти собственный вектор. Для начала, для λ1=0:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}0&-\alpha&\Delta{x}\\\alpha&0&\Delta{y}\\0&0&0\end{pmatrix}\begin{pmatrix}v_x\\v_y\\v_z\end{pmatrix}=0

Применяем метод Гаусса, причём преобразуем исключительно матрицу 3х3, без добавочки в виде вектора 3х1, поскольку он всё равно нулевой, и как эти нули между с собой не складывай и на константы не умножай - так и останутся нули!

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}0&-\alpha&\Delta{x}\\\alpha&0&\Delta{y}\\0&0&0\end{pmatrix}\Leftrightarrow\begin{pmatrix}1&0&\Delta{y}/\alpha\\\0&1&-\Delta{x}/\alpha\\0&0&0\end{pmatrix}

(верхние строки поменяли местами и поделили на α)

Нули в нижней строке означают, что мы можем произвольно выбрать значение z. Постановим его равным α, тогда x,y найдём по верхним строчкам, в итоге:

Интерполяция движений на плоскости через матр. экспоненту v_0=\begin{pmatrix}-y\\x\\\alpha\end{pmatrix}

Теперь найдём собственный вектор для собственного значения +iα:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}-i\alpha&-\alpha&\Delta{x}\\\alpha&-i\alpha&\Delta{y}\\0&0&-i\alpha\end{pmatrix}\Leftrightarrow\begin{pmatrix}1&-i&\Delta{y}/\alpha\\-1&i&-i\Delta{x}/\alpha\\0&0&1\end{pmatrix}\Leftrightarrow\begin{pmatrix}1&i&\Delta{y}/\alpha\\0&0&\Delta{y}/\alpha-i\Delta{x}/\alpha\\0&0&1\end{pmatrix}

Неприятные выкладки в правом столбце, на самом деле, "уничтожаются" прибавлением к верхним строкам нижней с нужными коэффициентами. Тупо всё над ней зануляем:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}1&i&0\\0&0&0\\0&0&1\end{pmatrix}

На этот раз у нас произвольная вторая компонента вектора, пусть это будет единичка. Третья компонента - строго НОЛЬ, решение уравнения z=0 (кто бы мог подумать), а первая выражается через вторую. Получаем вектор:

Интерполяция движений на плоскости через матр. экспоненту v_1=\begin{pmatrix}i\\1\\0\end{pmatrix}

То же самое проделывается для собственного значения -iα, только другой знак. Получаем:

Интерполяция движений на плоскости через матр. экспоненту v_2=\begin{pmatrix}-i\\1\\0\end{pmatrix}

Теперь мы можем построить матрицу из собственных значений по главной диагонали, именно её мы загоним под экспоненту:

Интерполяция движений на плоскости через матр. экспоненту J=\begin{pmatrix}0&0&0\\0&i\alpha&0\\0&0&-i\alpha\end{pmatrix}

Давайте и экспоненту сразу возьмём:

Интерполяция движений на плоскости через матр. экспоненту exp(J)=\begin{pmatrix}1&0&0\\0&e^{i\alpha}&0\\0&0&e^{-i\alpha}\end{pmatrix}

И ещё нам нужна матрица из собственных векторов:

Интерполяция движений на плоскости через матр. экспоненту V=\begin{pmatrix}-y&i&-i\\x&1&1\\\alpha&0&0\end{pmatrix}

На неё мы домножим результат слева. Но ещё надо найти обратную от неё... Увы, я не музыкант, в дополнительных минорах теряюсь напрочь, все посчитать и ни разу в знаке не ошибиться - просто невыполнимая для меня задача... Так что по-старинке, через элементарные преобразования, лучше посчитаю:

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

Интерполяция движений на плоскости через матр. экспоненту \left(\begin{array}{ccc|ccc}1&-i/y&i/y&-1/y&0&0\\0&1/x+i/y&1/x-i/y&1/y&1/x&0\\0&i/y&-i/y&1/y&0&1/\alpha\end{array}\right)\Leftrightarrow\left(\begin{array}{ccc|ccc}1&-i/y&i/y&-1/y&0&0\\0&1&-1&-i&0&-iy/\alpha\\0&1/x+i/y&1/x-i/y&1/y&1/x&0\end{array}\right)\Leftrightarrow
(вычли первую строчку из двух других, затем две нижние строки поменяли местами, и среднюю поделили на i/y)

Интерполяция движений на плоскости через матр. экспоненту \left(\begin{array}{ccc|ccc}1&0&0&0&0&1/\alpha\\0&1&-1&-i&0&-iy/\alpha\\0&0&2/x&i/x&1/x&iy/(\alpha{x})-1/\alpha\end{array}\right)\Leftrightarrow\left(\begin{array}{ccc|ccc}1&0&0&0&0&1/\alpha\\0&1&0&-i/2&1/2&-iy/(2\alpha)-x/(2\alpha)\\0&0&1&i/2&1/2&iy/(2\alpha)-x/(2\alpha)\end{array}\right)
(к первой строчке прибавили вторую, домноженную на i/y, а из третьей вычли вторую, домноженную на 1/x+i/y, затем третью строчку поделили на 2/x и прибавили к второй)

Фух, в правой части мы получили обратную матрицу...

Кстати, здесь у нас в исходной задаче никаких комплексных чисел не было, и в ответе их быть не должно, сейчас они выползли, чтобы появились собственные векторы.

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

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}-y&i&-i\\x&1&1\\\alpha&0&0\end{pmatrix}\begin{pmatrix}1&0&0\\0&e^{i\alpha}&0\\0&0&e^{-i\alpha}\end{pmatrix}=\begin{pmatrix}-y&ie^{i\alpha}&-ie^{-i\alpha}\\x&e^{i\alpha}&e^{-i\alpha}\\\alpha&0&0\end{pmatrix}

И теперь этот результат справа на матрицу, обратную матрицу собственных векторов:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}-y&ie^{i\alpha}&-ie^{-i\alpha}\\x&e^{i\alpha}&e^{-i\alpha}\\\alpha&0&0\end{pmatrix}\begin{pmatrix}0&0&1/\alpha\\-i/2&1/2&-\frac{iy+x}{2\alpha}\\i/2&1/2&\frac{iy-x}{2\alpha}\end{pmatrix}=\begin{pmatrix}e^{i\alpha}/2+e^{-i\alpha}/2&ie^{i\alpha}/2-ie^{-i\alpha}/2&\frac{cos(\alpha)-1}{\alpha}y+\frac{sin(\alpha)}{\alpha}x\\-ie^{i\alpha}/2+ie^{-i\alpha}/2&\frac{e^{i\alpha}+e^{-i\alpha}}{2}&\frac{1-cos(\alpha)}{\alpha}x+\frac{sin(\alpha)}{\alpha}y\\0&0&1\end{pmatrix}

Это и есть ответ, только его надо немного причесать. Экспоненты мы по известным формулам превращаем в синус и косинус, т.е верхний квадрат 2х2 - это снова самая обычная матрица поворота, которую мы вывели таким вот извращённым способом. А справа пока что слегка поменяем местами слагаемые:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}cos(\alpha)&-sin(\alpha)&\frac{sin(\alpha)}{\alpha}x-\frac{1-cos(\alpha)}{\alpha}y\\sin(\alpha)&cos(\alpha)&\frac{1-cos(\alpha)}{\alpha}x+\frac{sin(\alpha)}{\alpha}y\\0&0&1\end{pmatrix}

Это уже вполне сойдёт за ответ!

Ровно так я его находил в эту субботу. Надо же было развеяться и отдохнуть от работы... А сегодня решил попробовать всё-таки посчитать В ЛОБ, т.е возводить исходную матрицу G в квадрат, затем в куб, и потом найти закономерности и найти каждый компонент итоговой матрицы по отдельности. Оказывается, В ДВЕ СТРОЧКИ делается! Вот G2:

Интерполяция движений на плоскости через матр. экспоненту G^2=\begin{pmatrix}-\alpha^2&0&-\alpha{y}\\0&-\alpha^2&\alpha{x}\\0&0&0\end{pmatrix}

Далее, G3:

Интерполяция движений на плоскости через матр. экспоненту G^3=\begin{pmatrix}0&\alpha^3&-\alpha^2{x}\\-\alpha^3&0&-\alpha^2{y}\\0&0&0\end{pmatrix}

И, для порядку, G4:

Интерполяция движений на плоскости через матр. экспоненту G^4=\begin{pmatrix}\alpha^4&0&\alpha^3{y}\\0&\alpha^4&-\alpha^3{x}\\0&0&0\end{pmatrix}

Ещё раз убеждаемся, что верхний квадрат 2х2 - всё та же матрица поворота (её мы уже выводили), в нижней строке получится 0;0;1 (единица - из единичной матрицы E), то есть надо лишь два правых элемента посчитать. Для верхнего из них:

Интерполяция движений на плоскости через матр. экспоненту (exp(G))_{13}=(1-\frac{\alpha^2}{6}+\frac{\alpha^4}{120}+\dots)x-(\frac{\alpha}{2}-\frac{\alpha^3}{24}+\frac{\alpha^5}{720}+\dots)y
Первая скобка - как синус, только все степени на единичку ниже, то бишь sin(α)/α. А вторая - почти косинус, только знак другой и единицы нет, и тоже степени на единицу ниже. Короче, (1-cos(α)/α.

Ну и то же самое со вторым, ответ получается тот же, что и через Жорданову форму. Ещё и надёжней: там мы при нахождении обратной матрицы собственных векторов очень вольно обращались с обратными величинами, а ведь по-хорошему надо было отдельно рассмотреть x=0 или y=0... И перед этим пришлось два разных варианта посмотреть, с α=0 либо нет, и потом их "склеивать". А тут "из коробки" всё склеено, надо просто помнить, что ряды для sin(α)/α и подобных соответствуют функциям, где особые точки уже устранены.

Небольшая проверка на вшивость.
При α стремящемся к нулю, sin(α)/α стремится к единичке, тогда как (1-cos(α))/α - к нулю, так что на α=0 у нас не возникает "ступеньки" с ранее найденной матрицей. Само по себе появление "синус икс на икс" обнадёживает: ведь два этих формализма (матричная экспонента и некомм. дуал. компл. числа) должны в итоге дать идентичные результаты! Но там синус был от половинного угла, а здесь - от полного. Ещё и "косинус икс на икс" некий выполз...

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

Давайте запишем два этих числа в матричной форме:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}t_x\\t_y\end{pmatrix}=\begin{pmatrix}\frac{sin(\alpha)}{\alpha}&-\frac{(1-cos(\alpha)}{\alpha}\\\frac{(1-cos(\alpha)}{\alpha}&\frac{sin(\alpha)}{\alpha}\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}

1-cos(α) можно сразу заменить на 2sin2(α/2), ну а sin(α), за компанию - на 2sin(α/2)cos(α/2). И потом синус вместе со знаменателем выносим общим множителем перед матрицей:

Интерполяция движений на плоскости через матр. экспоненту \begin{pmatrix}t_x\\t_y\end{pmatrix}=\frac{sin(\alpha/2)}{\alpha/2}\begin{pmatrix}cos(\alpha/2)&-sin(\alpha/2)\\sin(\alpha/2)&cos(\alpha/2)\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}

Вот это поворот!
Теперь и здесь у нас один-единственный "синус икс на икс", с половинным углом в аргументе, а впридачу к нему поворот на половинный угол! Казалось бы, причём здесь кватернионы и некомм. дуал. компл. числа!

Зато теперь найти обратное преобразование, "матричный логарифм" - вообще раз плюнуть! sin(α/2)/(α/2) просто обращаем, получая (α/2)/sin(α/2), а матрицу половинного поворота - транспонируем, чтобы развернуться назад.

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



Нда, аналитическая геометрия и линейная алгебра были моим самым нелюбимым предметом в институте. Вот и не знаю, то ли Стокгольмский синдром, то ли весёлый икигай.

Оставить комментарий

Популярные посты:
nero
Проверить свою организацию: зачем это нужно даже владельцу
kwakin_misha
Тёма получил новую игрушку
nikolian
О как!
magman67
Запрет на открытие российскими туристами счетов в тайских банках подтверждён
kacho
Без названия
matsam
Закончили
maria_gromakova
8/92
abigail_lazarus
У мессира Воланда была дочь
obezzyann
Анатонны. Задание 25. Идиомы
Архив записей в блогах:
Узрел почетного консула Донецкой Народной Республики (фото)
Иду, гуляю по Москве, смотрю, в траве лежит-отдыхает почетный консул Донецкой Народной Республики. Испугался я сначала, подумал, может совсем плохо уже ему, надо растормошить, не помер ли, а то вдруг скорую вызвать надо. Растормошил, а консул на это только обиделся: «Живая я! - заорал ...
Доброе утро :)
...
Спички в цветочном горшке
Рассказываю, зачем я вставляю спички в цветочные горшки. Всем цветоводам советую так делать С тех пор, как мы переехали жить в частный дом, я не устаю заводить новую растительность в виде домашних цветов. Муж смеется, говорит, что огорода мне мало. А я просто люблю наблюдать за ...
Таким будет Музей Героев Украины.
ZN.UA 11 марта в 11:56 Научно-производственная компания "Киев-Проект" опубликовала эскизы проекта реконструкции Дома профсоюзов , пострадавшего от пожара в феврале 2014 года. Эскизы проекта "Реконструкции здания Дома профсоюзов под музей героев Украины" обнародов ...
К вопросу о природе Хрущевской оттепели
Самое главное это то, что выводы Екатерины Винокуровой (см. ниже) касаются только Хрущёвской номенклатуры, которая впоследствии оказалась номенклатурой предателей. Сталинских генералов Хрущев вычистил почти всех. Моего деда, который был главным энергетиком министерства судостроительной ...
WOW Авто Армия Беларусь Бизнес Видео Дети Жесть Животные Закон Здоровье Игры Интернет Искусство История Казахстан Кино Конфликты Коронавирус Коррупция Косметичка Криминал Кулинария Ликбез Литература Лытдыбр Медицина Мнения Музыка Наука Общество Олимпиада Отдых Отношения Персоны Политика Природа Происшествия Путешествия Разное Разоблачения Реклама Религия СНГ Сиськи События Спорт Страны ТВ и СМИ Творчество Технологии Транспорт Троллинг Финансы Фото Шоубиз Штуки Экономика Юмор