Представление графической информации

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

В компьютерной технике применяются цветовые модели RGB, CMYK, HSV (или HSB) и другие. Первая из этих моделей является аддитивной, вторая - субтрактивной, третья - перцепционной, или интуитивной (см. ниже). Данные модели являются аппаратно-зависимыми, синтезируемые цвета в них зависят от параметров устройства. Аппаратно-независимой является, например, цветовая модель CIE Lab. Эта модель, в частности, используется как промежуточная для преобразования цвета из модели RGB в модель CMYK.

Цветовая модель RGB

В цветовой модели RGB основными цветами являются красный, зеленый (green) и синий ( рис. 3.2 (a)). В ней используется аддитивное смешение цветов - метод синтеза цвета, основанный на сложении цветов излучающих объектов. Эта модель используется, например, для синтеза цвета на экране компьютера.

Цветовая модель RGB представляется в виде куба ( рис. 3.2 (b) ) со стороной 1 в системе координат Oxyz ( рис. 3.2 (c)), где координатные оси соответствуют яркости красного, зеленого и синего цвета.

Цвет, который получается вычитанием основного цвета из белого, называется дополнительным цветом для основного (сумма соответствующих компонент основного и дополнительного цветов равна 1). Для красного цвета дополнительным является голубой (cyan), для зеленого - пурпурный (magenta), а для синего - желтый цвет.

(рис 3.2) Модель RGB: (a) основные и дополнительные цвета; (b) цветовой куб; (c) система координат

Вершины куба соответствуют основным и дополнительным цветам, а также черному и белому. Они имеют координаты:

черный (0, 0, 0)

белый (1, 1, 1)

красный (1, 0, 0)

голубой (0, 1, 1)

зеленый (0, 1, 0)

пурпурный (1, 0, 1)

синий (0, 0, 1)

желтый (1, 1, 0)

Оттенки серого, располагаются на главной диагонали куба, соединяющей вершины черного и белого цвета ( рис. 3.2 (c)). Таким образом, цвет с координатами (c, c, c), где 0 < c < 1, является оттенком серого. Чем менее насыщен цвет, тем ближе он к главной диагонали.

Режим кодирования цвета определяется его глубиной - числом бит, отводимых для хранения цвета. Например, в режиме истинного цвета (англ. True Color), или в полноцветном режиме, для кодирования цвета используется 24 бита - по 8 бит для красной, зеленой и синей составляющих. В режиме "высокого" цвета (англ. High Color) для кодирования зеленой компоненты используется 6 бит, а красной и синей - по 5 бит. Для кодирования цвета пикселя черно-белого изображения (с оттенками серого) достаточно 8 бит.

Общее число цветов, которое можно закодировать в режиме True Color, равно $$2^{24}$$, или 16777216, в режиме High Color - $$2^{16}$$, или 65536.

Если цвет имеет координаты x, y и z ( рис. 3.2 (c)), что записывают в виде rgb(x, y, z), то для кодирования в режиме True Color они заменяются округлениями соответственно чисел 255x, 255y и 255z до целых, так что получаются целые компоненты цвета вида $$rgb(N_x, N_y, N_z)$$ (математически цвет представляется с помощью компонент 255x, 255y и 255z без округления до целых).

Рассмотрим примеры кодирования цвета в режиме True Color.

Пример 1. Цвета вершин куба кодируются в виде (hex):

черный	(0, 0, 0)	000000	белый	(255, 255, 255)	ffffff
красный	(255, 0, 0)	ff0000	голубой	(0, 255, 255)	00ffff
зеленый	(0, 255, 0)	00ff00	пурпурный	(255, 0, 255)	ff00ff
синий	(0, 0, 255)	0000ff	желтый	(255, 255, 0)	ffff00

Пример 2. Цвет rgb(0,5, 0,8, 0,02) в 24-битном режиме имеет десятичные целые компоненты rgb(128, 204, 5). Соответственно, его двоичный код выглядит следующим образом:

100000001100110000000101,

или 80cc05 (hex). Цвет принадлежит зеленой цветовой гамме.

Пример 3. Пусть цвет имеет код b1b1b1 (hex). Три компоненты одинаковы, поэтому он является оттенком серого цвета: rgb(177, 177, 177).

Пример 4. Пусть цвет имеет код 2f1ae0 (hex). Тогда он имеет десятичные целые компоненты rgb(47, 26, 224). Соответственно, его дробные компоненты имеют вид: rgb(0,18, 0,1, 0,88) (найдите эту точку на кубе и определите тон).

Если 16-ричные коды каждой компоненты цвета состоят из двух одинаковых цифр, то вместо 6 цифр, представляющих цвет, может использоваться 3 цифры. Например, цвет 33cc99 (hex) может обозначаться как 3c9 (hex).

Вместе с моделью RGB используется также модель RGBA. Дополнительная альфа-компонента (обозначенная A) представляет прозрачность цвета и измеряется в пределах от 0 (полная прозрачность) до 1 (полная непрозрачность), либо указывается в процентах.

Цветовая модель CMYK

Цветовая модель CMYK - это модель субтрактивного синтеза, она используется в полиграфии. Основными цветами в этой модели являются голубой (cyan), пурпурный (magenta) и желтый (yellow). В субтрактивной модели цвет формируется с помощью вычитания основных цветов из белого. Субтрактивное смешение соответствует смешению красок на бумаге. Бумага отражает падающий свет. Наносимые на нее краски одни лучи света поглощают, а другие отражают. Цвет краски определяется лучами, которые не были поглощены. Голубая краска поглощает красный цвет, пурпурная - зеленый, желтая - синий. Поэтому данные поглощаемые цвета являются дополнительными для основных ( рис. 3.3 (a)).

Реальные краски не идеальны, при смешении трех основных красок на бумаге черного цвета не получится. Потому в модель была добавлена четвертая компонента (key) - черный цвет (black).

Пространство цветов в цветовой модели CMYK, как и в модели RGB, представляют на единичном цветовом кубе ( рис. 3.3 (b)), при этом начало координат находится в вершине белого цвета ( рис. 3.3 (c)), а оси координат соответствуют яркостям голубого, пурпурного и желтого цветов. Таким образом, компоненты цвета в модели CMYK имеют значения от 0 до 1; они также указываются в процентах от 1.

(рис 3.3) Модель CMYK: (a) основные и дополнительные цвета;(b) цветовой куб; (c) система координат

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

Пусть r, g и b - компоненты цвета в модели RGB, и $$0 \le r, g, b \le 1$$.

Если, в частности, R, G, B - целые компоненты красного, зеленого и синего цвета, соответственно, такие что $$0 \le R, G, B \le 255$$, то положим $$r=\frac{R}{255}, g=\frac{G}{255}, b=\frac{B}{255}$$.

Обозначим K = max(r, g, b). Пусть $$K \ne 0$$. Тогда цвет $$rgb(r, g, b)$$ имеет в цветовой модели $$CMYK$$ следующие компоненты:

$$c=1-\frac{r}{K}; m=1-\frac{g}{K}; y=1-\frac{b}{K}; k=1-K$$

Если K = 0, то полагают rgb(0, 0, 0) = cmyk(0, 0, 0, 1).

Соответственно, формулы преобразования цветовых компонент из модели CMYK в модель RGB имеют вид: r = (1 - c)(1 - k); g = (1 - m)(1 - k); b = (1 - y)(1 - k).

Для 24-битного представления компоненты цвета в модели RGB равны округлениям до целых значений R = 255r, G = 255g и B = 255b.

Пример 5. Найдем компоненты цвета rgb(202, 124, 50) (оттенок коричневого цвета) в модели CMYK. Имеем: $$r =\frac{202}{255} = 0,792, g = 0,486, b = 0,196$$. Поэтому K = 0,792. Следовательно, c = 0, m = 0,386, y = 0,752, k = 0,208. Таким образом, rgb(202, 124, 50) = rgb(0,79, 0,49, 0,2) = cmyk(0, 0,39, 0,75, 0,21) = cmyk(0%, 39%, 75%, 21%).

Обратное преобразование цвета cmyk(0, 0,386, 0,752, 0,208) в модель RGB приведет к исходному результату.

Пример 6. Пусть цвет в модели CMYK имеет компоненты cmyk(0,3, 0,15, 0,2, 0,45). Тогда 1 - k = 0,55, поэтому компоненты цвета в модели RGB имеют вид: r = 0,7 * 0,55 = 0,385; g = 0,85 * 0,55 = 0,4675; b = 0,8 * 0,55 = 0,44. Для 24-битного представления получаем: R = 98, G = 119, B = 112.

Обратное преобразование из модели RGB в модель CMYK приведет к представлению, которое будет отличаться от исходного: c = 0,176, m = 0, y = 0,059, k = 0,533. Таким образом, один и тот же цвет в модели CMYK может иметь различные представления. Последовательные преобразования из одной модели в другую будут приводить к тем же результатам, если хотя бы одна из компонент c, m и y - нулевая.

Цветовая модель HSV

Цветовая модель HSV (или HSB) представляет цветовое пространство в виде компонент тона, насыщенности и яркости. Модель соответствует субъективному восприятию цвета человеком.

