Аффинные преобразования на плоскости код. Аффинное преобразование и его матричное представление

Глава I.Понятие о геометрическом преобразовании

1.1 Что такое геометрическое преобразование?

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

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

Пример. Симметрия относительно прямой l является геометрическим преобразованием. Правило, позволяющее по точке A найти соответствующую ей точку А", в этом случае заключается в следующем: из точки А опускается перпендикуляр АР на прямую lи на его продолжении за точку Р откладывается отрезок РА"=АР.

Сложение геометрических преобразований

Предположим, что мы рассматриваем два геометрических преобразования, одно из которых называем „первым", а другое - „вторым". Возьмем на плоскости произвольную точку А и обозначим через А" ту точку, в которую переходит А при первом преобразовании. В свою очередь точка А" переводится вторым преобразованием в некоторую новую точку А". Иначе говоря, точка А" получается из точки А при помощи последовательного применения двух преобразований - сначала первого, а затем второго.

Результат последовательного выполнения взятых двух преобразований также представляет собой геометрическое преобразование: оно переводит точку А в точку А". Это „результирующее" преобразование называется суммой первого и второго рассмотренных преобразований.

Пусть на плоскости задана какая-либо фигура F. Первое преобразование переводит ее в некоторую фигуру F" . Вторым преобразованием эта фигура F" переводится в некоторую новую фигуру F"". Сумма же первого и второго преобразований сразу переводит фигуру Fв фигуру F".

Пример. Пусть первое преобразование представляет собой симметрию относительно точки О1 а второе преобразование - симметрию относительно другой точки О2. Найдем сумму этих двух преобразований.

Пусть А - произвольная точка плоскости. Предположим сначала, что точка A не лежит на прямой O1O2. Обозначим через А" точку, симметричную точке А относительно О1, а через A" - точку, симметричную точке A" относительно О2 . Так как О1O2 - средняя линия треугольника АА"А"" то отрезок АА" параллелен отрезку О1O2 и имеет вдвое большую длину. Направление от точки А к точке А" совпадает с направлением от точки

О1 к точке О2. Обозначим теперь через МNтакой вектор, что отрезки MNи O1 O2 параллельны, отрезок МNв два раза длиннее отрезка O1О2 и лучи МNи O1O2 имеют одно и то же направление. Тогда АА" = МN, т. е. точка А" получается из точки А параллельным переносом на вектор МN.

То же справедливо и для точки, лежащей на прямой O1О2.

Окончательно мы получаем: сумма симметрии относительно точки O1 и симметрии относительно точки O2 представляет собой параллельный, перенос.

1.2 Движения

Осевая симметрия, поворот (в частности, центральная симметрия) и параллельный перенос имеют то общее, что каждое из этих преобразований переводит любую фигуру F на плоскости в равную ей фигуру F" . Преобразования, обладающие этим свойством, называются движениями. Гомотетия представляет собой пример преобразования, не являющегося движением. Действительно, каждое движение переводит любую фигуру в равную ей фигуру, т. е. изменяет лишь положение фигур на плоскости; гомотетия же изменяет и размеры фигур.

Роль движений в геометрии

Движения играют в геометрии чрезвычайно важную роль. Они не изменяют ни формы, ни размеров фигур, меняя лишь расположение фигуры. Но фигуры, отличающиеся лишь своим расположением на плоскости, с точки зрения геометрии совершенно одинаковы. Именно поэтому их и называют в геометрии «равными фигурами». Ни одно свойство геометрической фигуры не отличается от соответствующего свойства равной ей фигуры. Так, например, равные треугольники имеют не только одинаковые стороны, но и одинаковые углы, медианы, биссектрисы, площади, радиусы вписанной и описанной окружностей и так далее.

На уроках геометрии мы всегда считали равные фигуры (т. е. такие, которые можно совместить при помощи движения) одинаковыми или неразличимыми. Такие фигуры часто принимают за одну и ту же фигуру. Именно поэтому мы можем сказать, что, например, задача построения треугольника по двум сторонам а, bи заключенному между ними углу С имеет только одно решение. На самом деле, конечно, треугольников, имеющих данные стороны а и b и заключенный между ними угол С данной величины, можно найти бесконечно много. Однако все эти треугольники одинаковы, равны, поэтому их можно принять за «один» треугольник.

