06. Основные расчетные соотношения и алгоритм Брезенхема для генерации окружности.

Окружность можно описать:

(x - x0)^2 + (y - y0)^2 = R^2
x^2 + y^2 = R^2
y = sqrt(R^2 - x^2)

Параметрически:

x = x0 + R*cost
y = y0 + R*sint

t ∈ [0, 2pi)

Генерация окружности начинается из точки (0, R). В случае окружности, достаточно определить 1/8 от всей окружности, а остальные получить отражением полученной дуги.

Вообще, имем только 3 случая выбора пикселя (в выбраном нами направлении от (0, R)):

• горизонтальный вправо
• диаганональный вниз и вправо
• вертикальный вниз

.

x(i - 1), y(i - 1) - нельзя!

Критерий выбора: модуль разности квадратов растоянний от центра окружности до пиксела и до идеальной окружности.

m (право) = |(xi + 1)^2 + (yi)^2 - R^2|
m (диагональ)  = |(xi + 1)^2 + (yi - 1)^2 - R^2|
m (вниз) = |(xi)^2 + (yi - 1)^2 - R^2|

Опять вводят ошибку - разность между квадратами расстояний от центра окружности до диаганального пикселя и от центра до точки на окружности R^2:

Δi = (xi + 1)^2 + (yi -1)^2 - R^2

В окрестности возможны 5 вариантов прохождения окружности:

1. Между горизонтальным (Xi+1, Yi) и диагональным (Xi+1, Yi-1) пикселями.
2. Между горизонтальным (Xi+1, Yi) и другим диагональным (Xi+1, Yi+1) пикселями.
3. Между вертикальным (Xi, Yi-1) и диагональным (Xi+1, Yi-1).
4. Между вертикальным (Xi, Yi-1) и третьим диагональным (Xi-1, Yi-1) пикселями.
5. Прохождение точно через диагональный (Xi+1, Yi-1) пиксель.

1. Δi < 0, выбираем между 1 и 2.

δ1 = |(xi + 1)^2 + (yi)^2 - R^2| - |(xi + 1)^2 + (yi - 1)^2 - R^2|

Если δ1 <= 0, выбираем горизонтальный пиксель (расстояние до диагонального больше). Иначе - диагональный (расстояние до горизонтального больше).

2. Δi > 0, выбираем между 3 и 4.

δ2 = |(xi + 1)^2 + (yi - 1)^2 - R^2| - |(xi)^2 + (yi - 1)^2 - R^2|

Если δ2 <= 0, выбираем диагональный (расстояние до вертикального больше). Иначе - вертикальный (расстояние до диагонального больше)

3. Δi = 0, выбираем пятый вариант. Окружность проходит через диагональный пиксель.

Вывод x(i+1), y(i+1), и ошибки Δ(i+1):

Псевдокод

1. Ввод R, Xc, Yc.
2. X = 0, Y = R, Δ = 2(1-R).
3. Высвечивание текущего пиксела (X,Y).
4. Анализ D:
   4.1 Если Δ < 0, go to 5.
   4.2 если Δ = 0, go to 8.
   4.3 если Δ > 0, go to 6.
5. δ1 = 2Δ + 2Y - 1 и анализ полученного значения:
   5.1 если δ1 =< 0, go to 7.
   5.2 иначе, go to 8.
6. Вычисление параметра δ2 = 2Δ - 2X - 1 и анализ полученного значения:
   6.1 если δ2 =< 0, go to 8
   6.2 иначе, go to 9.
7. Горизонтальный шаг: X = X + 1; Δ = Δ + 2X + 1. go to 3.
8. Диагональный шаг: X = X + 1; Y = Y - 1; Δ = Δ + 2(X - Y + 1). go to 3.
9. Вертикальный шаг: Y = Y - 1; Δ = Δ - 2Y + 1. go to 3.
10. Конец.

Следующий вопрос: 07. Растровая развертка сплошных областей. Алгоритм с упорядоченным списком ребер.

Предыдущий вопрос: 05. Алгоритмы Брезенхема разложения отрезков в растр. Простой алгоритм Брезенхема. Целочисленный алгоритм Брезенхема. Общий алгоритм Брезенхема.