36.Элементы компьютерной алгебры Методические указания

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования Российской Федерации
Ярославский государственный университет им. П.Г. Демидова
Кафедра теории функций и функционального анализа
Элементы компьютерной алгебры
Методические указания
Ярославль 2004
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ББК
УДК
В 14я73+В15я73
Э 45
51(075)
Составители: Ф.И. Папоркова, Н.Б. Чаплыгина
Элементы компьютерной алгебры: Метод. указания / Сост. Ф.И. Папоркова, Н.Б. Чаплыгина; Яросл. гос. ун-т. – Ярославль, 2004. – 32 с.
Цель данных методических указаний – помочь студентам в приобретении
и закреплении элементарных навыков самостоятельного написания программ,
связанных с изучением курса «Геометрия и алгебра. Часть 1».
Предназначены для студентов первого курса математического факультета,
обучающихся по дисциплине «Дополнительные главы геометрии и алгебры»
(блок ЕН), специальности 010200 Прикладная математика и информатика, очной формы обучения.
Рецензент: кафедра теории функций и функционального анализа Ярославского государственного университета им. П.Г. Демидова.
© Ярославский государственный университет, 2004
© Ф.И. Папоркова, Н.Б. Чаплыгина, 2004
Учебное издание
Элементы компьютерной алгебры
Составители: Папоркова Флорида Идыфатовна
Чаплыгина Надежда Борисовна
Редактор, корректор В.Н. Чулкова
Компьютерная верстка И.Н. Ивановой
Подписано в печать 08.04.2004 г. Формат 60×84/16.Бумага тип.
Печать офсетная. Усл. печ. л. 1,86. Уч.-изд. л. 1,6. Тираж
экз. Заказ
Оригинал-макет подготовлен в редакционно-издательском отделе
Ярославского государственного университета.
Отпечатано на ризографе.
Ярославский государственный университет.
150000 Ярославль, ул. Советская, 14.
2
.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Преобразование точек плоскости
Пусть задана прямоугольная система координат и точка Р(х,у) с
координатами х и у, задаваемая матрицей (ху). Под воздействием линейного преобразования, осуществляемого матрицей А= 
a b
,
c d 
точка
Р(х,у) отображается в точку Р*(х*, у*), что эквивалентно записи
( ху)
a b

 = ( x * y *)
c d 
или aх+су=х*, bx+dy=y*.
Рассмотрим несколько частных случаев, демонстрирующих разное влияние отдельных элементов матрицы на перемещение точки Р.
Начнем с элементов главной диагонали:
1. Тождественное преобразование задается матрицей А= 
1 0

0 1
не меняет положения точки Р. Действительно, (ху)
х=х*, у=у*.
− 1 0

 0 − 1
2. Матрица А= 
1 0

 = ( х * у *)
0 1
и
или
осуществляет симметричное отображе-
ние точки Р(х,у) относительно начала координат, что эквивалентно
повороту точки на 180о:
( ху)
− 1 0

 0 1
3. Матрица А= 
− 1 0 

 = ( х*, у *),
 0 − 1
− х = х*,
− у = у *.
вызывает симметричное отображение точ-
ки Р(х,у) относительно оси Оу:
− 1 0 

 = ( х*, у *),
0
−
1


1 0

Матрица А= 
0
−1


( ху)
4.
− х = х*,
осуществляет отображение, симметричное
относительно оси Ох:
5. Матрица А= 
а 0

0
1


правлении оси Ох:
( ху)
1 0

0
d


1 0 

 = ( х*, у *),
−
0
1


х = х*,
− у = у *.
вызывает перемещение точки Р(ху) в на(ху)
6. Матрица А= 
у = у *.
 а 0

 = ( х*, у *),
0
1


ах = х*,
у = у *.
осуществляет перемещение точки Р(ху) в
направлении оси Оу.
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. Матрица А= 
а
0

0 d 
вызывает перемещение одновременно вдоль
осей Ох и Оу. При а=d>1 имеет место увеличение масштаба координат точки Р. При 0<a=d<1 – уменьшение масштаба. Итак, элементы
главной диагонали матрицы преобразования вызывают отображение
и изменение масштаба координат. Далее рассмотрим влияние элементов побочной диагонали матрицы преобразования.
8. Матрица А= 
0 1

1 0
осуществляет симметричное отображение
относительно прямой у=х:
( ху)
0 −1

0 
−1
9. Матрица А= 
0 1

 = ( х*, у *),
1 0
у = х*,
х = у *.
осуществляет симметричное отображение
относительно прямой у=-х.
10. Матрица А= 
0 1

−
1
0


стрелки:
вызывает поворот на 90о против часовой
 0 1

 = ( х*, у *), − у = х*,
х = у *.
 −1 0
0 − 1
 вызывает поворот на
11. Матрица А= 
1 0 
0 − 1
 = ( х*, у *),
стрелки: (ху) 
у = х*, − х = у * .
0 
1
(ху)
270о против часовой
Таким образом, элементы побочной диагонали матрицы вызывают либо поворот, либо симметричное отображение.
Матрицы вида
0 b


1
0


и
0 1

 ,
0
с


где b≠±1, с≠±1, осуществляют
симметрию с последующим изменением масштаба соответственно по
оси Ох и оси Оу.
Наконец рассмотрим преобразования сдвига и смещения.
12. Матрица А= 
1 b

0 1
(ху)
0 b

 = ( х*, у *),
0 1
(x
осуществляет сдвиг в направлении оси Оу:
bx + y) = ( x * y *),
4
x = х*,
bх + y = у * .
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
13. Матрица А= 
1 0

