Какое свойство не относится к аффинным преобразованиям
Образ прямой линии.
Изучим геометрические свойства аффинных преобразований. Ниже (f) обозначает аффинное преобразование, записываемое в декартовой системе координат (O, boldsymbol{e}_{1}, boldsymbol{e}_{2}) формулами
$$
x^{*}=a_{1}x+b_{1}y+c_{1}, y^{*}=a_{2}x+b_{2}y+c_{2}.label{ref1}
$$
при условии
$$
begin{vmatrix}
a_{1}& b_{1}\
a_{2}& b_{2}
end{vmatrix} neq 0.label{ref2}
$$
Рассмотрим на плоскости прямую линию с уравнением (boldsymbol{r}=boldsymbol{r}_{0}+boldsymbol{a}t) и найдем ее образ при преобразовании (f). (Под образом прямой понимается множество образов ее точек.) Радиус-вектор образа (M^{*}) произвольной точки (M) можно вычислить так:
$$
overrightarrow{OM^{*}}=overrightarrow{Of(O)}+foverrightarrow{(O)M^{*}}=boldsymbol{c}+f(boldsymbol{r}).nonumber
$$
Здесь (boldsymbol{c}) — постоянный вектор (overrightarrow{Of}(O)), а (boldsymbol{r}) — радиус-вектор точки (M). Согласно (11) §2 мы получаем
$$
overrightarrow{OM^{*}}=boldsymbol{c}+f(boldsymbol{r}_{0})+f(boldsymbol{a})t.label{ref3}
$$
Так как (f) — аффинное преобразование и (boldsymbol{a} neq boldsymbol{0}), то (boldsymbol{a}) перейдет в вектор (f(boldsymbol{a}) neq 0), и уравнение eqref{ref3} является уравнением прямой линии. Итак, образы всех точек прямой (boldsymbol{r}=boldsymbol{r}_{0}+boldsymbol{a}t) лежат на прямой eqref{ref3}.
Более того, преобразование (f) определяет взаимно однозначное отображение одной прямой на другую, так как при сделанном здесь выборе начальных точек и направляющих векторов точка (M^{*}) имеет на прямой eqref{ref3} то же значение параметра (t), что и точка (M) на исходной прямой. Отсюда мы получаем первое утверждение.
Утверждение 1.
При аффинном преобразовании:
- прямая линия переходит в прямую линию;
- отрезок переходит в отрезок;
- параллельные прямые переходят в параллельные.
Доказательство.
Для доказательства второго утверждения достаточно заметить, что отрезок прямой состоит из таких точек, у которых значения параметра удовлетворяют неравенству вида (t_{1} leq t leq t_{2}) Третье утверждение следует из того, что при аффинном преобразовании коллинеар-ные векторы переходят в коллинеарные.
Утверждение 2.
При аффинном преобразовании отношение длин параллельных отрезков не изменяется.
Доказательство.
Пусть отрезки (AB) и (CD) параллельны. Это значит, что существует такое число (lambda), что (overrightarrow{AB}=lambda overrightarrow{CD}). Образы векторов (overrightarrow{AB}) и (overrightarrow{CD}) связаны той же зависимостью (overrightarrow{A^{*}B^{*}}=lambda overrightarrow{C^{*}D^{*}}). Отсюда вытекает, что
$$
frac{|overrightarrow{AB}|}{|overrightarrow{CD}|}=frac{|overrightarrow{A^{*}B^{*}}|}{|overrightarrow{C^{*}D^{*}}|}=|lambda|.nonumber
$$
Следствие.
Если точка (C) делит отрезок (AB) в некотором отношении (lambda), то ее образ (C^{*}) делит образ (A^{*}B^{*}) отрезка (AB) в том же отношении (lambda).
Изменение площадей при аффинном преобразовании.
Для начала рассмотрим ориентированный параллелограмм. Выберем общую декартову систему координат (O, boldsymbol{e}_{1}, boldsymbol{e}_{2}) и обозначим через ((p_{1}, p_{2})) и ((q_{1}, q_{2})) компоненты векторов (boldsymbol{p}) и (boldsymbol{q}), на которых он построен. Площадь параллелограмма мы можем вычислить, пользуясь формулой:
$$
S_{pm}=S_{pm} (boldsymbol{p}, boldsymbol{q})=(p_{1}q_{2}-p_{2}q_{1}) S_{pm} (boldsymbol{e}_{1}, boldsymbol{e}_{2}).nonumber
$$
Пусть аффинное преобразование (f) записывается в выбранной системе координат формулами eqref{ref1}. Из ранее доказанного утверждения следует, что векторы (f(boldsymbol{p})) и (f(boldsymbol{q})) имеют в базисе (f(boldsymbol{e}_{1}), f(boldsymbol{e}_{2})) те же компоненты ((p_{1}, p_{2})) и ((q_{1}, q_{2})), что и векторы (boldsymbol{p}) и (boldsymbol{q}) в базисе (boldsymbol{e}_{1}, boldsymbol{e}_{2}). Образ параллелограмма построен на векторах (f(boldsymbol{p})) и (f(boldsymbol{q})), и площадь его равна
$$
S_{pm}^{*}=S_{pm} (f(boldsymbol{p}), f(boldsymbol{q}))=(p_{1}q_{2}-p_{2}q_{1}) S_{pm} (f(boldsymbol{e}_{1}), f(boldsymbol{e}_{2})).nonumber
$$
Вычислим последний множитель. Как мы знаем из уже доказанного утверждения 7, координаты векторов (f(boldsymbol{e}_{1}), f(boldsymbol{e}_{2})) равны соответственно ((a_{1}, a_{2})) и ((b_{1}, b_{2})). Поэтому (S_{pm} (f(boldsymbol{e}_{1}), f(boldsymbol{e}_{2}))=(a_{1}b_{2}-a_{2}b_{1}) S_{pm} (boldsymbol{e}_{1}, boldsymbol{e}_{2})) и
$$
S_{pm}^{*}=(p_{1}q_{2}-p_{2}q_{1})(a_{1}b_{2}-a_{2}b_{1}) S_{pm} (boldsymbol{e}_{1}, boldsymbol{e}_{2}).nonumber
$$
Отсюда мы видим, что
$$
frac{S_{pm}^{*}}{S_{pm}}=begin{vmatrix}
a_{1}& b_{1}\
a_{2}& b_{2}
end{vmatrix}.label{ref4}
$$
Таким образом, отношение площади образа ориентированного параллелограмма к площади этого параллелограмма одинаково для всех параллелограммов и равно (a_{1}b_{2}-a_{2}b_{1}).
Отсюда следует, что данный детерминант не зависит от выбора системы координат, в которой записано преобразование, хотя он вычисляется по коэффициентам, зависящим от системы координат. Эта величина — инвариант, выражающий геометрическое свойство преобразования.
Из формулы eqref{ref4} видно, что отношение площади образа неориентированного параллелограмма к его площади равно
$$
S^{*}/S=|a_{1}b_{2}-a_{2}b_{1}|.label{ref5}
$$
Если (a_{1}b_{2}-a_{2}b_{1} > 0), то ориентации всех ориентированных параллелограммов сохраняются при преобразовании, а если (a_{1}b_{2}-a_{2}b_{1} < 0), то для каждого ориентированного параллелограмма ориентация образа противоположна его ориентации.
Займемся теперь площадями других фигур. Каждый треугольник может быть дополнен до параллелограмма, площадь которого равна удвоенной площади треугольника. Поэтому отношение площади образа треугольника к площади этого треугольника удовлетворяет равенству eqref{ref5}.
Каждый многоугольник может быть разбит на треугольники. Следовательно, формула eqref{ref5} справедлива и для произвольных многоугольников.
Мы не будем здесь касаться определения площади произвольной криволинейной фигуры. Скажем лишь, что в тех случаях, когда эта площадь определена, она равна пределу площадей некоторой последовательности многоугольников, вписанных в рассматриваемую фигуру. Из теории пределов известно следующее предположение: если последовательность (S_{n}) стремится к пределу (S), то последовательность (delta S_{n}), где (delta) постоянное, стремится к пределу (delta S). На основании этого предложения мы заключаем, что формула eqref{ref5} справедлива в самом общем случае.
В качестве примера найдем выражение площади эллипса через его полуоси. Ранее мы доказали, что эллипс с полуосями (a) и (b) может быть получен сжатием окружности радиуса (a) к прямой, проходящей через ее центр. Коэффициент сжатия равен (b/a). В одном из примеров мы получили координатную запись сжатия к прямой (x^{*}=x), (y^{*}=lambda y). Детерминант из коэффициентов в этих формулах равен (lambda), то есть в нашем случае (b/a). Таким образом, отношение площади эллипса к площади окружности равно (b/a), и эта площадь равна (S=(b/a)pi a^{2}). Окончательно имеем
$$
S=pi ab.nonumber
$$
Образы линий второго порядка.
Мы видели, что прямая линия переходит в прямую. Это частный случай следующего утверждения.
Утверждение 3.
Аффинное преобразование переводит алгебраическую линию в алгебраическую линию того же порядка.
Доказательство.
В самом деле, пусть линия (L) в декартовой системе координат (O, boldsymbol{e}_{1}, boldsymbol{e}_{2}) имеет алгебраическое уравнение порядка (p). Мы уже доказали, что образы всех точек линии (L) при аффинном преобразовании (f) имеют в системе координат (f(O), f(boldsymbol{e}_{1}), f(boldsymbol{e}_{2})) те же координаты, что и их прообразы в системе координат (O, boldsymbol{e}_{1}, boldsymbol{e}_{2}). Следовательно, координаты образов в системе (f(O), f(boldsymbol{e}_{1}), f(boldsymbol{e}_{2})) связаны тем же алгебраическим уравнением порядка (p). Этого достаточно, чтобы сделать нужное нам заключение.
Из доказанного выше утверждения, в частности, следует, что линия второго порядка при аффинном преобразовании перейдет в линию второго порядка. Мы докажем более сильное утверждение. Как мы уже знаем, линии второго порядка можно разделить на семь классов. Мы увидим, что класс линии сохраняется при аффинном преобразовании. На этом основании классы линий, перечисленные в указанной теореме, называются аффинными классами. Итак, докажем новое утверждение.
Утверждение 4.
Линия второго порядка, принадлежащая к одному из аффинных классов, при любом аффинном преобразовании может перейти только в линию того же класса. Каждую линию второго порядка подходящим аффинным преобразованием можно перевести в любую другую линию того же аффинного класса.
Доказательство.
Линию мы назовем ограниченной, если она лежит внутри некоторого параллелограмма. Легко видеть, что при аффинном преобразовании ограниченная линия должна перейти в ограниченную, а неограниченная — в неограниченную.
- Эллипс — ограниченная линия второго порядка. Кроме эллипсов ограничены только линии, состоящие из одной точки, то есть пары мнимых пересекающихся прямых. Поскольку эллипс ограничен и состоит больше, чем из одной точки, он может перейти только в эллипс.
- Гипербола состоит из двух отдельных ветвей. Это свойство можно сформулировать так, что будет ясна его неизменность при аффинных преобразованиях. Именно, существует прямая линия, не пересекающая гиперболу, но пересекающая некоторые ее хорды.Из всех линий второго порядка только гиперболы и пары параллельных прямых обладают этим свойством. У гиперболы ветви не прямые линии, и потому при аффинном преобразовании она может перейти только в гиперболу.
- Парабола — неограниченная линия второго порядка, состоящая из одного непрямолинейного куска. Этим свойством не обладают никакие другие линии второго порядка, и потому парабола может перейти только в параболу.
- Если линия второго порядка представляет собой точку (пару мнимых пересекающихся прямых), прямую (пару совпавших прямых), пару пересекающихся или пару параллельных прямых, то из доказанных ранее свойств аффинных преобразований следует, что эта линия не может перейти в линию никакого другого класса.
Докажем вторую часть предложения. В уже доказанной нами теореме канонические уравнения линий второго порядка написаны в декартовой прямоугольной системе координат и содержат параметры (a, b, …) Если мы откажемся от ортонормированности базиса, то сможем произвести дальнейшие упрощения канонических уравнений и привести их к виду, не содержащему параметров. Например, замена координат (x’=x/a), (y’=y/b) переводит уравнение эллипса (x^{2}a^{2}+y^{2}b^{2}=1) в уравнение (x’^{2}+y’^{2}=1), каковы бы ни были (a) и (b). (Последнее уравнение не есть уравнение окружности, так как новая система координат не декартова прямоугольная.)
Читатель без труда покажет, что канонические уравнения линий второго порядка переходом к подходящей системе координат могут быть преобразованы в уравнения:
- (x^{2}+y^{2}=1);
- (x^{2}+y^{2}=0);
- (x^{2}-y^{2}=1);
- (x^{2}-y^{2}=0);
- (y^{2}=2x);
- (y^{2}-1=0);
- (y^{2}=0).
Такую систему координат мы назовем аффинной канонической системой координат.
Из ранее доказанного утверждения следует, что аффинное преобразование, которое совмещает аффинные канонические системы координат двух линий одного аффинного класса, совмещает и эти линии. Это заканчивает доказательство.
Разложение ортогонального преобразования.
Теорема 1.
Каждое ортогональное преобразование раскладывается в произведение параллельного переноса, поворота и, возможно, осевой симметрии.
Доказательство.
Пусть (f) — ортогональное преобразование и (vartriangle ABC) — равнобедренный прямоугольный треугольник с прямым углом (A). При преобразовании (f) он перейдет в равный ему треугольник (vartriangle A^{*}B^{*}C^{*}) с прямым углом при вершине (A^{*}). Теорема будет доказана, если, производя последовательно параллельный перенос (p), поворот (q) и (в случае необходимости) осевую симметрию (r), мы сможем совместить треугольники (ABC) и (A^{*}B^{*}C^{*}). Действительно, произведение (rqp) — аффинное преобразование так же, как и (f), а аффинное преобразование однозначно определяется образами трех точек, не лежащих на одной прямой. Поэтому (rqp) совпадает с (f).
Итак, переведем (A) и (A^{*}) параллельным переносом (p) на вектор (overrightarrow{AA^{*}}) (если (A=A^{*}), то (p) — тождественное преобразование). Затем поворотом (q) вокруг точки (A^{*}) совместим (p(B)) с (B^{*}) (возможно, и это преобразование окажется тождественным). Точка (q(p(C))) либо совпадает с (C^{*}), либо симметрична ей относительно прямой (A^{*}B^{*}). В первом случае цель уже достигнута, а во втором потребуется осевая симметрия относительно указанной прямой. Теорема доказана.
Следует иметь в виду, что полученное разложение ортогонального преобразования не однозначно. Более того, можно поворот или параллельный перенос разложить в произведение осевых симметрий, произведение параллельного переноса и поворота представить как один поворот и так далее. Мы не будем уточнять, как это сделать, а выясним следующее общее свойство всех таких разложений.
Утверждение 5.
При любом разложении ортогонального преобразования в произведение любого числа параллельных переносов, поворотов и осевых симметрий четность числа осевых симметрий, входящих в разложение, одна и та же.
Доказательство.
Для доказательства рассмотрим на плоскости произвольный базис и проследим за изменением его ориентации (направления кратчайшего поворота от (boldsymbol{e}_{1}) к (boldsymbol{e}_{2})) при осуществляемых преобразованиях. Заметим, что поворот и параллельный перенос не меняют ориентацию ни одного базиса, а осевая симметрия меняет ориентацию любого базиса. Поэтому, если данное ортогональное преобразование меняет ориентацию базиса, то в любое его разложение должно входить нечетное число осевых симметрий. Если же ориентация базиса не меняется, то число осевых симметрий, входящих в разложение, может быть только четным.
Определение.
Ортогональные преобразования, которые могут быть разложены в произведение параллельного переноса и поворота, называются ортогональными преобразованиями первого рода, а остальные — ортогональными преобразованиями второго рода.
Ортогональное преобразование в декартовой прямоугольной системе координат записывается формулами:
$$
begin{array}{cc}
& x^{*}=x cos varphi mp y sin varphi+c_{1},\
& y^{*}=x sin varphi pm y cos varphi+c_{2}.
end{array}.nonumber
$$
При верхних знаках коэффициентов у (y) в этих формулах детерминант, составленный из коэффициентов, равен +1, а при нижних знаках он равен —1. Отсюда и из формулы eqref{ref4} следует следующее утверждение.
Утверждение 6.
Ортогональное преобразование первого рода записывается в декартовой прямоугольной системе координат формулами
$$
begin{array}{cc}
& x^{*}=x cos varphi mp y sin varphi+c_{1},\
& y^{*}=x sin varphi pm y cos varphi+c_{2}.
end{array}.nonumber
$$
с верхними знаками у коэффициентов при (y), а ортогональное преобразование второго рода — с нижними знаками.
Разложение аффинного преобразования.
Мы видели, насколько аффинное преобразование может изменить плоскость: окружность может перейти в эллипс, правильный треугольник — в совершенно произвольный. Казалось бы, никакие углы при этом сохраниться не могут. Однако имеет место следующее утверждение
Утверждение 7.
Для каждого аффинного преобразования существуют две взаимно перпендикулярные прямые, которые переходят во взаимно перпендикулярные прямые.
Доказательство.
Для доказательства рассмотрим какую-либо окружность. При данном аффинном преобразовании она перейдет в эллипс. Каждая ось эллипса — множество середин хорд, параллельных другой оси. При аффинном преобразовании хорда перейдет в хорду, параллельность должна сохраниться, а середина отрезка переходит в середину его образа. Поэтому прообразы осей эллипса — отрезки, обладающие тем же свойством: каждый из них есть множество середин хорд окружности, параллельных другому отрезку. Такие отрезки непременно являются двумя взаимно перпендикулярными диаметрами окружности. Это то, что нам требовалось: существуют два взаимно перпендикулярных диаметра окружности, которые переходят во взаимно перпендикулярные отрезки — оси эллипса.
Стоит отметить один особый случай: окружность при аффинном преобразовании может перейти в окружность. В этом случае то же рассуждение проходит с любыми двумя взаимно перпендикулярными диаметрами окружности-образа. Очевидно, что при этом любые два взаимно перпендикулярных направления остаются перпендикулярными.
Определение.
Два взаимно перпендикулярных направления называются главными или синугулярными направлениями аффинного преобразования (f), если они переходят во взаимно перпендикулярные направления.
Теорема 2.
Каждое аффинное преобразование раскладывается в произведение ортогонального преобразования и двух сжатий к двум взаимно перпендикулярным прямым.
Доказательство.
Доказательство аналогично доказательству теоремы 1. Рассмотрим аффинное преобразование (f) и выберем равнобедренный прямоугольный треугольник (ABC) так, чтобы его катеты (AB) и (AC) были направлены вдоль главных направлений преобразования (f). Обозначим через (A^{*}), (B^{*}) и (C^{*}) образы его вершин. Сделаем такое ортогональное преобразование (g), при котором (g(A)=A^{*}), а точки (g(B)) и (g(C)) лежат соответственно на лучах (A^{*}B^{*}) и (A^{*}C^{*}). (Этого легко добиться, как и в теореме 1, параллельным переносом, поворотом и осевой симметрией.)
Пусть (lambda=|A^{*}B^{*}|/|A^{*}g(B)|), a (mu=|A^{*}C^{*}|/|A^{*}g(C)|). Тогда сжатие (p_{1}) к прямой (A^{*}C^{*}) в отношении (lambda) переведет (g(B)) в (p_{1}g(B)=B^{*}) и не сдвинет точек (A^{*}) и (g(C)). Аналогично, сжатие (p_{2}) к прямой (A^{*}B^{*}) переведет (g(C)) в (p_{2}g(C)=C^{*}) и не сдвинет точек прямой (A^{*}B^{*}).
Это означает, что произведение (p_{2}p_{1}g) переводит точки (A), (B) и (C) в точки (A^{*}), (B^{*}) и (C^{*}) так же, как и заданное нам преобразование (f). Согласно ранее доказанному утверждению имеем (p_{2}p_{1}g=f), как и требовалось.
Источник
В этой статье я расскажу об одной необычной формуле, которая позволяет взглянуть под новым углом на аффинные преобразования, а особенно на обратные задачи, которые возникают в связи с этими преобразованиями. Обратными я буду называть задачи, требующие вычисления обратной матрицы: нахождение преобразования по точкам, решение системы линейных уравнений, преобразование координат при смене базиса и т.д. Сразу оговорюсь, что в статье не будет ни фундаментальных открытий, ни уменьшения алгоритмической сложности — я просто покажу симметричную и легко запоминающуюся формулу, с помощью которой можно решить неожиданно много ходовых задач. Для любителей математической строгости есть более формализованное изложение здесь [1] (ориентированно на студентов) и небольшой задачник вот здесь [2].
Аффинное преобразование обычно задается матрицей и вектором трансляции и действует на вектор‑аргумент по формуле
Впрочем, можно обойтись и без , если воспользоваться аугментированной матрицей и однородными координатами для аргумента (как хорошо известно пользователям OpenGL). Однако оказывается, кроме этих форм записи можно ещё использовать детерминант особой матрицы, в которой содержатся как координаты аргумента, так и параметры, задающие преобразование. Дело в том, что детерминант обладает свойством линейности по элементам любой своей строки или столбца и это позволяет использовать его для представления аффинных преобразований. Вот, собственно, как можно выразить действие аффинного преобразования на произвольный вектор :
Не спешите убегать в ужасе — во‑первых, здесь записано преобразование, действующее на пространствах произвольной размерности (отсюда так много всего), а во‑вторых, хотя формула и выглядит громоздко, но просто запоминается и используется. Для начала, я выделю логически связанные элементы рамками и цветом
Итак, мы видим, что действие любого аффинного преобразования на вектор можно представить как отношение двух детерминантов, при чем вектор‑аргумент входит только в верхний, а нижний — это просто константа, зависящая только от параметров.
Выделенный синим цветом вектор — это аргумент, вектор на который действует аффинное преобразование . Здесь и далее нижние индексы обозначают компоненту вектора. В верхней матрице компоненты занимают почти весь первый столбец, кроме них в этом столбце только ноль (сверху) и единица (снизу). Все остальные элементы в матрице — это векторы‑параметры (нумеруются верхним индексом, взятым в скобки, чтобы не перепутать со степенью) и единицы в последней строке. Параметры выделяют среди множества всех аффинных преобразований то, которое нам нужно. Удобство и красота формулы в том, что смысл этих параметров очень прост: они задают аффинное преобразование, которое переводит векторы в . Поэтому векторы , мы будем называть «входными» (в матрице они обведены прямоугольниками) — каждый из них покомпонентно записан в своём столбце, снизу дописывается единица. Сверху же записываются «выходные» параметры (выделены красным цветом) , но теперь уже не покомпонентно, а как цельная сущность.
Если кого‑то удивляет такая запись, то вспомните о векторном произведении
где была очень похожая структура и первую строку точно так же занимали векторы. При этом необязательно, чтобы размерности векторов и совпадали. Все детерминанты считаются как обычно и допускают обычные «трюки», например, к любому столбцу можно прибавить другой столбец.
С нижней матрицей всё предельно просто — она получается из верхней вычёркиванием первой строки и первого столбца. Недостаток (1) в том, что приходится считать детерминанты, однако если эту рутинную задачу переложить на компьютер, то окажется, что человеку останется лишь правильно заполнить матрицы числами из его задачи. При этом с помощью одной формулы можно решить довольно много распространенных на практике задач:
- нахождение аффинного преобразования по точкам;
- расчёт барицентрических координат;
- полилинейную интерполяцию;
- задачи на линейные преобразования (без трансляции):
- обращение матрицы;
- правило Крамера в одну формулу (нет, то что вы видели, это не в одну формулу);
- пересчет координат вектора при изменении базиса;
- интерполяцию полиномами Лагранжа.
Под действием неизвестного аффинного преобразования три точки на плоскости перешли в другие три точки. Найдем это аффинное преобразование.
Для определенности, пусть наши входные точки
а результатом действия преобразования стали точки
Найдем аффинное преобразование .
На самом деле, решать эту задачу можно по‑разному: с помощью системы линейных уравнений, барицентрических координат… но мы пойдем своим путем. Думаю, по использованным обозначениям Вы догадываетесь к чему я клоню: берём уравнение (1) для размерности и подставляем в качестве входных параметров, а — в качестве выходных
а дальше остается лишь посчитать детерминанты
Намётанный глаз легко обнаружит здесь поворот на и трансляцию на .
Когда формула применима?
Входные и выходные векторы могут иметь разную размерность — формула применима для аффинных преобразований, действующих на пространствах любой размерности. Впрочем, входных точек должно быть достаточно и они не должны «слипаться»: если аффинное преобразование действует из -мерного пространства — точки должны образовывать невырожденный симплекс из точки. Если это условие не выполнено, то однозначно восстановить преобразование невозможно (никаким методом вообще, не только этим) — формула предупредит об этом нулём в знаменателе.
Зачем восстанавливать аффинные преобразования программисту?
Часто нужно найти преобразование между двумя картинками (для расчёта положения камеры, например). Если у нас найдётся несколько надёжных особых точек (фич) на этих изображениях, ну или просто не хочется начинать сразу с ранзаков и борьбы с аутлаерами, то вполне можно использовать эту формулу.
Еще один пример — текстурирование. Вырезать треугольник из текстуры и натянуть на треугольник где‑нибудь на плоскости или в пространстве — типичная задача на применение аффинного преобразования к точкам из пространства текстуры, переводящее их в пространство, где «живут модели». И довольно часто нам легко указать каким точкам на текстуре соответствуют вершины треугольника модели, но вот установить куда переходят неугловые точки может потребовать некоторых размышлений. С этой же формулой достаточно просто вставить числа в правильные ячейки и будет вот такая красота.
Из того, с чем приходилось лично сталкиваться: нейросеть выдаёт координаты углов маркера и мы хотим «дополнить реальность» виртуальным объектом, который располагается на маркере.
Очевидно, при перемещении маркера объект должен повторять все его движения. И тут формула (1) как нельзя кстати — она нам поможет передвинуть объект вслед за маркером.
Или вот еще пример: нужно запрограммировать вращение различных объектов на сцене с помощью инструмента «гизмо». Для этого мы должны уметь вращать выбранную модель вокруг трех осей параллельных осям координат и проходящих через центр объекта. На картинке показан случай вращения модели вокруг оси параллельной .
В конечном итоге всё сводится к двумерной задаче о вращении вокруг произвольной точки. Давайте даже решим её для какого‑то простого случая, скажем, поворота на против часовой стрелки вокруг (общий случай решается так же, просто не хочется загромождать выкладки синусами‑косинусами). Конечно, можно пойти путём самурая и перемножить три матрицы (трансляция точки вращения в ноль, собственно вращение и трансляция назад), а можно и так — найти координаты любых трёх точек до и после вращения и воспользоваться формулой. Первая точка находится легко — мы и так знаем, что переходит в себя. Давайте рассмотрим точку на единичку правее, для неё верно . Ну и ещё одну на единичку ниже, тут очевидно, что . Дальше всё просто
Разложим верхний детерминант (1) по первой строке согласно правилу Лапласа. Ясно, что в результате мы получим некоторую взвешенную сумму векторов . Оказывается, что коэффициентами в этой сумме служат барицентрические координаты аргумента по отношению к симплексу, заданному (за доказательствами смотреть в [1]). Если нас интересуют только барицентрические координаты точки, можно схитрить и заполнить первую строку единичными ортами — после вычисления детерминантов мы получим вектор, чьи компоненты совпадают с барицентрическими координатами . Графически такое преобразование , переводящее точку в пространство её барицентрических координат, будет выглядеть следующим образом
Давайте опробуем этот «рецепт» на практике. Задача: найти барицентрические координаты точки по отношению к заданному треугольнику. Пусть для определённости это будет точка , а в качестве вершин треугольника возьмём
Дело за малым — взять (1) для , правильно расположить там данные задачи и посчитать детерминанты
Вот и решение: барицентрическими координатами по отношению к заданному треугольнику есть , и . В программировании расчёт барицентрических координат часто возникает в контексте проверки, находится ли точка внутри симплекса (тогда все барицентрические координаты больше ноля и меньше единицы), а также для различных интерполяций, о которых сейчас пойдёт речь.
Заметьте, формула (1) обладает приятной двойственностью: если разложить детерминант по первому столбцу — получим стандартную запись для аффинной функции, а если по первой строке — аффинную комбинацию выходных векторов.
Итак, мы обнаружили, что аффинное преобразование взвешивает выходные векторы с коэффициентами, равными барицентрическим координатам аргумента. Естественно воспользоваться этим свойством для полилинейной интерполяции.
Интерполяция цвета
Для примера, давайте просчитаем стандартный GL‑ный «привет мир» — раскрашенный треугольник. Конечно, OpenGL прекрасно умеет интерполировать цвета и тоже делает это с помощью барицентрических координат, но сегодня мы это сделаем сами.
Задача: в вершинах треугольника заданы цвета, произвести интерполяцию цвета внутри треугольника. Для определённости, пусть вершины нашего треугольника имеют координаты
Припишем им цвета: жёлтый, циан и маджента
Тройки чисел — это RGB‑компоненты цвета. Возьмём (1) и правильно расставим входные данные
Здесь компоненты указывают как закрасить точку в терминах RGB. Давайте посмотрим, что вышло.
Можно сказать, мы только что произвели аффинное преобразование двумерного пространства картинки в трехмерное пространство цветов (RGB).
Интерполяция нормалей (шейдинг Фонга)
Мы можем вкладывать самый разный смысл в векторы, которые мы интерполируем, в том числе это могут быть векторы нормалей. Более того, именно так и делается шейдинг Фонга (Phong shading), только после интерполяции векторы нужно нормировать. Для чего нужна такая интерполяция хорошо иллюстрирует следующее изображение (взятое из Википедии commons.wikimedia.org/w/index.php?curid=1556366).
Приводить расчёты, я думаю, уже не стоит — все детали рассмотрены в [2], а вот картинку с результатом я покажу.
Векторы на ней не единичные и для использования в шейдинге Фонга должны быть сначала отнормированы, к тому же, для наглядности, они направлены в очень разные стороны, что редко бывает на практике.
Рассмотрим еще один необычный пример применения аффинного преобразования.
Даны три точки
Найдём уравнение проходящей через них плоскости в виде . И сделаем это с помощью аффинных преобразований: известно ведь, что они переводят плоскости в плоскости. Для начала спроектируем все точки на плоскость , что несложно. А теперь установим аффинное преобразование, которое переводит проекции точек в изначальные трехмерные точки
и которое «подхватит» вместе с точками и всю плоскость да так, что после преобразования она будет проходить через интересующие нас точки.
Как обычно, мы лишь должны распределить числа по элементам матриц
Перепишем последнее выражение в привычном виде
и нарисуем что вышло.
Несмотря на всю практическую важность аффинных преобразований, чаще приходится иметь дело с линейными. Конечно, линейные преобразования — частный случай аффинных, оставляющие на месте точку . Это позволяет немного упростить формулу (ведь один из столбцов будет состоять почти из одних нулей и по нему можно разложить детерминант)
Как видим, из формулы пропала последняя строчка с единицами и один столбец. Этот результат вполне согласуется с нашими представлениями, что для задания линейного преобразования достаточно указать его действие на линейно независимых элементах.
Линейное преобразование по трем точкам
Давайте решим задачу, чтобы увидеть как всё работает. Задача: известно, что под действием некоторого линейного преобразования
Найдём это линейное преобразование.
Берём упрощённую формулу и ставим правильные числа на правильные места:
Готово!
Напомню, что матрица линейного преобразования
содержит в своих столбцах образы единичных векторов:
Итак, действуя матрицей на орты, мы получаем её столбцы. А что можно сказать об обратном преобразовании (допустим, оно существует)? Оно все делает «наоборот»:
Постойте‑ка, ведь мы только что нашли образы трёх точек под действием линейного преобразования — достаточно, чтоб восстановить само преобразование!
где , и .
Не будем себя ограничивать трехмерным пространством и перепишем предыдущую формулу в более общем виде
Как видим, надо приписать к матрице слева колонку с компонентами вектора‑аргумента, сверху — строчку с координатными векторами, а дальше дело только за умением брать детерминанты.
Задача на обратное преобразование
Давайте опробуем приведённый метод на практике. Задача: обратить матрицу
Воспользуемся (2) для
Сразу видно, что
Ещё со школы мы сталкиваемся с уравнениями вида
Если матрица невырожденная, то решение можно записать в виде
Хм… не в предыдущем ли разделе я видел такое же выражение, только вместо стояла другая буква? Воспользуемся им.
Это не что иное, как правило Крамера. В этом легко убедиться, разложив детерминант по первой строке: вычисление как раз предполагает, что мы вычеркнем столбец с , а с ним и ‑й столбец матрицы . Теперь если переставить столбец на место удалённого, то мы как раз и получим правило «вставить столбец на место ‑го столбца и найти детерминант». И да, со знаками всё хорошо: одни мы генерируем при разложении по строке, а другие при перестановке — в результате они друг друга компенсируют.
Присмотревшись к полученному уравнению, можно заметить его схожесть с уравнением для нахождения барицентрических координат: решение системы линейных уравнений— это нахождение барицентрических координат точки по отношению к симплексу, одна из вершин которого , а остальные задаются столбцами матрицы .
Решение системы линейных уравнений
Решим систему линейных уравнений
В матричной форме она выглядит так
Используем полученную формулу
откуда ответ , и .
Предположим, что мы выбрали новый базис (перешли к другой системе координат). Известно, что новые координаты векторов выражаются через старые линейно. Поэтому неудивительно, что мы можем использовать наш инструментарий для смены базиса. Как это сделать, я покажу на примере.
Итак, пускай мы перешли от стандартного базиса к базису, состоящему из векторов
В старом базисе задан вектор . Найдём координаты этого вектора в новом базисе. В новой координатной системе векторы нового базиса станут ортами и будут иметь координаты
здесь и далее штрихи возле столбцов означают, что координаты в них относятся к новому базису. Несложно догадаться, что линейное преобразование, которое переводит
также нужным образом преобразует координаты нашего вектора. Осталось только применить формулу
Решение задачи привычным образом требует обращения матрицы (которое, впрочем, также в основном состоит из вычисления детерминантов) и умножения
Мы лишь упаковали эти шаги в одну формулу.
Эффективность формулы в решении обратных задач объясняется тем, что выполняется следующее равенство (доказательство есть в [1])
Таким образом, формула прячет в себе обратную матрицу и умножение на еще одну матрицу в придачу. Это выражение и есть стандартное решение задачи нахождения линейного преобразования по точкам. Заметьте, что делая вторую матрицу в произведении единичной, мы получим просто обратную матрицу. С ее помощью решается система линейных уравнений и задачи, которые к ней сводятся: нахождение барицентрических координат, интерполяция полиномами Лагранжа, и т.д. Однако, представление в виде произведения двух матриц, не даёт нам получить те самые «два взгляда», связанные с разложением по первой строке и по первому столбцу.
Напомню, что интерполяция Лагранжа — это нахождение полинома наименьшей степени проходящего через точки , , , . Не то чтобы это была распространённая в программистской практике задача, но всё равно давайте ее рассмотрим.
Как связаны полиномы и линейные преобразования?
Дело в том, что полином
можно рассматривать как линейное преобразование, которое отображает вектор в . Значит, задача интерполяции точек , , , сводится к нахождению такого линейного преобразования, что
а это мы делать умеем. Подставим правильные буквы в правильные ячейки и получим формулу
Доказательство, что это будет именно полином Лагранжа (а не чей‑то другой), можно посмотреть в [1]. Кстати, выражение в знаменателе — это определитель Вандермонда. Зная это и разложив детерминант в числителе по первой строке, придем к более привычной формуле для полинома Лагранжа.
Задача на полином Лагранжа
Сложно ли этим пользоваться? Давайте попробуем силы на задаче: найти полином Лагранжа, проходящий через точки , и .
Подставим эти точки в формулу
На графике всё будет выглядеть так.
Свойства полинома Лагранжа
Разложив верхний детерминант по первой строке и первому столбцу, мы взглянем на полином Лагранжа с двух разных сторон. В первом случае получим классическую формулу из Википедии, а во втором — запись полинома в виде суммы одночленов , где
А ещё мы теперь можем сравнительно просто до?