Билет 8

1. Растровое представление геометрических объектов. Целочисленные алгоритмы для построения графических примитивов.

2. Основные подходы к разработке ПО. Методы программирования и структура ПО.

3. Исследовать на экстремум функцию:

F₀= x₁² - x₂² + 2x₃² ,

при условии

x₁+ x₂+ x₃ ≥4

1. Существует два основных вида представления геометрических объектов - растровое и векторное. Векторное представление - это математическое описание объекта, построенное на основе понятия “вектор”. Растровое - это представление объекта в том виде, в котором он будет выглядеть в реальности, то есть его изображение. Существуют способы перевода векторного представления в растровое и обратно.

Один из способов перевода 2D векторных объектов - алгоритмы Брезенхема.

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

Пусть на сетке растра задан отрезок прямой (x1,y1)-(x2,y2), тангенс угла наклона которого находится в диапазоне [0,1].

Для построения пэлов используют управляющую переменную d. На каждом шаге d пропорциональна разности между s и t. Для i-го шага, когда пэл P_i-1 уже известен, требуется определить, какой из пэлов P_i или S_i должен быть выбран. Если s<t, то выбираем S_i, как наиболее близко расположенный пэл к реальному отрезку, в противном случае P_i.

Начальное значение переменной d определяется как d=2*dy-dx, где dy = y2-y1 и dx = x2-x1. Для каждого значения x_i = x_i-1+1 проверяем знак управляющей переменной d:

а) если d>0, то выбираем пэл P_i, тогда y_i=y_i-1+1 и d=d+2*(dx-dy)

б) если d>0, то выбираем пэл S_i, тогда y_i=y_i-1 и d=d+2*dy

Алгоритм Брезенхема для построения окружностей.

Аналогичным образом, но немного сложнее строится окружность. Классическая схема алгоритма Брезенхема рассматривается на случай обхода лишь дуги окружности в 45⁰ от x = 0 до x=R/1.41.

Начальное значение управляющей переменной d определяется как d=3-2*R. Проверяем знак d:

а) d<0, y_i=y_i-1, d = d+4*x+6

б) d>0, y_i=y_i-1-1, d = d+4*(x-y)+10

Для построения полной окружности используется восьмисторонняя симметрия.

procedure bres_circle(xc,yc,r:interger):

var x,y,d:integer:

procedure sim(x,y;integer);

begin

putpixel(x+xc,y+yc,White);

putpixel(x+xc,-y+yc,White);

putpixel(-x+xc,-y+yc,White);

putpixel(-x+xc,y+yc,White);

putpixel(y+xc,x+yc,White);

putpixel(y+xc,-x+yc,White);

putpixel(-y+xc,-x+yc,White);

putpixel(-y+xc,x+yc,White);

end;

begin

d:=3-2*y;

x:=0;

y:=r;

while(x <= y) do

begin

sim(x,y);

if d<0 then d:=d+4*x+6

else begin

d:=d+4*(x-y)+10;

dec(y)

end;

inc(x)

end;

end;

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

Обратимся к тексту процедуры bres_circle. Она использует процедуру sim, которая, как можно видеть, расставляет восемь точек вокруг точки (xc,yc) (центра нашей окружности). Эта процедура реализует следующее: окружность обладает центром симметрии и бесконечным количеством осей симметрии. Поэтому нет необходимости строить всю окружность, достаточно построить некоторую ее часть и последовательным применением преобразований симметрии получить из нее полную окружность. Мы станем строить 1/8 часть окружности, заключенную в РAOB (рис. 1).

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

Рис. 1

Кроме того, именно процедура sim отвечает за расположение центра окружности. Главная процедура вполне может считать, что она строит окружность с центром в начале координат.

Приступим к разбору ключевой идеи алгоритма. Пусть мы находимся в некоторой промежуточной фазе построения. Мы только что поставили точку (x_i, y_i) и теперь должны сделать выбор между точками 1(x_i+1, y_i-1) и 2(x_i+1, y) (рис. 2). (Напомним, что мы строим часть окружности, заключенную в РAOB, следовательно, подняться выше мы не можем и спуститься вниз более чем на одну точку не можем тоже.)

Рис. 2

Реальная окружность может быть расположена относительно точек 1 и 2 одним из пяти способов 1-5. Если мы выбераем точку 1, то тем самым говорим, что (x_i+1)²+(y_i-1)² » R². Если же выбераем точку 2, то допускаем, что (x_i+1)²+(y_i)² » R². Рассмотрим две погрешности Dⁱ₁ и Dⁱ₂:

Dⁱ₁ = (x_i+1)²+(y_i-1)²-R²

Dⁱ₂ = (x₁+1)²+(y_i)²-R²

и контрольную величинуDⁱ = Dⁱ₁+Dⁱ₂. При выборе точки, следующей за (x_i, y_i), станем руководствоваться следующим критерием:

если Dⁱ > 0, выберем точку 1;

если Dⁱ Ј 0, выберем точку 2.

Обоснуем разумность такого выбора. Рассмотрим знаки погрешностей Dⁱ₁ и Dⁱ₂ и их влияние на знак контрольной величины Dⁱ для всех пяти возможных положений окружности.

Для положения 1.

Dⁱ₁ < 0, Dⁱ₂ < 0 Ю Dⁱ₁+Dⁱ₂ < 0 Ю выбирается 2.

Для положения 2.

Dⁱ₁ < 0, Dⁱ₂ = 0 Ю Dⁱ₁+Dⁱ₂ < 0 Ю выбирается 2.

Для положения 3 возможны варианты (учитывая, что Dⁱ₁ < 0, Dⁱ₂ > 0).

Вариант 3.1. |Dⁱ₁| і |Dⁱ₂| Ю Dⁱ₁+Dⁱ₂ < 0 Ю выбирается 2.

Вариант 3.2. |Dⁱ₁| < |Dⁱ₂| ЮDⁱ₁+Dⁱ₂ > 0 Ю выбирается 1.

Для положения 4.

Dⁱ₁ = 0, Dⁱ₂ > 0 Ю Dⁱ₁+Dⁱ₂ > 0 Ю выбирается 1.

Для положения 5.

Dⁱ₁ > 0, Dⁱ₂ > 0 Ю Dⁱ₁+Dⁱ₂ > 0 Ю выбирается 1.

Далее получим выражение для контрольной величины Dⁱ

Dⁱ = Dⁱ₁+Dⁱ₂ = (x_i+1)²+(y_i-1)²-R²+(x_i+1)²+(y_i)²-R² = 2x_i²+2y_i²+4x_i-2y_i+3-2R².

Выражение для Dⁱ⁺¹ существенным образом зависит от выбора следующей точки. Необходимо рассмотреть два случая: y_i+1 = y_i и y_i+1 = y_i-1.

Dⁱ⁺¹ [при y_i+1 = y_i] = 2x²_i+1+2y²_i+1+4x_i+1-2y_i+1+3-2R² = 2(x_i+1)²+2y_i²+4(x_i+1)-2y_i+3-2R² = Dⁱ+4x_i+6.

Dⁱ⁺¹ [при y_i+1 = y_i-1] = 2x²_i+1+2y²_i+1+4x_i+1-2y_i+1+3-2R² = 2(x_i+1)²+2(y_i-1)²+4(x_i+1)-2(y_i-1)+3-2R² = Dⁱ+4(x_i-y_i)+10.

Теперь, когда получено рекуррентное выражение для Dⁱ⁺¹ через Dⁱ, остается получить D¹ (контрольную величину в начальной точке.) Она не может быть получена рекуррентно, ибо не определено предшествующее значение, зато легко может быть найдена непосредственно

x₁ = 0, y₁ = R Ю D¹₁ = (0+1)²+(R-1)²-R² = 2-2R,

D¹₂ = (0+1)²+R²-R² = 1

D¹ = D¹₁+D¹₂ = 3-2R.

Таким образом, алгоритм построения окружности, реализованный в bres_circle, основан на последовательном выборе точек; в зависимости от знака контрольной величины Dⁱ выбирается следующая точка и нужным образом изменяется сама контрольная величина. Процесс начинается в точке (0, r), а первая точка, которую ставит процедура sim, имеет координаты (xc, yc+r). При x = y процесс заканчивается.