c 1
(ху)
1 0

 = ( х*, у *),
1
c


вызывает сдвиг в направлении оси Ох:
(x + cy
y) = ( x * y *),
x + cy = х*,
y = у *.
Результат преобразования точек с помощью матрицы общего вида, когда преобразование применено к началу координат, имеет вид
(0
0)
a

c
b
 = ( x * y *)
d 
или
х* = 0, у* = 0 .
Это означает, что начало ко-
ординат является инвариантом. Это ограничение может быть преодолено путем введения однородных координат, о которых более подробно будет сказано позднее. Сейчас мы лишь заметим, что эта трудность преодолевается при помощи преобразования, задаваемого мат1 0 0 


 0 1 0 ,
 m n 1


рицей вида
и введения третьей компоненты в радиус-
векторы точек Р(х,у) и Р*(х*,у*), т.е. представляя их в виде (х у 1) и
(х* у* 1). Действительно, имеем:
(х
1 0 0 


 0 1 0  = ( x * y * 1)
 m n 1


у 1)
А= 
a 0
Р
(x + m
1) = ( x * y * 1).
1 0

0 d 
Р*
у*,у
А= 
0

0 d 
у*,у
Р
−1 0

 0 1
А= 
х,х*
−1 0 

 0 − 1
А= 
1 0

 0 −1
у*,у
a
Р*
Р
Р*
х,х*
х,х*
А= 
у*,у
Р*
y+n
А= 

 0 1
у*,у
или
у*,у
Р
Р
х,х*
Р*
5
х,х*
Р*
Р
х,х*
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
0 − 1

−1 0 
А= 
0 1

1 0
у*,у
А= 
Р
у*,у
*
Р
Р
у=х
Р*
х,х*
х,х*
у=-х
0 − 1

1 0 
А= 
А= 
0 1

 −1 0
у*,у
у*,у
Р*
о
270
Р
Р*
90о
х,х*
А= 
1 b

0 1
Р
х,х*
А= 
1 0

с 1
у*,у
у*,у
су
Р*
bx
х*=су+х
Р
Р*
cy
P
y*=bx+y
bx
х,х*
х,х*
Рис. 1. Преобразование точек
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Преобразование прямых линий на плоскости
Известно, что прямая линия определяется двумя (различными)
своими точками. Пусть прямая проходит через точки M и N. Радиусвекторы точек M и N соответственно равны (11) и (23). Рассмотрим
матрицу преобразования А= 
1 3
,
 4 1
осуществляющую операцию сдви-
га. Имеем МА= (11)
NA= (23)
1 3
 = (5 4 ) = М*,
 4 1
1 3
 = (14 9 ) = N*.
 4 1
Более компактно прямая линия (MN) может быть представлена
матрицей В= 
11 

23
 
и преобразование прямой линии может быть заВА= 
11 

23
 
писано следующим образом:
1 3   5 4 

 = 
 = В*.
4
1
14
9

 

Здесь строки матрицы В* представляют собой радиус-векторы
точек М* и N*.
у*,у
N*
N
M*
M
x,x*
Рис. 2. Преобразование линии
По рис. 2 видно, что операция сдвига увеличила длину линии
(MN) и изменила ее положение.
Преобразование параллельных линий
Пусть задана прямая (MN), определяемая двумя точками М(х1,у1)
и N(х2,у2), и прямая (E F), параллельная (MN), определяемая точками
E и F.
Угловой коэффициент прямой (MN) или (E F) определяется отношением k1= У2 − У1 .
Х2 − Х1
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Подвергнув прямую (MN) общему преобразованию, получим
прямую (M*N*):
 х1

 х2
у1 

у2 
 а b   ax1 + cy1

 = 
 c d   ax2 + cy2
bx1 + dy1   x1*
=
bx2 + dy2   x2*
y1*   M *
=
.
y2*   N * 
Определим угловой коэффициент прямой (M*N*)
y2 − y1
(bx + dy2 ) − (bx1 + dy1 ) b( x2 − x1 ) + d ( y2 − y1 )
x2 − x1 b + dk1
=
=
=
k2 = 2
.
(ax2 + cy2 ) − (ax1 + cy1 ) a ( x2 − x1 ) + c( y2 − y1 ) a + c y2 − y1 a + ck1
x2 − x1
b+d
Отсюда видно, что k2 не зависит от координат х1, х2, у1, у2, а
k1, a, b, c, d имеют одни и те же значения как для прямой (MN), так и
для (EF). Следовательно, k2 один и тот же для (M*N*) и для (E*F*).
Итак, параллельные линии остаются параллельными после преобразования. Это означает, что параллелограмм преобразуется в другой параллелограмм.
Преобразование пересекающихся линий
Пусть прямая MN определяется точками М  − 1 , 3 
 2 2
и
N(3,-
2), а прямая EF – точками Е(-1, -1) и F  3, 5 . Точкой пересечения этих
 3
прямых является точка К  4 , 1  . Преобразование прямых, задаваемое
5 5
матрицей А= 
1 2 
 ,
1 − 3 
M*N*:
E*F*:
 1
−
 2
 − 1 − 11

5 
3
1
3 

приводит нас к прямым, определяемым точками:
11 
1
 − 
11 

1
2
2
 
3 
М * 1, − 
=
, где

2 ,

2 1 − 3  
12 
N * (1, 12)

1


E * (− 2, 1)
2   − 2 1
14
=
, где F *  14 , 1 .
= 3  
1
 3