Цветовое пространство модели HSV представляется в виде вертикального конуса с вершиной внизу ( рис. 3.4 (a)). Вершина конуса соответствует черному цвету. Ось яркости направлена вверх, тону соответствует направление вдоль окружности основания конуса, а насыщенность определяется углом между осью яркости и лучом, соединяющим вершину конуса и заданную точку ( рис. 3.4 (b)). Точки оси конуса соответствуют цветам с нулевой насыщенностью - оттенкам серого, от черного до белого.

На окружности основания конуса отмечаются цвета спектра, от красного до фиолетового, к которым добавлены красно-фиолетовые тона. Чистый красный цвет соответствует нулю. Основные цвета моделей RGB и CMYK располагаются в вершинах правильных треугольников, при этом их дополнительные цвета попадают на концы диагоналей. Тон цвета измеряется в углах, от $$0^\circ$$ до $$360^\circ$$, либо от 0 до 1, в направлении против часовой стрелки. Цвета этой окружности имеют максимальные насыщенность и яркость. Показатели насыщенности и яркости имеют значения от 0 до 1, также они могут указываться в процентах от 1.

(рис 3.4) Модель HSV: (a) цветовой конус; (b) система координат

Пример 7. В таблице 3.1 представлены компоненты некоторых цветов в моделях HSV и RGB. Параметр тона указан в градусах, а параметры насыщенности и яркости - в процентах.

Основные цвета в моделях HSV и RGB

Название	HSV	RGB
красный	(0, 100, 100)	(255, 0, 0)
оранжевый	(30, 100, 100)	(255, 127, 0)
желтый	(60, 100, 100)	(255, 255, 0)
зеленый	(120, 100, 100)	(0, 255, 0)
голубой	(180, 100, 100)	(0, 255, 255)
синий	(240, 100, 100)	(0, 0, 255)
фиолетовый	(270, 100, 100)	(127, 0, 255)
пурпурный	(300, 100, 100)	(255, 0, 255)
черный	(0, 0, 0)	(0, 0, 0)
белый	(0, 0, 100)	(255, 255, 255)

Рассмотрим формулы преобразования цветовых компонент из модели RGB в модель HSV. Пусть компоненты цвета rgb(r, g, b) находятся в пределах от 0 до 1. Обозначим компоненты цвета в модели HSV через H, S и V, соответственно, где S и V принадлежат отрезку [0; 1], а H измеряется в градусах от 0 до 360.

Параметр яркости имеет вид: V = max(r, g, b).

Положим $$\Delta = V - min(r, g, b)$$ и $$\delta=\frac{60}{\Delta}$$, для $$\Delta \ne 0$$. Параметры насыщенности (S) и тона (H) находятся следующим образом:

