Решение аффинных задач

 

 

Введение.  Постановка задачи.

     Название темы  дипломной работы предусматривает  предварительное рассмотрение нескольких  основных положений того  материала, который будет излагаться в  последующих главах.  Поскольку  речь идет об одной из разновидностей  систем координат – аффинной – дадим общее определение системы координат. Системой координат называется совокупность одной, двух, трех или более пересекающихся координатных осей, с точкой их пересечения (началом координат)  и единичными отрезками на каждой из осей. Любая точка в системе координат определяется упорядоченным набором нескольких чисел – координат. В данной невырожденной системе координат  каждой точке  будет соответствовать  только один набор координат. Если в качестве координатных осей берутся прямые, перпендикулярные друг другу, то система координат называется прямоугольной или ортогональной. Прямоугольная система координат, в которой единицы измерения по всем осям равны друг другу, называется ортонормированной или декартовой системой координат. Декартовая система координат является наиболее простой и наиболее используемой системой. Любая из ныне существующих систем координат имеет свои недостатки и достоинства. В частности, аппарат декартовых координат невозможно использовать для решения некоторых задач по различным причинам. В частности укажем на некоторые из них:

1. В декартовых координатах невозможно описать бесконечно удаленную точку.
2. В декартовых координатах при поведении алгебраических операций невозможно провести различие между точками и векторами в пространстве.
3. Аппарат декартовых координат не позволяет применять унифицированный механизм работы с матрицами для выражения преобразований точек.

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

Аффинный [лат.affinis] — смежный соседний. Аффинская геометрия — раздел математики, изучающий величины и геометрические объекты, остающиеся неизменными при аффинных преобразованиях.

Преобразования возможно описать только при условии существования координат.

       Аффинная система  координат (косоугольная система координат) — прямолинейная система координат в аффинном пространстве.

 

          

Рис.1 .Точка М на аффинной плоскости.

     В n-мерном пространстве она  задаётся упорядоченной системой линейно независимых векторов , ,… выходящих из одной точки O. Аффинными координатами точки называют такие числа , что

     Tочку О и систему векторов называют репером или аффинным базисом; прямые, проходящие через вектора координатными осями. На аффинной плоскости n=2 координату называют абсциссой, а — ординатой точки М. В пространстве же координаты точки называют её абсциссой, ординатой и аппликатой. Аналогичным образом именуют и координатные оси. Поскольку окружающий мир воспринимается нами в трехмерном пространстве, то декартовая система координат и аффинная система координат воспринимается наблюдателями без особых затруднений.  Но в настоящее время возникло новое направление в исследовании геометрических и других разнообразных свойств материальных объектов, которые описываются дробной размерностью пространства. Речь идет о фрактальных объектах. Поскольку это направление исследований имеет свою специфику, то данная работа посвящена классическим геометрическим методам изучения объектов.  

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

 