Таким образом, геометрия изучает те свойства фигур, которые одинаковы у равных фигур. Такие свойства можно назвать «геометрическими свойствами». Другими словами: геометрия изучает свойства фигур, не зависящие от их расположения. Но фигуры, отличающиеся только расположением (равные фигуры), - это те, которые можно совместить с помощью движения. Поэтому мы приходим к следующему определению предмета геометрии; геометрия изучает те свойства фигур, которые сохраняются при движениях.

Движения в геометрии и физике

Итак, понятие движения играет в геометрии первостепенную роль. Движения («наложения») использовались в VI классе для определения равных фигур, для доказательства признаков равенства треугольников; понятие движения, как мы видели выше, позволяет также дать описание предмета геометрии.

Между тем в определениях понятия равенства фигур и понятия движения имеется пробел. В самом деле, равные фигуры определялись (в VI классе) как такие фигуры, которые могут быть совмещены наложением (т. е. движением). Движения же были определены выше как такие преобразования, которые переводят два многоугольника F1 и Fтаковы, что существует многоугольник F", гомотетичный Fи равный F1 , то углы многоугольника Fсоответственно равны углам многоугольника F" и стороны многоугольника Fсоответственно, пропорциональны сторонам многоугольника F". Но у многоугольника F те же самые углы и стороны, что и у равного ему многоугольника F1. Следовательно, многоугольники F1и F подобны в том смысле, в каком это понималось в курсе геометрии VIII класса.

Обратно, пусть многоугольники F1 и F таковы, что их углы соответственно равны и стороны соответственно пропорциональны. Отношение сторон многоугольника F1 к соответствующим сторонам многоугольника Fобозначим через k. Далее, обозначим через F" многоугольник, получающийся из Fгомотетией с коэффициентом k (и каким угодно центром гомотетии. В таком случае в силу теоремы многоугольники F" и F1 будут иметь соответственно равные стороны и углы, т. е. эти многоугольники будут равны. Поэтому многоугольники F1 и Fбудут подобны и в смысле приведенного здесь определения подобия.

Глава II.Аффинные преобразования

2.1 Аффинные преобразования плоскости

Аффинным преобразованием α называется такое преобразование плоскости, которое всякую прямую переводит в прямую и сохраняет отношение, в котором точка делит отрезок.

На рис.1: L"= α(L), A"=α(A), B"=α(B), C"=α(C),

|

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

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

Пусть даны плоскости: w и w1 прямая l(направление проектирования), не параллельная ни одной из этих плоскостей (рис.2). Точка Аєw называется проекцией точки А1єw1, если АА1||l , то прямая АА1 называется проектирующей прямой. Параллельное проектирование представляет собой отображение плоскости w1 на w.

Отметим следующие свойства параллельного проектирования.

1) Образом всякой прямой а1 является прямая.

В самом деле, прямые, проектирующие точки прямой а1, образуют плоскость (она проходит через а1 параллельно l), которая при пересечении с wдает образ прямой а1 – прямую а(рис.2).

2) Отношение, в котором точка делит отрезок, сохраняется, т.е.

(рис.2)

Сразу следует из теоремы о пересечении сторон угла параллельными прямыми.

Перейдем непосредственно к построению примера аффинного преобразования.

Возьмем два экземпляра плоскости w и один из них переместим в другое положение w1(рис.3). Новое положение какой-либо точки Аєwобозначим А1єw1. Теперь плоскость w1 спроектируем в каком-нибудь положении на w, проекцию точки А1 обозначим А".

Получилось преобразование плоскости w на себя, при котором

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

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

Поворот .

Рассмотрим поворот произвольной точки A вокруг начала координат на угол(Рис. 6).

Элементарное аффинное преобразование – поворот на угол .

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

(5)

Удобно координаты точки объединить в виде 2-х мерного вектора (столбика). Тогда переход точки A в положение точкиA

(6)

В этих обозначениях поворот можно выразить в виде матричного умножения.

(7)

Здесь R – матрица поворота (Rotation- вращение). Структуру этой матрицы получаем из уравнений (5).

