При условии. 1. Существует два основных вида представления геометрических объектов - растровое и векторное

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 ⁱ для всех пяти возможных положений окружности.