Глава 1. Аффинные преобразования. Аффинные преобразования плоскости       Первоначально рассмотрим аффинное преобразование системы координат в пространстве. Пусть в пространстве заданы две системы координат и . Обычно первая система координат  называется "старой", а вторая — "новой". Старый и новый базисы представим в виде символических матриц-строк: , .      Предположим, что перед нами поставлены  следующие задачи: 1). Необходимо найти координаты  вектора в новом базисе по  известным координатам этого  же вектора в старом базисе; 2). Необходимо найти координаты  точки в новом системе координат, если известны её координаты в старой системе координат       Рассмотрим  преобразование координат произвольного  не нулевого вектора при замене  базиса. Предположим, что нам известны  координаты векторов нового базиса, которые определяются по известному  старому базису                                                                              (1)         Если записать  по столбцам   соответствующие  координаты векторов нового базиса относительно старого базиса, то можно составить матрицу:                                                                                       (2)        Квадратная матрица, составленная из координатных столбцов векторов нового базиса в старом базисе называется матрицей  преобразования базиса.      Используя  матрицу  преобразования базиса  формулы (1) можно записать в виде:       (3) Умножение  матрицы-строки на матрицу преобразования в (3) производится по правилам умножения матриц.      Пусть вектор  в старом базисе имеет координаты , а в новом базисе — координаты , т.е.                                    , где - координатные столбцы вектора .       Подставляя  в правую часть последнего  равенства выражение (3), получаем                                 (4)      Последнее выражение  устанавливает связь координат вектора в разных базисах: координатный столбец вектора в старом базисе получается в результате умножения матрицы преобразования  на координатный столбец вектора в новом базисе.        С помощью  последующего выражения находим связь координат вектора на плоскости при замене базиса:               (5) где   —  координатные столбцы вектора относительно базисов и    на плоскости соответственно,   —   матрица перехода от базиса к базису .       Рассмотрим  матрицу перехода от одного  базиса к другому. Эта матрица  обладает следующими свойствами:      1. Пусть в пространстве имеются три базиса и  известны матрицы перехода: от базиса к базису ; от к ; от к .  В этом случае матрица композиции преобразований базисов   и равна произведению матриц преобразований базисов:                                (6)       2. Если -матрица перехода от базиса к базису , то матрица обратимая (невырожденная) и обратная матрица является матрицей перехода от базиса к базису . Координаты вектора в базисах и связаны формулами:          3. Определитель матрицы перехода от базиса к базису    равен отношению ориентированных объемов параллелепипедов, построенных на базисных векторах (рис.2.,а):     Определитель матрицы перехода от базиса на плоскости к базису равен отношению ориентированных площадей параллелограммов, построенных на базисных векторах (рис.2, б):      Определитель  матрицы перехода положительный, если эти базисы одноименные (оба  правых или оба левых), и отрицательный, если базисы разноименные (один правый, а другой левый). Рис.2 Любая невырожденная квадратная матрица (2-го или 3-го порядков) может служить матрицей перехода от базиса к базису (на плоскости или в пространстве соответственно). Докажем первое свойство. Запишем связь (4) для данных базисов:   Подставляя первое выражение во второе равенство, получаем   . Сравнивая с третьим равенством, приходим к (6). Докажем второе свойство.  Пусть  — матрица перехода от базиса к базису . Учитывая, что матрица перехода от базиса к базису — единичная), применяем свойство 1 к трем базисам . Для трех базисов аналогично получаем: . Следовательно, Докажем третье свойство для базисов в пространстве. Пусть матрица перехода от стандартного базиса к базису , где , , . По формуле (1.20) ориентированный объем параллелепипеда, построенного на векторах , равен смешанному произведению или, что то же самое, определителю . Аналогично, если — матрица перехода от стандартного базиса к базису , то . Из первых двух свойств матрицы перехода следует, что . что и требовалось доказать. Преобразование координат точки при замене системы координат.    Пусть в пространстве заданы  две системы координат    (старая) и (новая), известна матрица (2) перехода от базиса к базису , а также координаты вектора переноса начала координат в старом базисе :      Пусть  и — координаты точки относительно старой и новой систем координат. Требуется найти формулы, связывающие старые и новые координаты точки (рис.2.9). Запишем векторное равенство в координатной форме (в старом базисе ), учитывая, что координаты радиус-вектора совпадают с координатами точки, а старые и новые координаты вектора связаны формулой (4). Получим (7) Формула (7) устанавливает связь координат одной и той же точки в разных системах координат в пространстве, выражая старые координаты через новые. Аналогичная формула                              (8)   устанавливает связь координат одной и той же точки в разных системах координат на плоскости, выражая старые координаты через новые. Формулы вида (7) или (8): с любой невырожденной матрицей задают аффинное преобразование координат на плоскости или в пространстве. По этим формулам можно для любой старой системы координат установить новую систему координат, поскольку известен вектор переноса начала координат (координатный столбец ) и координаты новых базисных векторов в старом базисе (координатные столбцы являются столбцами матрицы ), и наоборот, по новой системе координат восстановить старую.      Прежде чем рассматривать аффинные  преобразования  плоскости остановимся  на некоторых основных понятиях, без которых невозможно описывать  преобразования.  Линейное преобразование  в месте с последующим преобразованием сдвига называют аффинным преобразованием. Аффинное преобразование Т (transition (анг.) – преобразование) в пространстве можно представить в матричной форме: .    . Аффинное преобразование плоскости однозначно определяется тройкой точек, не лежащих на одной прямой и их образами. Предположим, некоторое аффинное преобразование Т отображает точки и точки       Одним из  основных понятий является понятие движения. Это понятие связано с фиксацией точек с определенными координатами. Поскольку  о методах преобразованиями координат при переходе от одного базиса к другому говорилось ранее во введении, то остановимся на рассмотрении  тривиального случая, когда рассматриваются лишь любые две точки на плоскости. Движением называется такое преобразование плоскости, при котором сохраняется расстояние между двумя любыми точками. Следовательно, при движении расстояние между образами X/ и Y/ равно расстоянию между их прообразами X и Y. Различают собственное и несобственное движения. Всякое собственное движение может быть представлено как перенос или вращение вокруг некоторой точки. Любое несобственное движение представляется в виде параллельного переноса вдоль некоторого направления и симметрично относительно прямой, имеющей то же самое направление. Согласно приведенному определению движения следует, что при движении сохраняются углы. Это заключение логически следует из того, что выполняется равенство треугольников АВС и А/В/C/ по трем сторонам и таким образом выполняется равенство соответствующих углов. В полной мере это относится к реперам.       На плоскости можно задать два аффинных репера. Репер — упорядоченная в плоскости тройка точек, не лежащих на одной прямой. В частности, репер может быть ортонормированным прямоугольником (Декартовым). Пусть точка задана в репере и точка — в репере . Аффинное преобразование плоскости, как частный случай преобразования пространства, можно охарактеризовать действиями над реперами. Приведем следующее определение: Аффинным преобразованием плоскости называется такое преобразование, при котором репер переходит в репер и при этом для любой точки плоскости с координатами в репере ( ) переходит в точку с теми же координатами в репере ( ). Рассмотрим аффинное преобразования плоскости с учетом преобразования координат.      В этом случае преобразование плоскости можно задать  двумя скалярными функциями двух переменных                   .      Преобразование  можно задать вектором-функцией      .      Преобразование  А плоскости называется аффинным, если координаты  образа Y выражаются через координаты прообраза X по формулам         .     Матрица A = называется матрицей аффинного преобразования, y= , x= столбцы образа Y и прообраза Х являются столбцами радиус векторами и , a = столбец образа начала координат, или вектора переноса начала координат. Столбец     a = определяет координаты образа O´=A(О) начала координат. При   для точки =A(О) получим координаты точки а: , .      Рассмотрим  другую любую аффинную систему  координат  . Пусть известна матрица перехода . Известен переход от старого базиса   к новому базису ( ). Вектор переноса начала координат задается выражением = .  Таким образом, получаем ,  координатные столбцы точек  X и  Y (радиус-векторов , , и ) в старой       и новой системе координат.      Отсюда получаем                                               a +A     . Рис.3 Учитывая, что матрица  S обратимая, выразим координатный столбец образа Y через координатный столбец прообраза X в системе координат :      .     Получили аффинное преобразование с матрицей и координатным столбцом ) вектора переноса.

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

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