$$s=\begin{cases} 0, V=0\\ \frac{\Delta}{V}, V \ne 0 \end{cases}\\ H=(H'+360) \quad \mod \quad 360,$$

где

$$ H'=\begin{cases} 0, \Delta=0\\ (g-b)\delta, V=r\\ (b-r)\delta+120, V = g\\ (r-g)\delta+240, V=b \end{cases}$$

Пример 8. Пусть цвет в 24-битном представлении имеет компоненты rgb(38, 200, 172) (оттенок бирюзового). После деления составляющих на 255 получим: r = 0,149, g = 0,784, b = 0,6745. Следовательно, $$V = 0,784$$, ,math>\Delta = 0,635,/math>, $$\delta = 94,488$$. Значит, S = 0,81, H = 169,653. Поэтому $$rgb(38, 200, 172) = rgb(0,15, 0,78, 0,67) = hsv(170^\circ, 81\%, 78\%)$$.

Пример 9. Пусть цвет имеет компоненты rgb(255, 20, 150) (темно-розовый). Имеем: r = 1, g = 0,078, b = 0,588. Следовательно, V = 1, S = 0,922, H = - 33,189 + 360 = 326,811. Итак, $$rgb(255, 20, 150) = rgb(1, 0,08, 0,59) = hsv(327^\circ, 92\%, 100\%)$$.

Теперь рассмотрим формулы преобразования из модели HSV в модель RGB. Обозначим компоненты цвета в модели HSV через H, S и V, где H измеряется в градусах от 0 до 360, а S и V имеют значения в пределах от 0 до 1. Пусть r, g и b - компоненты цвета в модели RGB из [0; 1].

Положим$$H_i=[H/60] \mod 6$$ и $$f=H/60-H_i$$.

Обозначим p = (1 - S)V, q = (1 - fS)V и t = (1 - (1 - f)S)V.

Значения r, g и b определяются значением $$H_i$$ (табл. 3.2) - номера одного из шести секторов круга - красно-желтого (0), желто-зеленого (1), зелено-голубого (2), сине-голубого (3), сине-фиолетового (4) и фиолетово-красного (5).

Значения цветовых компонент в модели RGB

$$H_i$$	r	gb
0	V	T	p
1	q	V	p
2	p	V	t
3	p	q	V
4	t	p	V
5	V	p	q

Пример 10. Пусть цвет имеет компоненты $$hsv(70^\circ, 90\%, 70\%)$$ (оттенок салатового). Тогда: H = 70, S = 0,9, V = 0,7.

Следовательно, $$H_i = 1$$, f = 0,167, p = 0,07, q = 0,595, t = 0,175. Поэтому r = 0,595, g = 0,7, b = 0,07. Для 24-битного представления получаем: R = 152, G = 179, B = 18. Таким образом, $$hsv(70^\circ, 90\%, 70\%)= hsv(70, 0,9, 0,7) = rgb(0,6, 0,7, 0,07) = rgb(152, 179, 18)$$.

Пример 11. Найдем компоненты цвета $$hsv(160^\circ, 45\%, 80\%)$$ (оттенок аквамаринового) в модели RGB. Имеем: H = 160, S = 0,45, V = 0,8. Поэтому $$H_i = 2$$, f = 0,667, p = 0,44, q = 0,56, t = 0,68. С помощью табл. 3.2 находим, что r = 0,44, g = 0,8, b = 0,68. Для 24-битного представления, соответственно, получаем: R = 112, G = 204, B = 173. Следовательно, $$hsv(160^\circ, 45\%, 8\0%) = hsv(160, 0,45, 0,8) = rgb(0,44, 0,8, 0,68) = rgb(112, 204, 173)$$.

Цвета в веб

Для представления цвета во Всемирной паутине (World Wide Web), сокр. веб, используются модели RGB и RGBA. Компоненты цвета представляются с помощью шести или трех 16-ричных цифр (см. п. 3.1.4) вида 45fc5a и 3a7 (перед ними ставится знак #) или с помощью структур вида rgb(10, 100, 200) или rgba(250, 150, 50, 0.5), соответственно. Кроме того, в языке разметки HTML цвета обозначаются с помощью названий. В спецификации 4.01 определены названия 16 цветов. Некоторые из них отличаются от тех, что используются в модели RGB. В рис. 3.5 указаны названия основных цветов HTML и их 16-ричные коды.

(рис 3.5) Основные цвета HTML

Цвета, компоненты которых имеют 16-ричные коды 00, 33, 66, 99, cc и ff, называют "безопасными" (англ. safe color). Соответственно, их десятичные цветовые компоненты выглядят следующим образом: 0, 51, 102, 153, 204, 255 (0, 255 и кратные 51). Каждая из трех компонент может принимать 6 значений, поэтому всего имеется 216 "безопасных" цветов.

"Безопасные" цвета используют веб-дизайнеры. Цвета называются "безопасными" потому, что корректно отображаются в любом браузере. Эти цвета составляли "безопасную палитру Netscape" и считались наиболее предпочтительными для отображения в веб-браузере, когда использовались 256-цветные видеокарты (в 90 гг. XX в.). В настоящее время таких предпочтений не имеется (с конца 90 гг.), но палитра "безопасных" цветов все еще бывает востребована.

Пример 12. Имеется 6 "безопасных" оттенков серого цвета, включая белый и черный ( рис. 3.6).

(рис 3.6) "Безопасные" оттенки серого цвета

Пример 13. Для цвета rgb(200, 100, 20) (оттенок шоколадного) ближайшим "безопасным" цветом является rgb(204, 102, 0) (темно-оранжевый).

Пример 14. Для цвета rgb(26, 125, 230) (близок к dodger blue) ближайшим "безопасным" цветом является rgb(51, 102, 255) (близок к royal blue).

Виды графики

Наиболее распространенными видами графики являются растровая, векторная, фрактальная и 3D-графика.

В растровой графике изображение представляется как массив пикселей, пиксель является ее наименьшим элементом. На ( рис. 3.7 показано растровое изображение и его выделенный увеличенный фрагмент.

(рис 3.7) (a) Растровое изображение; (b) выделенный фрагмент

Число пикселей на дюйм (англ. pixel per inch - ppi) называется разрешением изображения. Основными свойствами пикселя являются размер, позиция и цветовая глубина. Растровое кодирование позволяет использовать двоичный код для представления графических данных, так как линейные координаты и яркость каждой точки можно выразить целыми числами.

Векторная графика использует способ представления объектов и изображений, основанный на математическом описании элементарных геометрических объектов таких как точки, линии, многоугольники, сплайны и кривые Безье (см. п. 3.2). Линии и фигуры задаются уравнениями и свойствами - цвет и начертание линии, цвет и способ заполнения фигуры.

Фрактальная графика строит изображение с помощью формул и алгоритмов (п. 3.3).

В трехмерной, или 3D-графике, выводимое на экран изображение является проекцией на плоскость трехмерного изображения. Она подразделяется на полигональную, в которой изображение строится в виде набора поверхностей - полигонов, и воксельную, аналогичную растровой, в которой минимальным элементом является воксель (от англ. volumetric pixel - объемный пиксель).

Примеры векторного, фрактального и трехмерного изображений приведены на рис. 3.8.

(рис 3.8) Изображение (a) векторное; (b) фрактальное; (c) трехмерное

Рассмотрим также примеры других видов графики - пиксельную и символьную.

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

В символьной графике изображение создается в текстовой форме из набора символов таблицы ASCII (рис. 3.9 (b)). Сначала подобные изображения создавались на печатных машинках, затем с помощью программ на ЭВМ. Данное направление называется ASCII-артом. Расширением ASCII-графики является ANSI-графика, в которой для создания изображения используются 224 печатных символа и цвет.

(рис 3.9) Изображение (a) пиксельное; (b) символьное

Пример 15. Ниже приведен ASCII-рисунок и 16-ричные коды символов каждой строки (см. табл. 2.6):

(\___/)			28 5c 5f 5f 5f 2f 29
(=' . '=)			28 3d 27 20 2e 20 27 3d 29
(") _ (")			28 22 29 20 5f 20 28 22 29

Графические примитивы. Кривые Безье

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

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

Основные графические примитивы

В клиентской области окна используется прямоугольная система координат, начало координат которой находится в левом верхнем углу, ось абсцисс направлена вправо, ось ординат - вниз, единицей измерения является пиксель (рис. 3.10). Ниже приведены примеры представления геометрических объек

Точка (point) представляется двумя координатами (x, y).

(рис 3.10) Система координат окна; точка и отрезок

Отрезок (line) определяется двумя точками - его концами.

Прямоугольник (rectangle) может представляться

координатами противоположных вершин ( рис. 3.11 (a)), правой верхней и левой нижней или наоборот;

координатами левой верхней вершины, а также шириной (width) и высотой (height) прямоугольника (рис. 3.11 (b)).

(рис 3.11) Представление прямоугольника и эллипса: (a) противоположными вершинами; (b) левой верхней вершиной, шириной и высотой; (c) описанным прямоугольником

Шириной прямоугольника называется длина его горизонтальной стороны, а высотой - длина вертикальной.

Эллипс (ellipse) определяется описанным прямоугольником (рис. 3.11 (c)), иногда - центром и осями.

Дуга (arc) и сектор (pie) эллипса рис. 3.12 представляются прямоугольником, описанным вокруг эллипса (см. выше п. 3), а также следующими двумя параметрами:

двумя точками на границе прямоугольника: дуга (сектор) эллипса заключается между лучами, которые соединяют центр прямоугольника и эти точки, в направлении против часовой стрелки ( рис. 3.12 (a));

величиной начального угла ($$\alpha$$) и угла раствора дуги ($$\beta$$) в градусах; начальный угол откладывается от точки касания эллипса правой стороны прямоугольника; углы откладываются в направлении по часовой стрелке (рис. 3.12 (b)).

(рис 3.12) Представление дуги (a) двумя точками; (b) двумя углами; (c) сектор эллипса

Многоугольник (polygon) и ломаная (polyline) представляются массивом (списком) точек (рис. 3.13).

(рис 3.13) (a) Многоугольник; (b) ломаная

Скругленный прямоугольник (rounded rectangle), или прямоугольник с закругленными углами, определяется параметрами прямоугольника (см. выше), а также шириной и высотой эллипса (рис. 3.14 (a)), который используется для "скругления" (рис. 3.14 (b)): вместо угла отображается дуга эллипса - его четвертая часть (рис. 3.14 (c)).

(рис 3.14) Скругление прямоугольника: (a) эллипс; (b) скругление; (c) прямоугольник с закругленными углами

Шириной эллипса называется длина его горизонтальной оси, а высотой - длина вертикальной оси.

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

Кривые Безье (Bezier curve) и сплайны (spline) представляются массивами (списками) точек (см. ниже). На рис. 3.15 показаны 4 точки (рис. 3.15 (a)) и построенные по ним кривая Безье (рис. 3.15 (b)), сплайн (curve) (рис. 3.15 (c)) и замкнутый сплайн (closed curve) (рис. 3.15 (d)).

(рис 3.15) Кривые: (a) исходные точки; (b) кривая Безье; (c) сплайн; (d) замкнутый сплайн

Кривые на плоскости

Рассмотрим примеры построения кривых на плоскости.

Через две различные точки плоскости $$(x_0, y_0)$$ и $$(x_1, y_1)$$, такие что$$x_0 \ne x_1$$, можно провести прямую вида y = ax + b. Имеем:

$$\begin{cases} y_0=ax_0_b,\\ y_1=ax_1+b. \end{cases} $$

Если $$x_0 \ne x_1$$, то эта система относительно a и b имеет единственное решение. Если $$x_0 = x_1$$, то уравнение прямой имеет вид: $$x = x_0$$. В общем виде прямая описывается уравнением $$ (y - y_0)(x_1 - x_0) = (x - x_0)(y_1 - y_0) $$.

В параметрическом виде отрезок, соединяющий точки $$ (x_0, y_0) $$ и $$ (x_1, y_1) $$, определяется следующим образом:

$$\begin{cases} x(t)=(x_1-x_0)t+x_0;\\ y(t)=(y_1-y_2)t+y_0, \end{cases} $$

где $$0 \let \le1$$. Имеем: $$x(0) = x_0, y(0) = y_0, x(1) = x_1, y(1) = y_1$$. В векторной форме данное соотношение записывается в виде:

$$r(t)(P_1-P_0)t+P_0,$$

где

$$r(t)={x(t) \choose y(t)}, P_o={x_0 \choose y_0}, P_1={x_1 \choose y_1}$$

Аналогично, через три точки плоскости $$ (x_0, y_0), (x_1, y_1) $$ и $$ (x_2, y_2) $$, абсциссы которых попарно различны, можно провести единственную кривую второго порядка, которая описывается многочленом второй степени (рис. 3.16 (a)). Его коэффициенты находятся из системы линейных уравнений относительно неизвестных a, b и c вида

$$\begin{cases} y_0=ax_0^2+bx_0+c,\\ y_1=ax_1^2+bx_1+c,\\ y_2=ax_2^2+bx_2+c \end{cases} $$

Определителем $$\Delta$$ данной системы является определитель Вандермонда порядка 3, так что $$\Delta = (x_1 - x_0)(x_2 - x_0)(x_2 - x_1) $$.

(рис 3.16) (a) Парабола, проведенная через 3 точки; (b) кубическая парабола, проведенная через 4 точки

В общем случае, через n + 1 точку плоск n, который определяется однозначно, например, если абсциссы этих точек попарно различны. На рис. 3.16 (a) и (b) показаны примеры кривых, описываемых с помощью многочленов второй и третьей степени, которые проходят через 3 и через 4 заданные точки, соответственно.

Кривые на плоскости могут быть заданы

явным образом с помощью одной или нескольких формул вида y = f(x), например $$y=\frac12x^3-2x^2+x+1$$ ( рис. 3.17 (a));

неявно, с помощью неявной функции или функций вида F(x, y) = 0, например $$(x - 2)^2 + 2(y - 1)^2 = 16$$ (рис. 3.17 (b));

параметрическим образом, например $$x(t) = t^3 - 2t$$, $$y(t) = t^2 - 2$$, где - $$-2 \le t \le 2$$ (рис. 3.17 (c)).

(рис 3.17) Задание кривых на плоскости: (a) явно; (b) неявно; (c) параметрически

Кривые, приведенные на рис. 3.17 (a) и (c), являются кубическими, а кривая на рис. 3.17 (b) - квадратичной.

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

Кривые Безье

Положим $$b_{k,n}(c)=C_n^kt^k(1-t)^{n-k}$$, где $$C_n^k=\frac{n!}{k!(n-k)!}$$, k и n - целые, $$n \ge 0, 0 \le k \le n$$, а t принадлежит множеству действительных чисел.

Полиномы $$b_{k, n}(t) $$ называются полиномами Берштейна.

Пусть $$P_0, P_1, \dots, P_n$$ - попарно различные точки плоскости, такие что $$P_j={x_j \choose y_j}$$, для $$j = 0, 1, \dots, n$$.

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

$$r(t)=B_n(P_0,P_1,\dots, P_n;t)=\sum_{k=0}^{n}B_{k,n}(t)P_k,$$

для $$0 \let \le1$$, где $$r(t) $$ - координаты точек кривой Безье, соответствующих параметру t. Кривая названа по имени одного из ее изобретателей Пьера Безье (1962).

Заметим, что при t = 0 получается точка $$P_0$$, а при t = 1 - точка $$P_n$$.

Если точка одна, то $$B_0(P_0; t) \equiv P_0$$, так как $$b_{0, 0}(t) \equiv 1$$. Рассмотрим подробнее кривые Безье для n = 1, 2, 3.

Пусть n = 1, и для построения кривой используются точки $$P_0$$ и $$P_1$$. Тогда кривая Безье описывается следующим образом:

$$r(t) = B_1(P_0, P_1; t) = (1 - t)P_0 + tP_1, $$

где $$t \in [0; 1]$$. В матричной форме кривую можно представить в виде

$$B_1(P_0,P_1;t)=(1 \quad t)\begin{pmatrix} 10\\ -11 \end{pmatrix}{P_0 \choose P_1}$$

Координаты точек кривой удовлетворяют соотношению $$r(t) = (P_1 - P_0)t + P_0$$ (см. п. 3.2.2), так что кривая Безье представляет собой отрезок, соединяющий точки $$P_0$$ и $$P_1$$ (рис. 3.18).

(рис 3.18) Построение кривой Безье по 2 точкам

Пусть n = 2. Тогда кривая Безье описывается следующим образом: $$r(t) = B_2(P_0, P_1, P_2; t) = (1 - t)^2P_0 + 2t(1 - t)P_1 + t^2P_2$$, где $$t \in [0; 1]$$, или, в матричной форме,

$$B_2(P_0,P_1,P_2,P_3;t)=(1 \quad t \quad t^2)\begin{pmatrix} 100\\ -220\\ 1-21\end{pmatrix} \begin{pmatrix} P_0\\ P_1\\ P_2\end{pmatrix}$$

Нетрудно заметить, что кривые Безье, построенные по трем точкам, являются квадратичными кривыми. Они используются, например, для создания шрифтов True Type.

Пример 16. Найдем уравнение кривой Безье второго порядка, которая строится по точкам $$P_0 = (0; 0), P_1 = (1; 1)$$ и $$P_2 = (2; 0) $$. Имеем:

$$ \left(\! \begin{array}{c} x \\ y \end{array} \!\right) (t) = (1-t)^2\left(\! \begin{array}{c} 0 \\ \end{array} \!\right)+2t(1-t) \left(\! \begin{array}{c} 1 \\ 1 \end{array} \!\right)+t^2 \left(\! \begin{array}{c} 2 \\ 2 \end{array} \!\right) $$

Поэтому $$x(t) = 2t(1 - t) + 2t^2 = 2t$$; y(t) = 2t(1 - t), где $$0 \le t \le 1$$. Следовательно, координаты x и y точек кривой Безье связаны соотношением:

$$y=x\left(1-\frac{x}{2} \right)=x-\frac{1}{2}x^2=-\frac{1}{2}(x-1)^2+\frac{1}{2},$$

где $$0 \le x \le 2$$ (рис. 3.19).

(рис 3.19) Кривая Безье 2 порядка для точек..

В компьютерной графике используются кубические кривые Безье, которые строятся по 4 точкам. Итак, пусть n = 3. Тогда кривая Безье задается формулой $$r(t) = B_3(P_0, P_1, P_2, P_3; t) = (1 - t)^3P_0 + 3t(1 - t)^2P_1 + 3t^2(1 - t)P_2 + t^3P_3$$, где $$t \in [0; 1]$$. Соответственно, матричная форма имеет вид:

$$B_3(P_0,P_1,P_2,P_3;t)=(1t \quad t^2 \quad t^3)\begin{pmatrix} 1000\\ -3300\\ 3-630\\ -13-31\end{pmatrix} \begin{pmatrix} P_0\\ P_1\\ P_2\\ P_3\end{pmatrix}$$

В общем случае столбец j матрицы порядка n + 1 кривой Безье $$B_n(P_0, P_1, \dots, P_n; t) $$ образуют коэффициенты при $$1, t, \dots, t^n$$ полинома $$b_{j,n}$$.

Найдем значения производной кривой Безье в точках $$P_0$$ и $$P_n$$. Для n > 0 и $$t \in [0; 1]$$ имеем (см. ниже утверждение 3):

$$r'(t)n\sum_{k=0}^{n-1}b_{k,n-1}(t)(P_{k+1}-P_k)$$

Следовательно, $$r' (0) = n(P_1 - P_0) $$ и $$r'(1) = n(P_n - P_{n - 1})$$.

Производная в точке $$t_0$$, если существует, находится в виде: $$y'_x(1)=\frac{y' (t_0)}{x'(t_0)}$$. Поэтому $$y'_x(0)=\frac{y_1-y_0}{x_1-x_0}$$, если $$x_1 \ne x_0$$, и $$y'_x(1)=\frac{y_n-y_{n-1}}{x_n-x_{n-1}}$$, если $$x_n \ne x_{n - 1}$$. Таким образом, кривая Безье касается в точке $$P_0$$ отрезка $$[P_0; P_1] $$, а в точке $$P_n$$ - отрезка $$ [P_n; P_{n - 1}]$$.

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

Утверждение 1. Для $$n \ge 1$$ выполняется соотношение

$$B_n(P_0, P_1, \dots, P_n; t) = B_1(B_{n - }1(P_0, \dots, P_{n - 1}; t), B_{n - 1}(P_1, \dots, P_n; t); t) $$

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

$$B_1(B_{n-1}(P_0,\dots, _{n-1};t), B_{n-1}(P_1,\dots, P_n;t);t)=\\ =(1-t)B_{n-1}(P_0,\dots, P_{n-1};t)+tB_{n-1}(P_1,\dots, P-n;t)=\\ =\sum_{k=0}^{n-1}C_{n-1}^{k}t^k(1-t)^{n-k}P_k+\sum_{k=0}^{n-1}C_{n-q}^kt^{k+1}(1-t)^{n-1-k}P_{k+1}=\\ =(1-t)^nP_0+\sum_{k=1}^{n-1}(C_{n-1}^k+C_{n-1}^{k-1})t^k(1-t)^{n-k}P_k+t^nP_n=\\ =\sum_{k=0}^{n}C_n^kt^k(1-t)^{n-k}P_k=B_n(P_0, P_1, \dots, P_n;t). $$

Из утверждения 1 следует, что кривая Безье не выходит за пределы выпуклой оболочки точек $$P_0, P_1, \dots, P_n$$.

Утверждение 2. Для $$n \ge 1 $$имеет место равенство:

$$B_n(P_0, P_1, \dots, P_n; t) = B_{n - 1}(B_1(P_0, P_1; t), B_1(P_1, P_2; t), \dots, B_1(P_{n - 1}, P_n; t); t)$$

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

$$B_{n-1}(B_1(P_0, P_1;t),B_1(P_1, P_2;t),\dots, B_1(P_{n-1}, P_n;t);t)=\\ =\sum_{k=0}^{n-1}C_{n-1}^k(1-t)^{n-1-k}B_1(P_k, P_{k+1};t)=\\ =\sum_{k=0}^{n-1}C_{n-1}^kt^k(1-t)^{n-1-k}((1-t)P_k+tP_{k+1})=\\ =\sum_{k=0}^{n-1}C_{n-1}^kt^k(1-t)^{n-k}P_k+\sum_{k=0}^{n-1}t^{k+1}(1-t)^{n-1-k}P_{k+1}=\\ =(1-t)^nP_0+\sum_{k=0}^{n-1}(C_{n-1}^k+C_{n-1}^{k-1})t^k(1-t)^{n-k}P_k+t^nP_n=\\ =\sum_{k=0}^nC_n^kt^k(1-t)^{n-k}P_k=B_n(P_0, P_1, \dots, P_n;t)$$

На утверждении 2 основан метод приближенного построения кривых Безье, созданный Полем де Кастельжо, еще одним изобретателем этих кривых (1959). Например, из утверждения 2 следует, что точка кривой Безье порядка n, соответствующая t = 0,5, совпадает при t = 0,5 с точкой кривой Безье порядка n - 1, построенной по точкам $$M_0, M_1, \dots, M_{n - 1}$$, которые являются серединами отрезков, соединяющих точки $$P_0$$ и $$P_1, P_1$$ и $$P_2, \dots, P_{n - 1}$$ и $$P_n$$, соответственно.

Пример 17. Рассмотрим точки A, B, и C квадратичной кривой Безье, построенной в примере 16 (см. рис. 3.20), соответствующие значениям 0,25, 0,5 и 0,75 параметра t. По утверждению 2,

$$B_2(P_0, P_1, P_2; t) = B_1(B_1(P_0, P_1; t), B_1(P_1, P_2; t); t). $$

Кривыми Безье первого порядка, построенными по точкам $$P_0$$ и $$P_1$$, а также $$P_1$$ и $$P_2$$, являются соответственно отрезки $$P_0P_1$$ и $$P_1P_2$$ ( рис. 3.20). Значениям 0,25, 0,5 и 0,75 параметра t на них соответствуют точки $$Q_0, M_0, R_0$$ и $$Q_1, M_1, R_1$$, которые делят эти отрезки на 4 равные части. Имеем:

$$B_2(P_0, P_1, P_2; 0,25)= B_1(B_1(P_0, P_1; 0,25), B_1(P_1, P_2; 0,25); 0,25) = B_1(Q_0, Q_1; 0,25);\\ B_2(P_0, P_1, P_2; 0,5) = B_1(M_0, M_1; 0,5);\\ B_2(P_0, P_1, P_2; 0,75)= B_1(R_0, R_1; 0,75).$$

Следовательно, точка A квадратичной кривой Безье совпадает с точкой отрезка $$Q_0Q_1$$, которая отстоит на четверть от его конца $$Q_0$$, точка B - с серединой отрезка $$M_0M_1$$ и точка C - с точкой отрезка $$R_0R_1$$, отстоящей на три четверти от его конца $$R_0$$.

(рис 3.20) Точки A, B и C кривых Безье второго и первого порядков

Рассмотрим примеры приближенного построения кривых Безье. Будем использовать 3 вспомогательные точки, которые соответствуют значениям 0,25, 0,5 и 0,75 параметра t.

Пример 18. Построим кривую Безье по 3 точкам $$P_0, P_1$$ и $$P_2$$. Соединим отрезками точки $$P_0$$ и $$P_1$$, а также $$P_1$$ и $$P_2$$, и разделим каждый отрезок на 4 равные части, отметив на них по 3 точки - концы этих частей. Занумеруем эти точки так, как показано на 3.21рис..

Соединим отрезками точки с равными номерами и отметим на первом из них точку A, отстоящую на четверть от первого конца отрезка, на втором - середину B и на третьем отрезке - точку C, отстоящую на три четверти от первого его конца.

Теперь проведем кривую, которая проходит через точки $$P_0$$, A, B, C и $$P_2$$ так, чтобы она касалась построенных отрезков и не выходила за их пределы, как показано на рисунке 3.21.

(рис 3.21) Построение кривой Безье по 3 точкам

Пример 19. Построим кривую Безье по 4 точкам $$P_0, P_1, P_2$$ и $$P_3$$, как показано на рис. 3.22. Как и ранее, соединим точки $$P_0$$ и $$P_1, P_1$$ и $$P_2, P_2$$ и $$P_3$$ отрезками и разделим каждый отрезок на 4 равные части, занумеровав точки деления так, как показано на рисунке. Последовательно соединим отрезками точки с равными номерами.

На первой паре отрезков отметим точки, отстоящие от первого конца отрезка на четверть, соединим их и на новом отрезке отметим точку A, отстоящую на четверть от первого конца отрезка. Точно так же, соединим середины второй пары отрезков и на новом отрезке отметим середину B. На третьей паре отрезков отметим точки, отстоящие от начала на три четверти, соединим их и на новом отрезке отметим точку C, отстоящую на три четверти от первого его конца.

(рис 3.22) Построение кривой Безье по 4 точкам

Проведем кривую, которая проходит через точки $$P_0, A, B, C$$ и $$P_3$$ и касается в них построенных отрезков, но не выходит за их пределы.

Утверждение 3. Для n > 0 и $$t \in [0; 1]$$ выполняется соотношение

$$\frac{d}{dt}\sum_{k=0}^{n}b_{k,n}(t)P_k=n\sum_{k=0}^{n-1}B_{k,n-1}(t)(P_{k+1}-P_k)$$

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

$$\frac{d}{dt}\sum_{k=0}^{n}b_{k,n}(t)P_k =(\sum_{k=0}^nC_n^kt^k(1-t)^{n-k}P_k)'=\\ =\sum_{k=0}^nC_n^k(kt^{k-1}(1-t)^{n-k}-(n-k)t^k(1-t)^{n-k-1}P_k=\\ =\sum_{k=0|^nC_n^kkt^{k-1}(1-t)^{n-k}P_k-\sum_{k=0}^n-1}C_k^n(n-k)t^k(1-t)^{n-k-1}P_k=\\ =\sum_{k=0}^{n-1}(C_n^{k+1}(k+1)P_{k+1}-C_n^k(n-k)P_k)t^k(1-t)^{n-k-1}=\\ =n\sum_{k=0}^{n-1}C_{n-1}^kt^k(1-t)^{n-k-1}(P_{k+1}-P_k),$$

так как $$C_n^{k+1}(k+1)=nC_n^k(n-k). $$

Следствие. Для n > 1 является верным равенство

$$ (B_n(P_0, P_1, \dots, P_n; t))' = B_{n - 1}(n(P_1 - P_0), n(P_2 - P_1), \dots, n(P_n - P_{n - 1}); t).$$

Годографом параметрической кривой r(t) = (x(t); y(t)), компоненты которой являются полиномами, называется кривая $$r(t) = (x'(t); y'(t)) $$.

Таким образом, кривая Безье, построенная по n точкам $$n(P_1 - P_0), n(P_2 - P_1), \dots, n(P_n - P_{n - 1})$$, является годографом исходной кривой Безье, построенной по точкам $$P_0, P_1, \dots, P_n$$.

Пример 20. Годографом квадратичной кривой Безье

$$x(t) = 2t;\\ y(t) = 2t(1 - t), $$

где $$0 \le t \le 1$$

(см. пример 16), является кривая x(t) = 2; y(t) = 2 - 4t, при $$0 \le t \le 1$$, которая представляет собой отрезок прямой x = 2 для - $$2 \le y \le 2$$ (рис. 3.23).

(рис 3.23) Квадратичная кривая Безье и ее годограф - отрезок прямой

Пример 21. На рис. 3.24 показаны кубическая кривая Безье (справа) и ее годограф - квадратичная кривая Безье (слева).

(рис 3.24) Кривая Безье (справа) и ее годограф (слева)

Отметим также, что в 3D-графике, кроме кривых Безье, используются поверхности Безье.

B-сплайны

B-сплайны являются обобщениями кривых Безье.

Последовательность действительных чисел $$T = (t_0, t_1, \dots, t_m)$$, таких что $$t_0 \le t_1 \le \dots \le t_m$$, называется узловым вектором, а сами эти числа - узлами.

Для заданного узлового вектора T положим:

$$N_{i,0}(t)=\begin{cases} 1, t \in [t_i;t_{i+1})\\ 0, t \notin [t_i;t_{i+1}); \end{cases}\\ N_{i,k}(t)=\frac{t-t_i}{t_{i+k}-t_i}N_{I,k-1}(t)+\frac{t_{i+k+1}-t}{t_{i+k+1}-t_{i+1}}N_{i+1,k-1}(t),$$

для k > 0 (считается, что $$\frac00=0$$).

Функции $$N_{i,k}(t)$$ называются базисными функциями степени k.

Например, при k = 1 и $$i \le1$$ имеем:

$$N_{0,1}(t)=\frac{t-t_0}{t_1-t_0}N_{0,0}(t)=\frac{t_2-t}{t_2-t_1}N_{1,0}(t),\\ N_{1,1}(t)=\frac{t-t_1}{t_3-t_1}N_{1,0}(t)+\frac{t_3-t}{T_3-t_2}N_{2,0}(t)$$

Пусть $$P_0, P_1, \dots, P_n$$ - попарно различные точки плоскости.

B-сплайном, или базисным сплайном степени k называется кривая

$$r(t)=\sum_{i=0}^{n}N_{i,k}(t)P_i,$$

для $$n \ge k$$ и $$t \in [t_k; t_{n + 1}]$$, где базисные функции определены на узловом векторе T, который содержит n + k + 2 узлов: $$T = (t_0, t_1, \dots, t_{n + k + 1})$$.

Пример 22. Пусть n = k = 1 и T = (0, 0, 1, 1), так что имеются две точки $$P_0$$ и $$P_1$$ и узлы $$t_0 = t_1 = 0, t_2 = t_3 = 1$$. Тогда

$$N_{0,0}(t)=N_{2,0}(t)=0,$$

для $$t \in [0;1]$$

$$N_{1,0}(t)\begin{cases} 1, \text{если}\; t \in [0;1);\\ 0, \text{если}\; t \notin [0;1) \end{cases}$$

По приведенным выше формулам получаем, что для $$t \in [0; 1]$$

$$N_{0,1}(t)=1-t$$

и

$$N_{1,1}(t)=t$$

Поэтому B-сплайн первой степени для точек $$P_0$$ и $$P_1$$ описывается в виде $$r(t) = N_{0,1}(t)P_0 + N_{1,1}(t)P_1 = (1 - t)P_0 + tP_1$$, и для $$t \in [0; 1]$$ представляет собой отрезок, соединяющий точки $$P_0$$ и $$P_1$$.

В общем случае B-сплайн степени k, для $$k \ge 1$$, совпадает при $$t \in [0; 1]$$ с кривой Безье, если n = k, а узловой вектор имеет вид:

$$T=\underbrace{(0,\dots,0,}_{k=1} \underbrace{1,\dots,1)}_{k=1}$$

Пример 23. Пусть n = 3, k = 1 и T = (0, 0, 1, 2, 3, 3). Построим B-сплайн первой степени по 4 точкам $$P_0, P_1, P_2$$ и $$P_3$$:

$$r(t)=N_{0,1}(t)P_0+N_{1,1}(t)P_1+N_{2,1}(t)P_2+N_{3,1}(t)P_3$$

Имеем: $$t_0 = t_1 = 0$$, $$t_2 = 1$$, $$t_3 = 2$$, $$t_4 = t_5 = 3$$. Следовательно,

$$N_{0,0}(t)=N_{4,0}(t)=0$$

для $$t \in [0;3]$$

$$ N_{1,0}(t)\begin{cases} 1, t \in [0;1);\\ 0, t \notin [0;1); \end{cases}\\ N_{2,0}(t)\begin{cases} 1, t \in [1;2);\\ 0, t \notin [1;2); \end{cases}\\ N_{3,0}(t)\begin{cases} 1, t \in [2;3);\\ 0, t \notin [2;3); \end{cases}$$

Поэтому

$$ N_{0,1}(t)=(1-t)N_{1,0}(t);\\ N_{1,1}(t)=tN_{1,0}(t)+(2-t)N_{2,0}(t) $$

Далее,

$$N_{2,1}=\frac{t-t_2}{t_3-t_2}N_{2,0}(t)=\frac{t_4-t}{t_4-t_3}N_{3,0}(t);\\ N_{}(t)=\frac{t-t_3}{t_4-t_3}N_{3,0}(t)+\frac{t_5-t}{t_5-t_4}N_{4,0}(t)$$

В нашем примере

$$N_{2,1}(t)-(t-1)N_{2,0}(t)+(3-t)N_{3,0}(t);\\ N_{3,1}(t)=(t-2)N_{3,0}(t)$$

Таким образом, B-сплайн описывается в виде:

$$ r(t)\begin{cases} (1-t)P_o+tP_1, t \in [0;1);\\ (2-t)P_1+(t-1)P_2, t \in [1;2)\\ (3-t)P_2+(t-2)P_3, t \in [2;3) \end{cases}$$

При $$t \in [0; 3]$$ он представляет собой ломаную с вершинами $$P_0, P_1, P_2$$ и $$P_3$$ (рис. 3.25).

(рис 3.25) B-сплайн первой степени с узлами (0, 0, 1, 2, 3, 3)

Такая же ломаная получается при $$t \in [1; 4]$$, если в качестве узлового вектора взять (0, 1, 2, 3, 4, 5).

Пример 24. Пусть n = 3, k = 2 и T = (0, 0, 0, 1, 3, 3, 3). Построим B-сплайн второй степени по 4 точкам $$P_0, P_1, P_2$$ и $$P_3$$:

$$r(t)=N_{0,2}(t)P_0+N_{1,2}(t)P_1+N_{2,2}(t)P_2+N_{3.2}(t)P_3$$

Имеем: $$t_0 = t_1 = t_2 = 0$$, $$t_3 = 1, t_4 = t_5 = t_6 = 3$$. Поэтому

$$N_{0,0}(t)=N_{1,0}(t)=N_{4,0}(t)=N_{5,0}(t)=0;\\ N_{2,0}(t)\begin{cases} 1,t \in[0;1);\\ 0, t \notin [0;1); \end{cases}\\ N_{3,0}(t)=\begin{cases} 1, t \in [1;3);\\ 0, t \notin [1;3). \end{cases}$$

Следовательно, $$N_{0,1}(t)=0; N_{1,1}(t)=(1-t) N_{2,0}(t); $$

$$N_{2,1}(t)=tN_{2,0}(t)+\frac12(3-t)N_{3,0}(t);\\ N_{3,1}(t)=\frac12(t-1)N_{3,0}(t)$$

Далее,

$$ N_{0,2}(t)=\frac{t-t_0}{t_2-t_0}N_{0,1}(t)+\frac{t_3-t}{t_3-t_0}N_{1,1}(t)\\ N_{1,2}(t)=\frac{t-t_1}{t_3-t_1}N_{1,1}(t)+\frac{t_4-t}{t_4-t_2}N_{2,1}(t)\\ N_{2,2}(t)=\frac{t-t_2}{t_4-t_2}N_{2,1}(t)+\frac{t_5-t}{t_5-t_3}N_{3,1}(t)\\ N_{3,2}(t)=\frac{t-t_3}{t_5-t_3}N_{3,1}(t)+\frac{t_6-t}{t_6-t_4}N_{4,1}(t)\\ N_{4,1}(t)=\frac{t-t_4}{t_5-t_4}N_{4,0}(t)+\frac{t_6-t}{t_6-t_5}N_{5,0}(t)$$

Поэтому

$$N_{0,2}(t)=(1-t)^2N_{2,0}(t);\\ N_{1,2}(t)=\frac{2}{3}t(3-2t)N_{2,0}(t)+\frac16(3-t)^2N_{3,0}(t);\\ N_{2,2}(t)=\frac{1}{3}(t-1)^2N_{2,0}(t)+\frac{1}{12}(3-t)(5t-3)N_{3,0}(t);\\ N_{3,2}(t)=\frac{1}{4}(t-1)^2N_{3,0}(t),$$

так как $$N_{4,0}(t)=0$$

Таким образом, B-сплайн второй степени для точек $$P_0, P_1, P_2$$ и $$P_3$$ с узловым вектором (0, 0, 0, 1, 3, 3, 3) определяется в виде

$$r(t)=N_{0,2}(t)P_0+N_{1,2}(t)P_1+N_{2,2}(t)P_2+N_{3,2}(t)P_3=\\ =\begin{cases} (1-t)^2P_0+\frac23t(3-2t)P_1+\frac13t^2P_2, t \in [0;1),\\ \frac16(3-t)^2P_1+\frac{1}{12}(3-t)(5t-3)P_2+\frac14(t-1)^2P_3, t \in [1;3). \end{cases}$$

На рис. 3.26 показан квадратичный B-сплайн, который построен по приведенной выше формуле для 4 точек, отмеченных на рисунке.

(рис 3.26) B-сплайн второй степени с узлами (0, 0, 0, 1, 3, 3, 3)

Различные виды B-сплайнов определяются узловыми векторами. В 3D-графике используются также сплайн-поверхности.

Фракталы

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

Ниже рассматриваются примеры построения различных видов фракталов - геометрических, с помощью описания L-систем (п. 3.3.1) и векторного предста

Черепашья графика. L-системы

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

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

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

Примером описания геометрических объектов, которые строятся с помощью рисующей черепахи, являются L-системы. Понятие L-системы было введено биологом Аристидом Линденмайером (1968) [11]. Фигура описывается в виде слова, заданного в некотором алфавите в соответствии с определенной грамматикой. Каждая буква алфавита соответствует некоторому действию рисующей черепахи. Поэтому данное слово определяет и саму процедуру построения изображения фигуры с помощью черепашьей графики.

Рассмотрим следующий алфавит:

F - смещение на заданный интервал с оставлением следа;

f - смещение на заданный интервал без следа;

+ - поворот на заданный угол направо;

- - поворот на заданный угол налево;

[ - начало записи действий в стек;

] - окончание записи действий в стек;

X - вспомогательный символ.

Например, квадрат можно представить в виде слова F+F+F+F, где угол поворота - прямой (рис. 3.27 (a)), а правильный треугольник - в виде слова F+F+F, где угол поворота равен $$120^\circ$$ (рис. 3.27 (b)).

(рис 3.27) (a) Квадрат; (b) правильный треугольник

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

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

Если в виде L-системы описывается фрактал, то для построения его приближения, указывается также число итераций $$n$$, а сам фрактал получается в пределе при $$n \to \infty$$. Нулевая итерация соответствует аксиоме. Приближения фрактала называются фрактальными фигурами.

Пример 25. Рассмотрим описание в виде L-системы кривой Коха:

угол: $$\frac{\pi}{3}$$;

аксиома: F;

правило: $$F \to F-F++F-F$$.

Шаг итерации состоит в замене каждого символа F в слове, полученном на предыдущем шаге, на строку F-F++F-F.

Пусть $$f_n$$ - кривая, полученная на шаге n, для $$n \ge 0$$. Кривая Коха является пределом последовательности $$f_0, f_1, f_2, \dots$$ при $$n \to \infty$$. Это непрерывная кривая, которая не имеет касательной ни в одной точке. Элемент $$f_n$$ называется n-м приближением кривой Коха (рис. 3.28).

(рис 3.28) Начальные приближения кривой Коха

Рассмотрим первые 3 приближения кривой Коха. Кривая $$f_0$$ соответствует аксиоме F и представляет собой отрезок ( рис. 3.28 (a)). Кривая $$f_1$$ соответствует слову F-F++F-F (рис. 3.28 (b)), кривая $$f_2$$ - слову

F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F

(рис. 3.28 (c)), кривая $$f_3$$ показана на рис. 3.28 (d).

Пусть $$i_n$$ - число отрезков, содержащихся в фигуре $$f_n$$, и $$l_n$$ -длина слова, описывающего фигуру на шаге n, т. е. число символов, которое содержит это слово. В соответствии с грамматикой имеем:

$$i_n = 4^n, $$ для $$n = 0, 1, 2, \dots$$; $$l_0 = 1, l_n = 4 * l_{n - 1} + 4, n = 1, 2, \dots$$

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

$$l_n=\frac73*4^n-\frac43$$

для $$n=0,1,2, \dots$$

Например, фигура, полученная на шаге 4, состоит из 256 отрезков, а описывающая ее строка - из 596 символов.

Если фигуру можно разбить на N частей, каждая из которых может быть получена из целой фигуры, конгруэнтной исходной, преобразованием подобия с коэффициентом r, то размерность подобия D фигуры удовлетворяет соотношению $$N * r^D = 1$$, и, следовательно,

$$D=\frac{\ln N}{\ln r^{_-1}}}$$

Найдем, например, размерность подобия кривой Коха. На каждом шаге итерации фигуру можно разбить на 4 части, каждая из которых конгруэнтна фигуре, подобной всей фигуре, полученной на предыдущем шаге, с коэффициентом подобия $$\frac{1}{3}$$. Поэтому размерность подобия кривой Коха находится следующим образом:

$$\frac{\ln 4}{\ln 3}\approx 1,26$$

В общем случае размерность подобия фрактальных фигур, в отличие от "обычных", также не является целым числом. Разобьем, например, отрезок на n равных частей, где n > 0. Каждая часть подобна исходной фигуре с коэффициентом подобия $$n^{- 1}$$. Поэтому размерность подобия отрезка равна 1. Аналогично, разобьем квадрат на n одинаковых квадратов. Тогда $$n = k^2$$ для некоторого натурального k. При этом каждый из n квадратов будет подобен исходному квадрату с коэффициентом подобия $$k^{- 1}$$. Поэтому размерность подобия квадрата равна $$\frac{\ln k^2}{\ln k}=2$$.

Пример 26. Рассмотрим фрактал "дерево" (рис. 3.29). Его описание в виде L-системы имеет вид:

угол: $$\frac{\pi}{7}$$

аксиома: F;

правило: F -> F[+F]F[-F]F.

На первом шаге итерации сначала проводится отрезок заданной длины; затем выполняются действия, описанные в квадратных скобках, т. е. в "стеке" - делается поворот направо на угол $$\frac{\pi}{7}$$ и проводится еще один отрезок; после этого черепаха возвращается в положение, которое у нее было перед "стеком", и проводится следующий отрезок; затем выполняется поворот налево на угол $$\frac{\pi}{7}$$ и снова проводится отрезок; после этого черепаха возвращается к положению перед последним "стеком" и проводится еще один отрезок. На рис. 3.29 показаны результаты построения дерева на нулевом (a), первом (b) и втором (c) шагах итерации.

(рис 3.29) Дерево. Итерация (a) 0; (b) 1; (c) 2

Фрактал "дерево" получается при неограниченном увеличении числа итераций. Размерность подобия для него имеет вид:

$$\frac{\ln 5}{\ln 3}\approx 1,46$$

Пример 27. Рассмотрим описание в виде L-системы еще одного хорошо известного фрактала - салфетки Серпинского (рис. 3.30). Имеем:

угол: $$\frac{\pi}{3}$$;

аксиома: FXF--FF-FF;

правила:

$$F \to FF;\\ X\to --FXF++FXF++FXF--.$$

На рис. 3.30 показаны фигуры, соответствующие нулевой, первой и пятой итерациям.

(рис 3.30) Салфетка Серпинского. Итерация (a) 0 (вверху) и 1; (b) 5

Острова Коха и кривая Гильберта

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

Пример 28. Построим два троичных острова Коха. Начальной фигурой для каждого острова является правильный треугольник; фигура на шаге n получается из фигуры, построенной на шаге n - 1, с помощью преобразования каждого отрезка AB этой фигуры в ломаную ACDEB с равными по длине четырьмя звеньями по правилу, показанному на рис. 3.31, где $$\widehat{ACD}=\widehat {DEB}=120^\circ$$

(рис 3.31) Преобразование отрезка для троичного острова Коха

Зная координаты концов отрезка AB, нетрудно найти координаты вершин этой ломаной. Обозначим через O начало координат. Положим:

$$v=\frac13AB=(x_v, y_v)$$

и

$$u-(y_v-x_v)$$

Очевидно, что вектор u перпендикулярен вектору v. Для радиус-векторов вершин C, D и E ломаной имеем:

$$OC=OA+v;\\ OD=\frac12(OA+OB)+\frac{\sqrt{3}}{2}u;\\ OE=OC+v$$

Острова отличаются друг от друга только направлением первого угла поворота, влево или вправо (рис. 3.32 (a-b)). Первый троичный остров называется еще снежинкой Коха.

(рис 3.32) Троичные острова Коха, n = 4: (a) первый; (b) второй

Очевидно, что представление троичного острова в виде L-системы отличается от представления кривой Коха только аксиомой.

Пример 29. Рассмотрим четверичный остров Коха. Исходной фигурой для построения является квадрат. На шаге итерации каждый отрезок преобразуется в ломаную, состоящую из 8 равных звеньев (рис. 3.33).

(рис 3.33) Преобразование отрезка четверичного острова Коха

Положим $$v=\frac14AB=(x_v, y_v), u=(-y_v, x_v)$$. Тогда радиус-векторы вершин ломаной находятся следующим образом:

OC = OA + v; OD = OC + u; OE = OD + v; OF = OC + v;
OG = OF - u; OH = OG + v; OI = OF + v. 

На рис. 3.34 показаны первые 2 итерации построения фигуры.

(рис 3.34) Четверичный остров Коха, первые 2 итерации

Пример 30. Рассмотрим фрактал, который называется кривой Гильберта. Кривая Гильберта представляет собой непрерывную кривую, которая полностью заполняет квадрат. Она являет

(рис 3.35) Кривая Гильберта, первые 4 итерации

Построим векторное представление ломаной $$f_n$$ на шаге итерации n, для $$n = 0, 1, 2, \dots$$

Пусть M - точка и $$v_1, v_2, \dots$$ - векторы. Обозначим через $$Mv_1, v_2, \dots, v_n$$ ломаную, первой вершиной которой является точка M, следующая вершина является концом вектора $$v_1$$, отложенного от точки M, третьей вершиной является конец вектора $$v_2$$, отложенного от второй вершины ломаной, и так далее.

Ломаную $$f_n$$ можно построить с помощью последовательности векторов, параллельных сторонам квадрата и имеющих одинаковую длину. Пусть ABCD - квадрат (рис. 3.36). Положим $$a_0 = AD, b_0 = AB$$. На каждом шаге длина векторов, составляющих ломаную, уменьшается вдвое. Обозначим $$a_n=\frac12a_{n-q}, b_n=\frac12b_{n-1}$$, для $$n = 1, 2, \dots$$

(рис 3.36) Построение кривой Гильберта

Ломаная $$f_0$$ состоит из вершины $$A_0$$, являющейся серединой диагонали AC, и пустой последовательности векторов. Ломаная $$f_1$$ имеет вид $$A_1b_1, a_1, - b_1$$ (см. рис. 3.36), где точка $$A_1$$ - середина отрезка $$AA_0$$.

Ломаная $$f_2$$ выглядит следующим образом:

$$A_2a_2, b_2, - a_2, b_2, b_2, a_2, - b_2, a_2, b_2, a_2, - b_2, - b_2, - a_2, - b_2, a_2, $$

где точка $$A_2$$ является серединой отрезка $$AA_1$$.

Обозначим через $$y_k$$ произвольную подпоследовательность векторов ломаной $$f_k$$. Через ($$- y_k$$ ) обозначим последовательность векторов, которая получается из последовательности $$y_k$$ заменой каждого вектора на противоположный к нему вектор. Далее, обозначим через $$g(y_k)$$ последовательность векторов, которая получается из последовательности $$y_k$$ одновременной заменой всех вхождений вектора $$a_k$$ на вектор $$b_k$$, а вектора $$b_k$$ - на вектор $$a_k$$. Кроме того, обозначим через $$inc(y_k)$$ последовательность векторов, которая отличается от последовательности $$y_k$$ заменой всех индексов на k + 1.

Пусть теперь $$x_n$$ - последовательность векторов ломаной $$f_n$$. Имеем:

$$x_0$$ - пустая последовательность;

$$x_n = g(inc(x_{n - 1})), b_n, inc(x_n - 1}), a_n, inc(x_{n - 1}), - b_n, - g(inc(x_n - 1)), $$

для $$n = 1, 2, \dots$$

Обозначим через $$A_n$$ точку, от которой откладывается последовательность векторов $$x_n$$, для $$n = 1, 2, \dots$$ Очевидно, что точки $$A_0, A_1, \dots$$ лежат на диагонали AC квадрата (см. рис. 3.36) и удовлетворяют соотношениям:

$$OA_0=\frac12(OA+OC);\\ OA_n=\frac12(OA+OA_{n-1}),$$

для $$n = 1, 2, \dots$$

Множество Мандельброта

Рассмотрим фрактал множество Мандельброта (рис. 3.37).

(рис 3.37) Множество Мандельброта

Пусть $$\mathbb {C}$$ - множество комплексных чисел и D - множество точек квадрата [- 2; 2] x [- 2; 2], так что

$$D = \{c | c \in \mathbb {C}, - 2 \le \Re c \le2, - 2 \leIm c \le2\}.$$

Для каждой точки c из множества D рассмотрим отображение $$f_c: \mathbb {C} \to \mathbb {C}$$, такое что $$f_c(z) = z^2 + c$$. Множество Мандельброта состоит из таких точек c множества D, для которых траектория точки 0 при отображении $$f_c$$ не выходит за пределы круга радиуса 2, т. е. для каждой точки z множества

$$\{0, f_c(0), f_c(f_c(0)), f_c(f_c(f_c(0))), \dots\}$$

выполняется условие: | z | < 2. Указанное множество представляет собой последовательность точек $$z_0, z_1, z_2, \dots$$, таких что

$$z_0=0, z_n=z_{n-1}^2+c,$$

для $$n = 1, 2, \dots$$

Положим $$z_n = x_n + iy_n$$, для $$n = 0, 1, 2, \dots$$, и c = x + iy. Тогда из данного соотношения будем иметь:

$$x_n=x_{n-1}^2-y_{n-1}^2+x, y_n = 2x_{n-1} y_{n-1}+y,$$

для $$n = 1, 2, \dots$$

Нулевая итерация соответствует множеству D. После первой итерации остаются точки, лежащие в круге радиуса 2, т. е. такие точки c, что | c | < 2, или $$x^2 + y^2 < 4$$. После второй итерации остаются точки c, для которых выполняется условие $$| c^2 + c | < 2$$ (рис. 3.38), и т. д.

(рис 3.38) Множество Мандельброта, 512 итераций

На рис. 3.38 черным цветом выделено множество точек, которые остаются в круге радиуса 2 после 512 итераций. Точки, которые выходят за пределы этого круга на разных шагах итерации, отличаются цветом.

Фрактал "Плазма"

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

Пусть I - множество номеров цветов из некоторой палитры, такое что I = {0, 1, 2, ..., N}, и ABCD - прямоугольник. Обозначим через M множество пикселей прямоугольника ABCD (рис. 3.39).

Пусть $$n_1, n_2, n_3, n_4$$ - четыре попарно различные элемента множества I. Раскрасим в цвета с этими номерами вершины A, B, C и D, соответственно (рис. 3.40).

Обозначим через T точку пересечения диагоналей прямоугольника ABCD и раскрасим ее в цвет с номером n, где $$n = (n_1 + n_2 + n_3 + n_4) \;\text{div}\; 4$$.

Пусть P, Q, R и S - середины сторон AB, BC, CD и DA, соответственно. Обозначим через $$d_{xy}$$ - длину стороны XY. Для точки P положим

$$v = (n_1 + n_2) \;\text{div}\; 2 + r,$$

где r - случайное целое число, такое что $$-d_{AB} \le r \le d_{AB}$$.

Раскрасим точку P в цвет с номером m, где

$$m=\begin{cases} v,v\in I,\\ 0, v <0,\\ N, v > N \end{cases}$$

Аналогично находятся номера цветов для точек Q, R и S.

(рис 3.39) Разбиение на 4 прямоугольника

Иногда слагаемое r в соотношение для v добавляется не для каждой стороны, а только для одной из них. Случайное число также может участвовать в определении цвета центра квадрата.

Описанная выше процедура применяется к прямоугольникам APTS, PBQT, TQCR и STRD (см.рис. 3.39). Далее построение продолжается рекурсивно до тех пор, пока не будет найден цвет для каждого пикселя множества M.

(рис 3.40) Два изображения фрактала "Плазма"

На рис. 3.40 приведены два варианта раскраски квадрата по описанному выше методу. Попарно различные цвета вершин квадрата выбираются случайным образом. Палитра состоит из 216 "безопасных" цветов.

Кодирование звуковой информации

В природе звуковые сигналы имеют непрерывный спектр частот, т. е. являются аналоговыми. Для записи и воспроизведения звука используются методы дискретизации и квантования. Основными параметрами звуковых волн являются частота и амплитуда колебаний. Частоту измеряют в герцах (в музыке ее называют тоном). Амплитуда звуковых колебаний характеризует громкость звука, ее называют силой звука или его давлением, она измеряется в паскалях. Из-за большого разброса значений используют логарифмическую шкалу децибелов как показателей уровня звука. Основными методами кодирования звука являются

метод частотной модуляции FM (frequency modulation);

метод таблично-волнового синтеза (wave table).

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

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

Упражнения

Определите примерный тон, а также светлый он или темный, только по его компонентам для цвета

a) rgb(50, 50, 50) ;

