logo
Пособие 2011

Растровая развёртка окружности

Существует несколько очень простых, но не эффективных способов преобразования окружностей в растровую форму. Например, рассмотрим для простоты окружность с центром в начале координат. Ее уравнение записывается как x2 + y2 = R2. Решая это уравнение относительно y, получим

y = ± .

Чтобы изобразить четвертую часть окружности, будем изменять x с единичным шагом от 0 до R и на каждом шаге вычислять y. Вторым простым методом растровой развертки окружности является использование вычислений x и y по формулам x = R cos α, y = R sin α при пошаговом изменении угла α от 0 до 90.

Для упрощения алгоритма растровой развёртки стандартной окружности можно воспользоваться её симметрией относительно координатных осей и прямых y = ± x; в случае, когда центр окружности не совпадает с началом координат, эти прямые необходимо сдвинуть параллельно так, чтобы они прошли через центр окружности. Тем самым достаточно построить растровое представление для 1/8 части окружности, а все оставшиеся точки получить симметрией (см. Рис. 4 .21).

Рис. 4.21. Восьмисторонняя симметрия

Рассмотрим участок окружности из второго октанта x Є [0, R/]. Далее опишем алгоритм Брезенхейма для этого участка окружности.

На каждом шаге алгоритм выбирает точку Pi (xi, yi), которая является ближайшей к истинной окружности. Идея алгоритма заключается в выборе ближайшей точки при помощи управляющих переменных, значения которых можно вычислить в пошаговом режиме с использованием небольшого числа сложений, вычитаний и сдвигов.

Рассмотрим небольшой участок сетки пикселей, а также возможные способы (от A до E) прохождения истинной окружности через сетку (Рис. 4 .22).

Предположим, что точка Pi-1 была выбрана как ближайшая к окружности при x = xi-1. Теперь найдем, какая из точек (Si или Ti) расположена ближе к окружности при x = xi-1 + 1.

Рис. 4.22. Варианты прохождения окружности через растровую сетку

Заметим, что ошибка при выборе точки Pi (xi, yi) была равна

D(Pi) = (xi2+ yi2) – R2.

Запишем выражение для ошибок, получаемых при выборе точки Si или Ti:

D(Si) = [(xi-1+ 1)2 + (yi-1)2] – R2;

D(Ti) = [(xi-1+ 1)2 + (yi-1 – 1)2] – R2.

Если | D(Si) | ≥ | D(Ti) |, то Ti ближе к реальной окружности, иначе выбирается Si.

Введем di = | D(Si) | – | D(Ti) |.

Ti будет выбираться при di ≥ 0, в противном случае будет устанавливаться Si.

Опуская алгебраические преобразования, запишем di и di+1 для разных вариантов выбора точки Si или Ti.

D1 = 3 – 2 R.

Если выбирается Si (когда di < 0), то di+1 = di + 4 xi-1 + 6.

Если выбирается Ti (когда di ≥ 0), то di+1 = di + 4 (xi-1 – yi-1) + 10.

Существует модификация алгоритма Брезенхейма для эллипса.

      1.