3
Точкой пересечения полученных прямых является К*(1, 1), что
подтверждается и преобразованием точки пересечения исходных
прямых
4

5
1 1 2 
 = (1, 1) .

5 1 − 3 
Итак, получили, что точка пересечения
исходной пары прямых линий преобразуется в точку пересечения
преобразованной пары.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Преобразование плоских фигур
Рассмотрим плоский треугольник MNL, определенный своими
вершинами: M(1, 2), N(1, 5) и L(2, 2). Преобразование данного треугольника эквивалентно преобразованиям его вершин. Действительно, рассмотрим две матрицы: А= 
3 0

 0 3
6
и
0 

1 .
2
В= 
0
Первая из них осуществляет увеличение в 3 раза координат относительно исходных. В результате действия преобразования, заданного второй матрицей, мы также имеем изменение масштаба, но, в силу
разных элементов главной диагонали матрицы, мы получаем искажение формы исходного треугольника. Чтобы записать преобразование
в матричной форме, запишем координаты вершин заданного треугольника в строки, образуя матрицу разметом 3х2. Тогда имеем:
 1 2


1 5
 2 2


3 6 

 3 0 

 =  3 15 
 0 3  6 6 


и
6
6 0 

1  = 6
0
 
2  12


M*(6, 1), N*  6,

1 2


1 5
 2 2


где M*(3, 6), N*(3, 15), L*(6,6) и
шины преобразованных треугольников.
N*
у*,у
N
1
5
,
2
1
5
,
2
L*(12, 1) – вер-
у,у*
L*
N
M*
N*
M L
х,х*
M L
M*
L*
хх*
Рис. 3. Равномерное и неравномерное изменение масштабов
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Известно, что преобразование поворота на угол α против часовой
 cos a sin a 
стрелки задается в общем виде матрицей  − sin a cos a  .


Мы рассмотрим частный случай поворота на 900 против часовой
стрелки исходного треугольника MNL.
Компактно это запишется так:
 − 2 1
1 2


  0 1 


=
−
1
5
5
1
,

 
 
 2 2  −1 0  − 2 2




где М*(-2,1), N*(- 5,1), Н*(- 2,2) – вершины преобразованного треугольника, М*N* Н* – результат поворота треугольника М N Н.
у*,у
N
H*
M H
N*
M*
х,х*
Рис. 4. Вращение
Преобразования симметричного отражения относительно оси, задаваемой уравнением у=х, и оси у=0 осуществляются матрицами вида А= 
0 1

1 0
и В= 
1 0

 0 −1
соответственно.
В этих случаях новые вершины определяются соотношениями
2 1
1 2


 0 1 
 −  5 1 
 1 5  
 2 2 1 0  2 2




и
1 − 2
1 2


 1 0  
 =  1 − 5  .
 1 5  
 2 2   0 − 1  2 − 2 




10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
N
у*,у
y*,y
N
M
L
х,х*
L L*
M
M*
M*
L*
N*
N*
х,х*
Рис. 5. Отображения
Комбинирование преобразований
Известно, что произведение матриц является некоммутативным.
Чтобы проиллюстрировать этот факт, рассмотрим преобразования
поворота и отображение треугольника MNL, задаваемого вершинами
М(1,2), N(1,5), L(2,2). Пусть за поворотом на 900 против часовой
стрелки следует отображение относительно оси у=0, тогда эти два
последовательных преобразования треугольник M N L переведут в
треугольник M* N* L*
− 2 1
1 2


  0 1 


=
−
1
5
5
1


 
 
 2 2  −1 0  − 2 2




 2 −1
− 2 1


 1 0  
 =  − 5 − 1  .
 − 5 1  
 − 2 2   0 − 1  − 2 − 2 




Если преобразования поворота и отображения будут осуществлены в другом порядке, то будет следующий результат
1 2 

 1 0 

1 5  
−
0
1

1 2  


 2 1
 1 2



0 1 
 0 1
 =  5 1 

 =  1 5  
−
1
0
1
0
  2 2 .

  2 2 




11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
у,у*
у,у*
N
N
L
L*
M
L
M
М*
х,х*
N*
х,х*
M*
N*
L*
Рис. 6. Комбинирование вращения и отображения
Преобразование единичного квадрата
Рассмотрим единичный квадрат АВСД, заданный вершинами А
(0,0), B(1,0), С (1,1) и Д (0,1), что можно записать матрицей вида
0 0


1
1


1 1 .


0 1


Применим преобразование общего вида к этому квадрату, что записывается следующим образом:
0

1
1

0

0

0  а

1  с

1 
0 
 0


в  a
в 
=
d   a + с в + d  , где



 с
d


А* (0,0),
В * (а .в),
Д * (с, д).
Квадрат АВСД преобразуется в параллелограмм А*В*С*Д* с
общей для них вершиной А=А*. Отметим также, что координаты
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
точки В* определяются первой строкой общей матрицы преобразований, а координаты Д* - второй строкой этой матрицы. Таким образом, если координаты точек В* и Д* известны, то общая матрица
преобразования определена. Отметим также, что элементы В и С вызывают сдвиг исходного квадрата по направлениям осей Ох и Оу, а
элементы а и d характеризуют коэффициенты изменения масштаба.
Итак, преобразование общего вида осуществляет комбинацию сдвига
и изменения масштаба.
у
у*
у,у*
a+c
1 D
C
C*
c D*
d
C*
D*
D
C
A
B
b+d
B*
B*
A
B
а)
х
a
b
A*
c
х*
б)
Рис. 7. Общее преобразование
единичного квадрата:а) - до преобразования, б) - после преобразования
х,х*
Рис. 8. Вращение
единичного квадрата
На примере поворота единичного квадрата против часовой стрелки на угол α продемонстрируем определение элементов матрицы
преобразования. По рис. 8 видно, что точка В (1,0) преобразуется в
точку В* (cos a, sin a), а Д(0,1) в Д* (- sin a, cos a).
Следовательно, можно записать:
0