b) rgb(90, 0, 100) ;

c) rgb(150, 200, 140) .

Найдите 1) 16-ричный код; 2) двоичный код; 3) ближайший "безопасный цвет" для цвета

a) rgb(101, 202, 55) ;

b) rgb(236, 12, 133) ;

c) rgb(17, 135, 250) .

Найдите целые RGB-компоненты цвета

a) f073ab;

b) 5d5d5d;

c) ссff33 (hex) .

Найдите цветовые компоненты в модели CMYK цвета

a) rgb(0,9, 0.4, 0,7)

b) rgb(24, 108, 209) ;

c) hsv(350, 90, 70) .

Найдите цветовые компоненты в модели HSV цвета

a) rgb(0,6, 0.8, 0,25) ;

b) rgb(105, 244, 56) ;

c) cmyk(0,4, 0,8, 0, 0,5) .

Найдите цветовые компоненты в модели RGB цвета:

a) cmyk(0,25, 0, 0,85, 0,7) ;

b) cmyk(0, 0,33, 0,88, 0,25) ;

c) hsv(100, 50, 80) ;

d) hsv(240, 100, 40).

Постройте черно-белое пиксельное изображение, каждая строка которого закодирована двоичным словом, в котором 0 соответствует белому цвету, а 1 - черному, если его код (hex) имеет вид:

a) 1830 0c60 4aa4 76dc 2aa8 1c70 0000 1c70 2aa8 76dc 4aa4 0c60 1830;

b) 3e 42 02 44 10;

c) 3f 41 01 42 18

d) 31 6b a5 6b 31.

Придумайте свой способ символьных изображений букв и цифр, например, с помощью символов (U+2591) и (

Найдите параметрическое представление кривой Безье для точек c координатами

a) (0; 0); (5; 5); (6;1);

b) (- 2; 0); (- 1; 1); (0; 0); (2; 0).

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

(рис 3.41) Исходные a) 3; b) 4; c) 4; d) 4; e) 4; f) 5 точек

Постройте кривые Безье для точек с взаимным расположением, приведенным на рис. 3.41 (b-e), в графическом редакторе Paint.

Найдите матричное представление кривой Безье 4-го порядка.

Составьте общее уравнение годографа кривой Безье 2-го порядка.

Постройте в системе координат $$ f = N_{0,0}, N_{1,0}, N_{2,0}, N_{3,0}, N_{0,1}, N_{1,1}, N_{2,1}, N_{0,2}, N_{1,2}$$ для узлового вектора

a) (0, 1, 2, 3, 4);

b) (0, 0, 1, 3, 4).

Найдите параметрическое представление B-сплайна для n точек и k узлов, если узловой вектор имеет вид:

a) (0, 0, 1, 3, 3), n = 2, k = 1; b) (0, 1, 2, 3, 4, 5, 6, 7), n = 4, k = 2;

a) (0, 0, 0, 1, 1, 1), n = k = 2; b) (0, 0, 0, 0, 1, 3, 5, 5, 5, 5), n = 5, k = 3.

Найдите число отрезков, из которых состоит приближенное изображение фрактала "дерево", после выполнения n итераций.

Найдите размерность подобия для салфетки Серпинского.

Опишите в виде L-системы и выполните построение для первых двух итераций

a) снежинки Коха;

b) квадратичного острова Коха;

c) кривой Гильберта.

Постройте фигуру, которая получается после первой и второй итераций, если в виде L-системы ее описание имеет вид (рис. 3.42):

a)угол: $$\frac{\pi}{7}$$; аксиома: F; правило: $$F \to F[+F][-F]F$$;

b)угол: $$\frac{\pi}{8}$$; аксиома: F; правило: $$F \to -F+F+[+F-F-]-[-F+F+F]$$;

c)угол: $$\frac{\pi}{9}$$; аксиома: F; правило: $$F \to -F[-F+F-F]+[+F-F-F]$$;

d)угол: $$\frac{\pi}{7}$$; аксиома: F; правило: $$F \to F[+F][-F][F]$$.

(рис 3.42) "Растения": (a) сорняк; (b) ветвь; (c) куст; (d) соцветие

На рис. 3.44 фигуры (a-c) показаны после четырех, а фигура (d) - после шести итераций.

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

Добавим в алфавит грамматики L-системы коэффициент q, обозначающий изменение длины отрезка смещения в q раз. Фрактал дерево Пифагора (рис. 3.43) в виде L-системы можно описать в виде:

угол: $$\frac{\pi}{4}$$; аксиома: F--X; коэффициент q:$$\sqrt{2}$$;

правила: $$F \to qF, X \to qF[+X][-F[X]--F]--qF-qF$$.

Постройте фрактал дерево Пифагора для первых 3 итераций.

(рис 3.43) Дерево Пифагора, 8 итераций

Опишите в виде L-системы фрактал "двоичное дерево" (рис. 3.44).

(рис 3.44) Двоичное дерево: итерация (a) 0; (b) 1; (c) 2

Указание. Возьмите в качестве аксиомы слово FX.