3.4. Аффинные преобразования

Линейное преобразование вместе с последующим преобразованием сдвига составляют аффинное преобразование пространства . Несмотря на то, что в примерах мы ограничимся преобразованиями на плоскости, то есть из все результаты легко обобщаются на случай -мерного пространства.

Отображение L называется линейным преобразованием пространства в пространство если:

для всех и произвольных скаляров Пример линейного преобразования плоскости:

Матричная запись этого преобразования:

служит примером следующей теоремы.

Теорема 3.4.4. Пусть L — линейное преобразование из Тогда существует такая матрица А размера , что:

Доказательство. Рассмотрим стандартный базис в

и вектор

Тогда

и с использованием условия линейности (3.12) получим:

Векторы представляют собой столбцы размера так как область значений L есть пространство Составим из этих столбцов -матрицу А. Раскрывая матричное произведение:

убеждаемся в том, что

Рис. 3.7. Сдвиг

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

которая пробегает отрезок от х до у. Пусть L — линейное преобразование. По определению линейного преобразования:

Следовательно, L преобразует отрезок в отрезок Более того, левая часть оригинала отображается в левую часть изображения Суммируя все это, заключаем, что линейное преобразование плоскости L отображает треугольную область с вершинами х, у и z на треугольную область с вершинами причем внутренность первого треугольника отображается на внутренность второго. Другие свойства линейного преобразования вынесены в упражнения.

Отображение Т называется преобразованием сдвига пространства (рис. 3.7), если:

где а — постоянный вектор. Эффект применения Т к произвольной кофигурации из заключается в сдвиге всей конфигурации на вектор а.

Рис. 3.8. Аффинные преобразования для ковра Серпинского

Таким образом, любое аффинное преобразование Т пространства можно представить в матричной форме:

В случае имеем:

Мы будем пользоваться аффинными преобразованиями при построении фракталов с помощью алгоритмов систем итерированных функций (глава 4). Аффинные преобразования для ковра Серпинского показаны на рис. 3.8. В матричной форме они имеют следующий вид:

Изометрия.

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

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

Напомним, что скалярное произведение двух векторов задается следующим образом

и что ненулевые векторы х и у перпендикулярны, или ортогональны, тогда и только тогда, когда Набор из попарно ортогональных векторов единичной длины называется ортонормированным базисом. Ясно, что столбцы квадратной матрицы Q порядка образуют ортонормированный базис, если:

где I — единичная матрица порядка при при . Матрица Q называется ортогональной матрицей.

Лемма 3.4.2. Если 0 — неподвижная точка изометрии Т пространства то Т сохраняет скалярное произведение:

Доказательство. Из определения изометрии и выражения (3.2) следует:

Теорема 3.4.5. Изометрия является аффинным преобразованием и может быть представлена в виде:

где Q — ортогональная матрица, b — вектор-столбец.

Доказательство. Положим . Тогда — тоже изометрия, причем По лемме сохраняет скалярное произведение, а следовательно и норму.

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

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

Пусть Тогда можно записать в виде:

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

где Q — ортогональная матрица, составленная из столбцов . Таким образом, Т — аффинное преобразование:

Упр. 5 в конце этого параграфа посвящено различным видам изометрии плоскости

Преобразование подобия.

Обобщением изометрии является преобразование подобия, при помощи которого могут быть получены многие фракталы (глава 4). Преобразование называется преобразованием подобия с коэффициентом подобия , если:

Следующая теорема устанавливает общий вид преобразования подобия пространства

Теорема 3.4.6. Преобразование подобия с коэффициентом подобия является аффинным преобразованием и может быть представлено в виде:

где Q — ортогональная матрица, b — вектор-столбец.

Доказательство. Пусть . Видно, что Т — изометрия, причем . По теореме можно записать в виде:

где Q — ортогональная матрица. Следовательно,

Упр. 6 в конце этого параграфа посвящено различным видам преобразования подобия плоскости .