1
1

0

0

0
1

1 
а

с
 0

в   cos a
=
d   a + c

 − sin a

0   0
0 

 
sin a   a
в 
=
− b + d  a + c в + d ,

 
cos a   c
d 
из чего следует, что матрицу преобразования поворота на угол α
 cos a sin a 
можно записать так: А =  − sin a cos a  .


13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Однородные координаты
Представление двумерного вектора трехмерным или в общем
случае n-мерного вектора (n+1)-мерным называют однородным координатным воспроизведением. При однородном координатном воспроизведении n-мерного вектора оно выполняется в (n+1)-мерном
пространстве, и конечные результаты в n-мерном пространстве получают с помощью обратного преобразования. Таким образом, двумерный вектор (х у) представляется трехкомпонентным вектором (hx hy
h). Разделив компоненты вектора на однородную координату h, получим
hy
hx
,
y= .
h
h
Не существует единственного однородного координатного представления точки в двумерном пространстве. Например, однородные
координаты (12, 8, 4), (6, 4, 2) и (3, 2, 1) представляют исходную точку (3, 2). Для простоты вычислений выбираем (ху1), чтобы представить непреобразованную точку в двумерных однородных координаa b 

 = ( x * y *) в дополнительных коор(
)
xy
тах. Преобразование
c
d


динатах задается выражением в однородных координатах в виде
х=
 а в 0


(ху1)  с d 0  = ( ХУН ) или (х*у*1) = (ХУН).
 0 0 1


В общем случае Н≠1, и преобразованные обычные координаты
Х
получаются за счет нормализации однородных координат: х*= ,
Н
у*=
у
.
Н
Геометрически все преобразования х и у происходят в плоскости
Н=1 после нормализации преобразованных однородных координат.
Преимущество введения однородных координат проявляется при
использовании матрицы преобразований общего вида порядка 3х3:
а b

с d
m n

14
p

g .
s 
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ранее мы исследовали воздействие элементов а, в, с, d, m, n.
Чтобы продемонстрировать роль элементов p и g при преобразованиях, рассмотрим операцию:
1 0 Р 


g
0
1
 = (х у pх +gy+1).
(ХУН) = (ху1) 
0 0

1 
Здесь Н = рх+gy+1. Переменная Н, которая определяет плоскость,
содержащую преобразованные точки, представленные в однородных
координатах, теперь образует уравнение плоскости в трехмерном
пространстве. Это преобразование показано на рис. 9, где линия АВ,
лежащая в плоскости хОу, спроектирована на линию СД плоскости
рХ+gY – Н + 1 = 0, здесь р = g=1.
Выполним нормализацию для того, чтобы получить обычные коХ
Х
Y
Y
, у*= =
.
ординаты: x*= =
Н pХ + gY + 1
Н pX + gY + 1
у=Y
Н=1
y*
А
В
С*
Д*
х=Х
x*
С
Н
Д
pX + gY – H + 1 = 0
Рис. 9. Преобразование в однородных координатах
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Полагая р=g=1, для точек А (1, 2) и В (3, 1) получим после преобразования А в C* и В в Д*:
x* = 1 = 1 , у* = 1 .
1+ 2 +1
4
2
Однородные координаты для точек С*, Д* соответственно равны
С*  1 , 1 ,1 и Д*  3 , 1 ,1 .
4 2 
5 5 
Результатом нормализации является перевод трехмерной линии
СД в ее проекцию С*Д* на плоскость Н=1. Как показано на рис. 9,
центром проекции является начало координат.
Осталось исследовать влияние элемента s матрицы общего вида.
В связи с этим рассмотрим преобразование
(ХУН) = (xу1)
1 0 0


 0 1 0 =
0 0 s 


(x у s).
Здесь H = s, что дает x* =
х
,
s
у*=
у
.
s
В результате преобразования
(xу1)→( х y 1 ) имеет место однородное изменение масштаба радиусs s
вектора точки.
При s <1 происходит увеличение, а при s>1 – уменьшение масштаба.
Итак, основная матрица преобразования размера 3х3 для двумерных однородных координат может быть подразделена на четыре части:
 a b . p


c d . a
. . . .


m n . s 


Элементы а, в, с, d осуществляют изменение масштаба, сдвиг и
поворот; m и n выполняют смещение; p и g – получение проекций; s
производит полное изменение масштаба.
Точки в бесконечности
Введение однородных координат дает возможность удобно и эффективно отразить множество точек одной координатной системы в
соответствующее множество преобразованной системы координат.
При этом бесконечная область одной координатной системы будет
отражаться в конечную область другой координатной системы; пря16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
мые линии, параллельные в одной системе координат, в общем случае не будут параллельными в другой, а геометрические свойства
точки пересечения можно оценить в любой из этих систем координат.
Рассмотрим две прямые линии, заданные уравнениями
 х− у =1
,

х + 2 у = 0
точка пересечения которых определяется как решение системы урав1 − 1 1   1 − 1 1   1 − 1 1   1 0 2 3 

 
 
 

1 2 0  →  0 3 − 1 →  0 1 − 1 / 3  →  0 1 1 3  .

 
 
 