(8)

Растяжение-сжатие, масштабирование.

Рассмотрим операцию растяжения-сжатия вдоль координатных осей с коэффициентами растяжения k 1 ,k 2 . Часто эту операцию называют масштабированием (Scaling- масштабирование). Для примера покажем (Рис. 7) растяжение отрезка с коэффициентами растяжения равными
.

Элементарное аффинное преобразование – растяжение с коэффициентами
.

Растяжение описывается следующим аффинным преобразованием.

(9)

Преобразование (9) можно выразить в виде матричного умножения.

(10)

Здесь S – матрица масштабирования. Структуру этой матрицы получаем из уравнений (9).

(11)

Отражение.

Рассмотрим операцию отражения относительно координатных осей. Для примера покажем (Рис. 8) отражение относительно оси x .

Элементарное аффинное преобразование – отражение относительно оси Ox.

Отражение описывается следующим аффинным преобразованием.

(12)

Преобразование (12) можно выразить в виде матричного умножения.

(13)

Здесь M – матрица отражения (Mirror– зеркало, отражение). Структуру этой матрицы получаем из уравнений (12).

(14)

Аналогично находим матрицу отражения относительно оси y .

(15)

Перенос.

Рассмотрим операцию переноса на вектор трансляции
. При этой операции любой объект перемещается без искажения, и любая сторона остается параллельной самой себе. Для примера покажем на рисунке 9 перенос отрезка.

Элементарное аффинное преобразование – перенос на вектор трансляции t .

Перенос описывается следующим аффинным преобразованием.

(16)

Преобразование (16) нам хотелось бы выразить в виде матричного умножения тип.

(17)

Здесь T – должна быть матрицей трансляции (Translation– трансляция, перенос). Однако невозможно построить матрицуT размерностью 22, чтобы одновременно удовлетворялись уравнения (16) и (17).

И все же, такую матрицу можно создать, если формально рассматривать аффинные 2D-преобразования в 3-х мерном пространстве. Для этого надо перейти к однородным координатам.

Однородные координаты.

Понятие однородных координат пришло к нам из проективной геометрии. Пусть точка A лежит на плоскости и имеет координаты (x ,y ). Тогдаоднородными координатами этой точки называется любая тройка чиселx 1 ,x 2 ,x 3 , связанных с заданными числамиx иy следующими соотношениями.

(18)

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

Таким образом, произвольной точке A (x ,y ) плоскости ставится в соответствие точкаA (x ,y , 1) в пространстве. По сути дела мы рассматриваем аффинные преобразования в плоскостиz = 1 , как это показано на рисунке 10.

Аффинное преобразование в однородных координатах.

Координаты точек лежащих в плоскости z = 1 объединяем в виде 3-х мерных векторов. Переход точкиA в положение точкиA * можно представить, как преобразование векторов.

(20)

В этих обозначениях общее аффинное преобразование (1) можно выразить в виде матричного умножения.

(21)

Здесь матрица P размерности 33 является матрицей общего аффинного преобразования (1) и имеет вид.

(22)

Отметим важный момент , связанный с однородными координатами. Переход к трехмерным векторам и матрицам (20, 21, 22) можно было выполнить совершенно формально, не привязываясь к реальному трехмерному пространству (x,y,z). Этот подход позволяет для 3D-аффинных преобразований ввести однородные координаты и производить матричные умножения в 4-х мерном векторном пространстве.

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

Матрица поворота R в однородных координатах будет иметь следующий вид.

(23)

Матрица растяжения S изменится следующим образом.

(24)

Матрицы отражения M относительно координатных осей будут иметь вид.

(25)

Матрица переноса T на вектор трансляциив однородных координатах будет иметь следующий вид.

(26)

Тема этого выпуска задание аффинного преобразования в матричной форме. Эта тема, по сути, является обобщением всего, что было сказано ранее.

Определение. Преобразование плоскости называется аффинным , если

• оно взаимно однозначно;
• образом любой прямой является прямая.

Преобразование называется взаимно однозначным , если

• разные точки переходят в разные;
• в каждую точку переходит какая-то точка.

Однородные координаты