Q=T(P),

А для векторов — в виде:

v = R(u).

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

q =f(p),

v =f(u).

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

 

 

 

 

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

 

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

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

v = Аu,    где А — квадратная матрица. Сравнивая это выражение с полученным в разделе 4.3 для операции изменения фрейма, приходим к выводу, что, если А невырожденна, любое линейное преобразование соответствует изменению фрейма. Следовательно, линейное преобразование можно рассматривать с двух точек зрения: как изменение представления или фрейма, которое приводит к новому представлению вершин, или как преобразование вершин в рамках того же фрейма.

При выполнении операций в однородных координатах А представляет собой матрицу 4 4, которая оставляет неизменным четвертый компонент представления (w). Матрица А имеет вид

A=

     Двенадцать элементов матрицы могут изменяться произвольным образом, и мы говорим о таком преобразовании, что оно имеет 12 степеней свободы (degrees of freedom). Но точки и векторы в аффинном пространстве имеют немного другое представление. Любой вектор можно представить в виде

в любую точку — в виде

Если рассмотреть применение произвольного преобразования А по отношению к вектору

v = Au,

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

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

где P0 — точка, а d — вектор. В некотором фрейме прямая выражается с помощью представления p0 и d соответственно, точки P0 и вектор d в этом фрейме:

Для любой матрицы аффинного преобразования А справедливо соотношение

Таким образом, можно построить преобразование прямой, выполнив сначала преобразование p0 и d, а затем воспользоваться любым алгоритмом формирования прямой. Если используется форма представления отрезка двумя точками

получим аналогичный результат — нужно сначала выполнить преобразование р0 и р1 а затем по ним построить преобразованный отрезок. Поскольку в матрице А имеется 12 элементов, которые можно выбирать произвольно, то аффинное преобразование прямой или прямолинейного отрезка имеет 12 степеней свободы.

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

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

 Поворот, сдвиг и масштабирование

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

Плоскопараллельное смещение

Плоскопараллельное смещение, или сдвиг (translation),— это операция, которая смещает точки на фиксированное расстояние вдоль заданного направления (рис. 4.29). Сдвиг задается только вектором смещения d, поскольку для всех точек Р на объекте справедливо соотношение

P'=P + d.

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

Рис.4

Поворот

Задать поворот (rotation) несколько сложнее, чем сдвиг, так как требуется специфицировать больше параметров. Начнем с простого примера поворота точки вокруг начала координат в двухмерной плоскости, как показано на рис. Поскольку задана определенная точка — начало координат, — мы имеем дело с определенным фреймом. Двухмерная точка (х, у) в этом фрейме поворачивается вокруг начала координат на угол в и занимает после поворота позицию . Формулы полярным описания поворота несложно получить, воспользовавшись представлением точек (х, у) и (х', у'):

Воспользовавшись формулами приведения синуса и косинуса суммы углов, получим

Эти же уравнения можно записать и в матричной форме:

Обратите внимание на три свойства этого преобразования, которые сохраняются и в других вариантах операции поворота.

1.       Существует некоторая точка, она называется фиксированной точкой (fixed point) преобразования (в приведенном выше примере— начало координат), которая остается неподвижной при применении к ней этого преобразования. На рис. 5 показано, какой результат получится при повороте вокруг фиксированной точки, отличной от начала координат.