нений методом Гаусса
Итак M (2/3, -1/3) – точка пересечения прямых.
Это решение может быть получено в элементах однородной системы координат. Перепишем уравнения в виде х – у – 1 = 0, х + 2у =0
и представим их в матричной форме:
 1 1


(х у 1) − 1 2  = (0 0) .
 −1 0


Но чтобы матрица имела себе обратную, она должна быть квадратной. Поэтому дополним все матрицы последнего уравнения третьим столбцом:
(х
 1 1 0


у 1) − 1 2 0  = (0 0 1) .
 −1 0 1


Пусть А =
 1 1 0


 −1 2 0 ,
 −1 0 1


тогда А =
-1
 2 −1 0

1
1 1 0 .
3

 2 −1 3
Умножая обе части уравнения (х у 1) А = (001) на А–1, получим
(ху 1)=(001) А = (001)
-1
 2 −1 0
 1
1
2
 1 1 0  = (2 − 1 3) = 
3
3
 3
 2 − 1 3
1 
1 .
3 
И мы вновь получим точку пересечения с координатами х =
2
,
3
у
= - 1.
3
Пусть две параллельные линии определены уравнениями
х – у = 1; х – у = 0.
Это
можно
записать
в
матричной
форме
(х
 1 1 0


 − 1 − 1 0  = (0 0 1) .
 −1 0 1


17
у 1)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В данном случае квадратная матрица не имеет обратной в силу
одинаковых первых двух строк, поэтому изменим матричную запись
следующим образом:
 1 1 1


(х у 1)  − 1 − 1 0  = (0 0 х)
 −1 0 0


 0 0 − 1


-1
Тогда В =  0 − 1 1  .
1 1
0 

Отсюда (х
у 1)
или
(х
В В = (00x) В = (00х)
-1
-1
у 1) B
= (0
0 х) .
 0 0 − 1


0 −1 1  ,
1 1
0 

(х у 1) = (х х 0) = х (110).
Полученные однородные координаты (110) должны представлять
«точку пересечения» двух параллельных линий в бесконечности, поскольку двумерный однородный вектор (а в о) образует точку в бесконечности на линии ау-bх=0. Тот факт, что вектор с однородной
компонентой Н, равной нулю, представляет точку в бесконечности,
может быть проиллюстрирован процедурой, изложенной ниже.
Рассмотрим линию у* = 3 х* и точку (ХУ) = (4 3).
4
Однородные координаты для точки (4 3):
Н
х*
у*
Х
У
1
4
3
4
3
1/2
8
6
4
3
1/3
12
9
4
3
1/4
16
12
4
3
Н
1
10
х*
у*
Х
У
40
30
4
3
1
100
400
300
4
3
Из этой таблицы видно, что точка (4 3) может быть представлена
в однородных координатах любыми способами.
Заметим, что при Н →0 отношение у * остаётся равным 3 и слех*
4
дующие одна за другой пары (х* у*), которые попадают на прямую
у* = 3 х*, становятся ближе к бесконечности.
4
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Таким образом, в пределе, когда Н →0, точка в бесконечности (х*
у* 1) = (∞ ∞ 1) задается значениями (ХУН) = (430) в однородных координатах. Из этого следует, что вектор (100) представляет точку в
бесконечности на оси Оx*, а вектор (010) представляет точку в бесконечности на оси Оу*. В такой форме однородные координаты дают
удобное представление точек в бесконечности.
Двумерное вращение вокруг произвольной оси
Однородные координаты обеспечивают поворот изображения вокруг точек, отличных от начала координат. В общем случае вращение
около произвольной точки может быть выполнено путем переноса
центра вращения в начало координат, поворотом относительно начала координат, а затем переносом точки вращения в исходное положение. Таким образом, поворот радиус-вектора (х у 1) около точки (m,
n) на произвольный угол α может быть выполнен с помощью прео бразования
(xy1)
0 0
 1


1 0
 0
 − m − n 1


 cos a

 − sin a
 0

0

0
1 
sin a
cos a
0
 1 0 0


 0 1 0  = ( XYH ) .
 m n 1


Двумерные вращения около каждой оси прямоугольной системы
представлены следующими матрицами:
C=
 cos a

 − sin a
 0

в) вокруг оси Ох:
А=
0
1

 0 cos a
 0 − sin a

с) вокруг оси Оу:
 cos β

В=  0
 sin β

а) вокруг оси Oz:
19
sin a
cos a
0
0

0 ;
1 
0 

sin a  ;
cos a1
0 − sin β 

1
0 .
0 cos β 
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Трехмерные преобразования
Для наилучшего восприятия формы объекта необходимо иметь
его изображение в трехмерном пространстве. Во многих случаях наглядное представление об объекте можно получить лишь путем выполнения операций вращения и переноса, а также путем построения
его проекций.
В связи с этим введем снова однородные координаты, тогда точка
в трехмерном пространстве (x y z) представится четырехмерным
вектором (xyz1) или (X Y Z H).
Преобразование описывается соотношениями
( х у z 1)А = ( Х У Z H )
X Y Z 
1 ,
и (х* у* z* 1) = 
H
H
H


где А - матрица некоторого преобразования. Обобщенная матрица
преобразования размера 4х4 для трехмерных однородных координат
имеет вид
 a b c p


d e f g 
А = h i j r 


l m n s


и может быть представлена в виде четырех отдельных частей
 3х 3 . 3х1


 . . . 
 1х 3 . 1х1 


Матрица размера 3х3 осуществляет линейное преобразование в
виде изменения масштаба, сдвига и вращения. Матрица - строка размера 1х3 производит перенос, а матрица-столбец размера 3х1 - преобразование в перспективе. Последний скалярный элемент выполняет
общие изменения масштаба. Полное преобразование, полученное путем воздействия на радиус-вектор точки матрицы размера 4х4 и нормализации преобразованного вектора, будем называть билинейным
преобразованием. Оно обеспечивает выполнение комплекса операций
сдвига, частичного изменения масштаба, вращения, отображения, переноса, а также изменения масштаба изображения в целом.
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Трехмерные изменения масштаба
Диагональные элементы основной матрицы преобразования размера 4х4 осуществляют частичное и полное изменение масштабов.
Преобразование
a

o
(хуz1)  o

o

o o o

e o o
= (ax ey
o j o

o o 1 
jz 1) = ( x * y * z * 1) производит час-
тичное изменение масштабов.
Общее изменение масштаба получается за счет использования
четвертого диагонального элемента:
(хуz1)
1

0
0

0

0 0 0

1 0 0
= (x
0 1 0

0 0 S 
x
s
y z s ) = ( x * y * z * 1) = 
y
s
z 
1 .
s 
Такой же результат можно получить при равных коэффициентах
частичных изменений масштабов. В этом случае матрица преобразо1

s
0
вания должна быть равной 
0

0
0
1
s
0
0
0 0 
0 0

1
0 .
s

0 1

Трехмерный сдвиг
Недиагональные элементы верхней левой подматрицы размера
3х3 от общей матрицы преобразования размера 4х4 осуществляют
сдвиг в трех измерениях (ху1)
1 b

d 1
h i

o o

o

o
= ( x + dy + hz, bx + g + iz, cx + fy + z,1) .
1 o
c
f
0

1 
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Трехмерное вращение
Ранее было показано, что матрица размера 3х3 обеспечивала
комбинацию операций изменения масштаба и сдвига. Однако, если
определитель матрицы размера 3х3 равен 1, то имеет место чистое
вращение около начала координат.
Исследуем некоторые частные случаи.
При вращении вокруг оси ОХ на угол α размеры вдоль оси Ох не
изменяются. Таким образом, матрица преобразований будет иметь
нули в первой строке и первом столбце, за исключением единицы на
главной диагонали. Другие элементы определяются так же, как делалось ранее:
0
0
1

 0 сosa sin a
А =  0 − sin a cjsa

0
0
0

0

0
0 .

1 
Для вращения на угол β около оси Оу нули ставят во второй
строке и втором столбце матрицы преобразования, за исключением
единицы на главной диагонали. Матрица определяется выражением
 cos β

 0
В=  sin β

 0

0 − sin β
1
0
0 cos β
0
0
0

0
0 .

1 
Аналогично матрица преобразования для вращения на угол γ во-
 cos γ

 − sin γ
круг оси Oz имеет вид С=  0

 0

sin γ
cos γ
0
0
0 0

0 0
1 0 .

0 1 
Определители всех этих матриц равны 1.
Отображение в пространстве
Наиболее просто отображение осуществляется относительно
плоскости. Для отображения без изменения масштабов необходимо,
чтобы определитель преобразования был равен - 1. При отображении
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
относительно плоскости хОу изменяется только знак координаты z.
1

0
А=  0

0

Поэтому матрица преобразования имеет вид
0

1 0 0
0 −1 0 .

0 0 1 
0
0
Аналогично для отображения относительно плоскости уОz:
−1

0
В=  0

0

0 0 0

1 0 0
,
0 1 0

0 0 1 
а относительно плоскости хОz: С=
1 0

0 −1
0 0

0 0

0
0
1
0
0

0
.
0

1 
Отображение относительно других плоскостей можно получить
путем комбинации вращения и отображения.
Пространственный перенос
Трехмерный линейный перенос изображения определяется выражением
1 0

0 1
(х у z 1)
0 0

l m

или ( х + l
0 1

0 0
= (Х У
1 0

n 1 
Z H)
y + m z + n 1) = ( X Y Z H ) .
Отсюда следует, что Х* =
Х
H
= x+l,
z+n.
23
У* =
Y
H
= у + m,
Z* =
Z
H
=
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Приложение
В приложении приведены примеры программ на языке С++, реализующие некоторые геометрические преобразования и построения.
Часть из них представляют алгоритмы, основанные на математических положениях, изложенных в данных методических указаниях.
Алгоритмы, реализованные другими программами, можно найти в
указанной литературе [I].
1. Масштабирование n (n<=N=100) точек с координатами, заданными массивами x[], y[]. Масштабирование задается коэффициентами kx по оси 0x и ky по оси 0y. Результирующие координаты точек – в тех же массивах x[] и y[] .
void scale2d(int n, float x[], float y[], float kx, float ky)
{float u[N][2],v[N][2]; // u-матрица исходной информации,
// v- преобразованные координаты,
// t - матрица преобразования, N – константа.
for(int i=0;i<n;i++) // формирование матрицы u
{ u[i][0]=x[i];
u[i][1]=y[i];
}
float t[2][2];
t[0][1]=t[1][0]=0;
// формирование матрицы преобразования t
t[0][0]=kx; t[1][1]=ky;
prodm2(v,u,t,n); // обращение к функции, вычисляющей v=u*t
for(i=0;i<n;i++) // получение выходных массивов координат
{x[i]=v[i][0];
y[i]=v[i][1];
}
}
2. Алгоритм двумерного смещения n точек с координатами,
заданными массивами x[], y[], на dx по оси 0X, на dy по оси 0Y.
Результирующие координаты смещенных точек – в исходных
массивах x[] и y[].
void trans2d(int n,float x[],float y[],float dx,float dy)
{ float u[N][N],v[N][N];
// N - константа
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
for(int i=0;i<n;i++)
for(int j=0;j<4;j++)
{ u[i][j]=0;v[i][j]=0;
} //j,i
for(i=0;i<n;i++)
{ u[i][0]=x[i];
u[i][1]=y[i];
u[i][2]=1;
} //i
float t[N][N];
// t – матрица преобразования
for(i=0;i<3;i++)
for(int j=0;j<3;j++)
{t[i][j]=0;
}
//j,i
t[0][0]=t[1][1]=t[2][2]=1;
t[2][0]=dx; t[2][1]=dy;
prodm(v,u,t,n,3,3); // функция вычисляет v=u*t
for(i=0;i<n;i++)
{ x[i]=v[i][0];
y[i]=v[i][1];
} //i
} //trans2d
3. Алгоритм двумерного поворота n (n<=N) точек с координатами, заданными массивами x[], y[], на угол teta против часовой
стрелки вокруг точки с координатами (ax, ay). Результирующие
координаты точек - в исходных массивах x[], y[].
void rot2d(int n,float x[],float y[],float teta,float ax,float ay)
{float u[N][3],v[N][3]; //u-матрица для исходной информации,
//v - матрица преобразованных координат
//t-матрица преобразования
for(int i=0;i<n;i++)
{ u[i][0]=x[i];
u[i][1]=y[i];
[i][2]=1;
}
float t[3][3];
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
t[0][2]=t[1][2]=0;
t[2][2]=1;
t[0][0]=t[1][1]=cos(teta);
t[0][1]=sin(teta);t[1][0]=-t[0][1];
t[2][0]=-ax*(cos(teta)-1)+ay*sin(teta);
t[2][1]=-ay*(cos(teta)-1)-ax*sin(teta);
prodm3(v,u,t,n);
// v=u*t
for(i=0;i<n;i++)
{x[i]=v[i][0];
y[i]=v[i][1];
}
}
4. Построение параметрического эллипса на плоскости.
void ellipse
(float c[2],
//координаты центра эллипса
float a,float b, //полуоси большая и малая
float fi,
//угол наклона большой оси в градусах
int n,
//число точек на эллипсе
float p[N][2] //сами генерируемые точки эллипса
)
{float d=2.0*3.1415926/n; //приращение угла
fi/=57.2957795;
//преобразовать к радианной мере
float cf=cos(fi),
sf=sin(fi),
cd=cos(d),
sd=sin(d),
c3=1.0,
s3=0.0;
float x1,y1;
for(int i=0;i<n;i++) //i-номер очередной точки эллипса
{ x1=a*c3;
y1=b*s3;
p[i][0]=c[0]+x1*cf-y1*sf;
//формирование координат точек эллипса
p[i][1]=c[1]+x1*sf+y1*cf;
float t=c3*cd-s3*sd;
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
s3=s3*cd+c3*sd;
c3=t;
} //i
} //ellipse
5. Построение сегментов кривой Безье из р точек на плоскости по заданному n-угольнику. При построении используется базисная функция Бернштейна basis, в теле которой функция c_n_i
вычисляет биномиальный коэффициент и функция st(t,i) вычисляет степень t^i.
void bezier (int n,
//число точек многоугольника
float x[], float y[], //координаты вершин многоугольника
int p,
//число точек кривой Безье
float bx[], float by[]) //координаты точек кривой Безье
{float j[N];
zer(j,n);
//заполнение массива нулями функцией zer
float b[N][2];
for (int i=0;i<n;i++)
{ b[i][0]=x[i];
b[i][1]=y[i];
}//i
int k=0;
//номер очередной точки кривой
for(float t=0;t<=1;t+=1.0/(p-1))
{ for(int i=0;i<n;i++)
j[i]=basis(n-1,i,t);
float temp[2];
//очередная точка кривой
prod(temp,j,b,n);
//функция prod вычисляет temp=j*b
bx[k]=temp[0];
by[k++]=temp[1];
} // t
} // bezier
float basis(int n,int i,float t)
{ return c_n_i(n,i)*st(t,i)*st(1-t,n-i);
} // basis
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
На первом рисунке изображена кривая Безье, построенная программой примера 5 для ломаной, состоящей из трех отрезков прямых. Кривая построена на 20 точках.
На втором рисунке изображена кривая кубического сплайна с заданными условиями на концах, построенная программой примера 6
для ломаной, состоящей из четырех отрезков прямых. Для построения каждого сегмента кривой были вычислены по десять точек сегмента.
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6. Построение на плоскости кривой кубического сплайна с
фиксированными условиями на концах.
Сначала описаны вспомогательные функции: change, ml, sb, inv.
Последняя описанная функция spline строит кривую кубического
сплайна.
// Обмен двух строк i-й и j-й матрицы a значениями
void change(int n, float a[N][N], int i, int j)
{ int k;
for(k=0;k<n;k++)
{ float r=a[i][k];
a[i][k]=a[j][k];
a[j][k]=r;
}
} // change
//Умножение i-й строки матрицы a на число c
void ml(int n, float a[N][N], int i, float c)
{ int k;
for(k=0;k<n;k++)
a[i][k]*=c;
} // ml
//Вычесть из строки i строку j, умноженную на с
void sb(int n, float a[N][N], int i, int j, float c)
{ int k;
for(k=0;k<n;k++)
a[i][k]-=c*a[j][k];
} // sb
//Следующая функция получает обратную матрицу a_1 из
//матрицы a методом Гаусса и возвращает 0, если исходная
//матрица вырожденная, и 1 – в противном случае;
// исходный массив а размером nxn преобразуется при этом в
//единичную матрицу
int inv(int n, float a[N][N], float a_1[N][N])
{ int i,j;
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
zer(a_1,n,n);
// функция zer инициализирует нулями массив а_1
for(i=0;i<n;i++)
а_1[i][i]=1.0;
// обнуление поддиагональных элементов
for(i=0;i<n;i++)
{ j=i;
while((a[j][i]==0)&&(j<n))j++;
if(j==n)return 0;
if(i!=j){change(n,a,i,j); change(n,a_1,i,j);}
ml(n,a_1,i,1./a[i][i]);ml(n,a,i,1./a[i][i]);
for (j=i+1;j<n;j++)
{sb(n,a_1,j,i,a[j][i]);sb(n,a,j,i,a[j][i]);}
} //i
//обнуление наддиагональных элементов
for(i=n-1;i>0;i--)
for (j=i-1;j>=0;j--)
{sb(n,a_1,j,i,a[j][i]);sb(n,a,j,i,a[j][i]);}
return 1;
} //inv
int spline(int n, // число точек в исходном массиве
float p[][2], //массив с исходными точками данных
// упорядочен по первой координате
float p_b[2], //векторы касательных на концах кривой
float p_e[2],
int ns,
// число точек, вычисляемых для каждого
// сегмента кривой, 1<ns<=NS, где NS – некоторая константа
float pout[N*NS][2]) //выходной массив точек сплайна
{
//найдем расстояния между соседними точками из массива р
int i,j;
float t[N];
for(i=1;i<n;i++)
t[i]=rasst(p[i-1],p[i]); // функция rasst вычисляет расстояние
//между указанными точками
//составим матрицу m (для вычисления внутренних касательных
//векторов p_1) и массив r
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
float m[N][N], m_1[N][N];
float r[N][2], p_1[N][2];
zer(m,n,n);
//заполнение нулями массива m
m[0][0]=m[n-1][n-1]=1;
r[0][0]=p_b[0]; r[n-1][0]=p_e[0];
r[0][1]=p_b[1]; r[n-1][1]=p_e[1];
for(i=1;i<n-1;i++)
{ m[i][i+1]=t[i];
m[i][i-1]=t[i+1];
m[i][i]=(t[i]+t[i+1])*2;
r[i][0]=(t[i]*(p[i+1][0]-p[i][0])/t[i+1]+
t[i+1]*(p[i][0]-p[i-1][0])/t[i])*3;
r[i][1]=(t[i]*(p[i+1][1]-p[i][1])/t[i+1]+
t[i+1]*(p[i][1]-p[i-1][1])/t[i])*3;
} //i
if(inv(n,m,m_1)) //вычисление обратной матрицы m_1
prodm(p_1,m_1,r,n,n); //произведение
p_1=m_1*r
else return 0;
//если полученная матрица m вырождена
//генерировать точки на кубическом сплайне
int k=0;
//номер генерируемой точки
float f[4], g[4][2];
float tau;
for(i=1;i<n;i++) //номер сегмента
{ for (tau=0.0;tau<1.;tau+=1.0/(ns-1))
{ //установить матрицу смешанной функции f
f[0]=2.*(tau*tau*tau)-3.0*tau*tau+1.0;
f[1]=-2.*(tau*tau*tau)+3.0*tau*tau;
f[2]=tau*(tau*tau-2.0*tau+1.0)*t[i];
f[3]=tau*(tau*tau-tau)*t[i];
//установить геoметрическую матрицу g
for(j=0;j<2;j++)
{ g[0][j]=p[i-1][j];
g[1][j]=p[i][j];
g[2][j]=p_1[i-1][j];
g[3][j]=p_1[i][j];
} //j
//вычислить очередную точку на кривой сплайна
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
prod(pout[k++],f,g,4); // pout[k]=f*g
}//tau
}//i
//сохранить последнюю точку
pout[k][0]=p[n-1][0];
pout[k][1]=p[n-1][1];
return 1;
}//spline3
Литература
1. Роджерс Д., Адамс Дж. Математические основы машинной
графики. М.: Машиностроение, 1980.
2. Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. М.: Мир, 1976.
3. Подбельский В.В. Язык С++. М.: Финансы и статистика, 1996.
4. Кострикин А.И. Введение в алгебру. Ч. 1: Основы алгебры. М.:
Физ.-мат. лит., 2000.
Содержание
Преобразование точек плоскости .......................................................................... 3
Преобразование прямых линий на плоскости .................................................... 7
Преобразование параллельных линий ................................................................. 7
Преобразование пересекающихся линий ............................................................. 8
Преобразование плоских фигур ............................................................................. 9
Комбинирование преобразований ....................................................................... 11
Преобразование единичного квадрата................................................................ 12
Однородные координаты ....................................................................................... 14
Точки в бесконечности ........................................................................................... 16
Двумерное вращение вокруг произвольной оси ............................................... 19
Трехмерные преобразования ................................................................................ 20
Трехмерные изменения масштаба ....................................................................... 21
Трехмерный сдвиг ................................................................................................... 21
Трехмерное вращение............................................................................................. 22
Отображение в пространстве ................................................................................ 22
Пространственный перенос .................................................................................. 23
Приложение .............................................................................................................. 24
Литература ................................................................................................................ 32
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Элементы
компьютерной алгебры
34