Если рассмотреть параллельный перенос, то оказывается, что для его задания матрицы 2x2 уже недостаточно. Но его можно задать с помощью матрицы размера 3x3. Появляется вопрос, откуда взять третью координату у двумерной точки?

Определение. Однородные координаты - координаты, обладающие тем свойством, что определяемый ими объект не меняется при умножении всех координат на одно и то же число.

Однородными координатами вектора (х, у) является тройка чисел (x", y", h) , где х = х" / h, у = y"/h, а h - некоторое вещественное число (случай, когда h = 0 является особым).

Прим. Данные координаты не позволяют однозначно задать точку плоскости. Например, (1 , 1, 1) и (2, 2, 2) задают одну и ту же точку (1, 1) . Предлагается взять набор (x, y, 1) , который будет описывать все точки плоскости.

Матрица преобразования для однородных координат имеет размер 3х3. Рассмотрим некоторые преобразования в однородных координатах.

Сжатие/растяжение

Это преобразование умножает соответствующие координаты точек на коэффициенты масштабирования по осям: (x, y ) -> (a x * x , a y * y ) . Матрица преобразования запишется следующим образом:

[ a x 0 0 ]

Где a x – растяжение по оси x ,

a y – растяжение по оси y .

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

Поворот

Матрица поворота 2x2 была подробно разобрана ранее. Теперь она дополняется строкой и столбцом:

[ -sin(phi)cos(phi) 0]

Прим. При угле phi = п эта матрица задает центральную симметрию относительно начала координат, которая является частным случаем поворота. Можно заметить, что такую симметрию можно задать с помощью преобразования сжатия/растяжения (допуская отрицательные коэффициенты масштабирования).

Параллельный перенос

Исходный вектор (x, y ) переходит в (x + t x, y + t y ) . Матрица преобразования запишется следующим образом:

[ 1 0 0]

[ t x t y 1]

Отражение

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

[-10 0]

отражение относительно оси x

отражение относительно оси y

Общий вид аффинного преобразования

Матрица 3x3, последний столбец которой равен (0 0 1) T , задает аффинное преобразование плоскости:

[ * * 0]

[ * * 0]

[ * * 1]

По одному из свойств, аффинное преобразование можно записать в виде:

f (x ) = x * R + t ,

где R – обратимая матрица 2 x2, а t – произвольный вектор. В однородных координатах это запишется следующим образом:

[ R 1,1 R 1,2 0 ]

[ R 2,1 R 2,2 0 ]

[ t x t y 1 ]

Если умножить вектор-строку на эту матрицу получаем результат преобразования:

[ xy1 ] *[ R 1,1 R 1,2 0 ]

[ R 2,1 R 2,2 0 ]

[ t x t y 1 ]

[ x’y’1 ]+[ t x t y 1 ]

При этом [ x ’ y ’ ]= R *[ x y ]

Прим. Любопытный читатель уже задал себе вопрос: в чем смысл определителя матрицы R? При аффинном преобразовании площади всех фигур изменяются в | R|. (Можно строго доказать это с точки зрения математики, но здесь этот факт приводится без доказательства.)

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

Матрица R определяет новый базис плоскости. Т.е. вектор (1, 0) переходит в (R 1,1, R 1,2 ), вектор (0, 1) переходит в (R 2,1, R 2,2 ). Новый базис это строки матрицы R .

Пример.

При отражении относительно оси y , базисный вектор по оси ординат сохраняется, а по оси абсцисс переходит в (-1, 0) . Т.о. матрица R будет выглядеть следующим образом:

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

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

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

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

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

• блок, в котором происходит создание окна и обрабатываются сообщения операционной системы, реализован в файл emain . cpp
• графический движок, выполняющий отрисовку изображения, класс Engine
• прослойка, необходимая для преобразования логических координат в оконные и обратно, класс Viewport
• объект, отвечающий за реакцию на действия пользователя, класс Action

В приведенном примере реализованы эти функциональные блоки, с подробными комментариями.

Аффинное преобразование это такое преобразование, которое сохраняет параллельность линий, но не обязательно углы или длины.
В компьютерной графике все, что относится к двумерному случаю, принято обозначать символом 2D (2-dimension). Допустим, на плоскости введена прямолинейная координатная система. Тогда каждой точке М ставится в соответствие упорядоченная пара чисел (х, у) ее координат (рис. 1).

Указанные выше формулы можно рассматривать двояко: либо сохраняется точка и изменяется координатная система в этом случае произвольная точка М остается той же, изменяются лишь ее координаты (х, у) (х*, у*) , либо изменяется точка и сохраняется координатная система в этом случае формулы задают отображение, переводящее произвольную точку М(х, у) в точку М*(х*, у*), координаты которой определены в той же координатной системе. В дальнейшем будем интерпретировать формулы, как правило, что в заданной системе прямолинейных координат преобразуются точки плоскости.
В аффинных преобразованиях плоскости особую роль играют несколько важных частных случаев, имеющих хорошо прослеживаемые геометрические характеристики. При исследовании геометрического смысла числовых коэффициентов в формулах для этих случаев удобно считать, что заданная система координат является прямоугольной декартовой.
Наиболее часто применяются следующие приемы компьютерной графики: перенос, масштабирование, поворот, отражение. Алгебраические выражения и рисунки, поясняющие данные преобразования сведем в табл.1.

Аффинные преобразования на плоскости

Под переносом понимается смещение примитивов вывода на один и тот же вектор.
Масштабирование это увеличение или уменьшение всего изображения либо его части. При масштабировании координаты точек изображения умножаются на некоторое число.
Под поворотом понимается вращение примитивов вывода вокруг заданной оси. (В плоскости чертежа вращение происходит вокруг точки.)
Под отражением понимают получение зеркального отображения изображения относительно одной из осей (например X).
Выбор этих четырех частных случаев определяется двумя обстоятельствами:
1. Каждое из приведенных выше преобразований имеет простой и наглядный геометрический смысл (геометрическим смыслом наделены и постоянные числа, входящие в приведенные формулы).
2. Как доказывается в курсе аналитической геометрии, любое преобразование вида (*) всегда можно представить как последовательное исполнение (суперпозицию) простейших преобразований вида А, Б, В и Г (или части этих преобразований).
Таким образом, справедливо следующее важное свойство аффинных преобразований плоскости: любое отображение вида (*) можно описать при помощи отображений, задаваемых формулами А, Б, В и Г.
Для эффективного использования этих известных формул в задачах компьютерной графики более удобной является их матричная запись.
Для объединения этих преобразований вводят однородные координаты. Однородными координатами точки называется любая тройка одновременно не равных нулю чисел x1 , x2 , x3 , связанных с заданными числами x и y следующими соотношениями:

Тогда точка M(х, у) записывается как M(hX, hY, h), где h 0 является масштабным множителем. Двумерные декартовы координаты могут быть найдены как

В проективной геометрии эти координаты вводятся для устранения неопределенностей, возникающих при задании бесконечноудаленных (несобственных) элементов. Однородные координаты можно интерпретировать как вложение промасштабированной с коэффициентом h плоскости в плоскость Z= h в трехмерном пространстве.
Точки в однородных координатах записываются трехэлементными вектор-строками. Матрицы преобразования должны иметь размер 3х3.
При помощи троек однородных координат и матриц третьего порядка можно описать любое аффинное преобразование плоскости.
В самом деле, считая h = 1, сравним две записи: помеченную символом (*) и нижеследующую, матричную:

Теперь можно использовать композиции преобразований, применяя одно результирующее вместо ряда преобразований, следующих друг за другом. Можно, например, сложную задачу разбить на ряд простых. Поворот точки А около произвольной точки В можно разбить на три задачи:
перенос, при котором В= 0 (где 0-начало координат);
поворот;
обратный перенос, при котором точка В возвращается на место и т. д.
Композиция наиболее общего вида из операций Т, D, R, M имеет матрицу:

Верхняя часть размером 2х2 - объединенная матрица поворота и масштабирования, a tx и ty описывают суммарный перенос.
К изложенным фундаментальным преобразованиям сводятся следующие:
прокручивание перемещение окна на поверхности визуализации (если перемещение ограничено только направлениями вверх и вниз, то оно называется вертикальным прокручиванием);

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