Комплексные числа.

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

задаются формулами:

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

Векторное пространство можно рассматривать как множество комплексных чисел:

установив взаимно однозначное соответствие:

Такие операции над векторами, как сложение и умножение на скаляр, заменяются сложением и умножением соответствующих комплексных чисел.

Очевидный пример аффинного преобразования, записанного при помощи комплексных чисел:

Это же преобразование в матричной форме:

Как следует из выражения (3.19), далеко не все аффинные преобразования можно представить с помощью (3.18). Произвольное аффинное преобразование в комлексной записи имеет вид:

где a, b и с — комплексные постоянные. Представлению (3.20) и его свойствам посвящено упр. 4 в конце этого параграфа.

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

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

Здесь — модуль, или абсолютное значение

Угол в называется аргументом z. Это угол (с точностью до ) между положительным направлением оси и вектором, соединяющим начало координат с точкой Произведение двух комплексных чисел выражается следующей формулой:

то есть модули перемножаются, а аргументы складываются. Таким образом, если мы положим , где в произвольный угол, , то (3.18) будет сжимающим аффинным отображением с коэффициентом сжатия . Геометрически действие этого преобразования на некоторую фигуру можно представить в виде последовательности шагов:

1. Повернуть фигуру относительно начала координат на угол 9.

2. Сжать фигуру к началу координат в раз.

3. Сдвинуть фигуру на радиус-вектор b.

Три преобразования для ковра Серпинского можно записать в комплексной форме следующим образом:

Аффинные коэффициенты.

В определении (3.15) произвольного аффинного преобразования плоскости имеется шесть параметров, или степеней свободы. Разумно предположить, что мы всегда в состоянии определить единственным образом все параметры аффинного преобразования, которое отображает три несовпадающие точки (шесть координат) на три точки

Рис. 3.9. Мировые и экранные координаты

И это действительно так: коэффициенты определяются из системы уравнений:

Пример дается в конце этого параграфа.

Замена координат.

При реализации на компьютере систем итерированных функций (глава 4) для задания координат пикселов принято использовать переменные и j. Обычно . Однако изначально координаты могут быть заданы вещественными числами (как в примере с ковром Серпинского), вроде или . Последние мы будем называть мировыми координатами, в отличие от экранных координат i, j (рис. 3.9). Если:

то нетрудно убедиться, что соответствие между координатами устанавливается формулой:

где (упр. 7 в конце этого параграфа). В более компактной записи:

где

Далее, остается вопрос, как записать аффинное или любое другое преобразование Т в экранных координатах. Пусть определяется формулой (3.21). Из диаграммы

видно, что новое преобразование Т задается формулой:

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

Теорема 3.4.7. Пусть — замена переменных для перехода от мировых координату к экранным, — аффинное преобразование в мировых координатах. Тогда преобразование Т в экранных координатах имеет вид:

где

Доказательство. Имеем:

где

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

Алгоритм

Назначение: для аффинного отображения Т, заданного в мировых координатах, вычисляет эквивалентное представление в экранных координатах. Отображение Т имеет вид:

Вход:

(аффинные коэффициенты)

(мировые координаты)

(экранные координаты)

Выход:

(новые аффинные коэффициенты)

Шаги:

Рис. 3.10. Отображение треугольника в треугольник

Пример. Рассмотрим пример аффинного преобразования, заданного тремя точками (рис. 3.10):

Матричная запись этого преобразования:

Пусть мировые координаты изменяются в пределах Задача состоит в том, чтобы отобразить квадрат, заданный в мировых координатах, в окно где

Рис. 3.11. Пример перехода к экранным координатам

Мы намеренно выбрали (вместо так как обычно начало отсчета (0,0) в экранной системе координат помещается в левый верхний угол.

Преобразование из мировых координат в экранные дается формулой:

В этой новой системе координат соответствие между точками запишется так (рис. 3.11):

Преобразование (3.22) в новых координатах примет следующий вид: