Лекция: При условии

x1+ x2+ x3 ≥4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1

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

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

Рис. 2

Реальная окружность может быть расположена относительно точек 1 и 2 одним из пяти способов 1-5. Если мы выбераем точку 1, то тем самым говорим, что (xi+1)2+(yi-1)2 » R2. Если же выбераем точку 2, то допускаем, что (xi+1)2+(yi)2 » R2. Рассмотрим две погрешности Di1 и Di2:

Di1 = (xi+1)2+(yi-1)2-R2

Di2 = (x1+1)2+(yi)2-R2

и контрольную величинуDi = Di1+Di2. При выборе точки, следующей за (xi, yi), станем руководствоваться следующим критерием:

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

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

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