Рисование окружности

Путь: Графика » Рисование » Окружность

Рисование окружности

Алгоритмы взяты из прекрасной книги
П.В.Вельтмандер "Машинная графика"

Во многих областях приложений, таких как, например, системы автоматизированного проектирования машиностроительного направления, естественными графическими примитивами, кроме отрезков прямых и строк текстов, являются и конические сечения, т.е. окружности, эллипсы, параболы и гиперболы. Наиболее употребительным примитивом, естественно, является окружность. Один из наиболее простых и эффективных алгоритмов генерации окружности разработан Брезенхемом.

1 Алгоритм Брезенхема

Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).

Окружность с центром в начале координат описывается уравнением:

X² + Y² = R²

Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра P_i(X_i, Y_i), ближайшую к истинной окружности, так чтобы ошибка:

E_i(P_i) = (X_i² + Y_i²) - R²

была минимальной. Причем, как и в алгоритме Брезенхема для генерации отрезков, выбор ближайшей точки выполняется с помощью анализа значений управляющих переменных, для вычисления которых не требуется вещественной арифметики. Для выбора очередной точки достаточно проанализировать знаки.

Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.

Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.

Рис. 1: Варианты расположения очередного пиксела окружности

При генерации окружности по часовой стрелке после занесения точки (X_i, Y_i) следующая точка может быть (см. рис. 0.1а) либо Pg = (X_i+1, Y_i) - перемещение по горизонтали, либо Pd = (X_i+1, Y_i-1) - перемещение по диагонали, либо Pv = (X_i, Y_i-1) - перемещение по вертикали.

Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:

|Dg|

| (X+1)²

Y²

R² |

|Dd|

| (X+1)²

(Y-1)²

R² |

|Dv|

| X²

(Y-1)²

R² |

Выбирается и заносится та точка, для которой это значение минимально.

Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б). Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.

Случай Dd < 0

Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный - Pg или диагональный - Pd.

Для определения того, какой пиксел выбрать Pg или Pd составим разность:

|Dg| - |Dd| =

|(X+1)² + Y² - R²| - |(X+1)² + (Y-1)² - R²|

И будем выбирать точку Pg при di Ј 0, в противном случае выберем Pd.

Рассмотрим вычисление di для разных вариантов.

Для вариантов 2 и 3:

Dg і 0 и Dd < 0, так как горизонтальный пиксел либо вне, либо на окружности, а диагональный внутри.

di = (X+1)² + Y² - R² + (X+1)² + (Y-1)² - R²;

Добавив и вычтя (Y-1)² получим:

di = 2 ·[(X+1)² + (Y-1)² - R²] + 2·Y - 1

В квадратных скобках стоит Dd, так что

di = 2 ·(Dd + Y) - 1

Для варианта 1:

Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg < 0 и Dd < 0, причем di < 0, так как диагональная точка больше удалена от окружности, т.е. по критерию di < 0 как и в предыдущих случаях следует выбрать горизонтальный пиксел Pg, что верно.

Случай Dd > 0

Здесь в качестве следующего пиксела могут быть выбраны или диагональный - Pd или вертикальный Pv.

Для определения того, какую пиксел выбрать Pd или Pv составим разность:

|Dd| - |Dv| =

|(X+1)² + (Y-1)² - R²| - |X² + (Y-1)² - R²|

Если si Ј 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.

Рассмотрим вычисление si для разных вариантов.

Для вариантов 5 и 6:

Dd > 0 и Dv Ј 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.

si = (X+1)² + (Y-1)² - R² + X² + (Y-1)² - R²;

Добавив и вычтя (X+1)² получим:

si = 2 ·[(X+1)² + (Y-1)² - R²] - 2·X - 1

В квадратных скобках стоит Dd, так что

si = 2 ·(Dd - X) - 1

Для варианта 7:

Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.

Случай Dd = 0

Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.

С другой стороны, для компонент si имеем: Dd = 0 и Dv < 0, так что по критерию si Ј 0 также выбираем диагональный пиксел.

Итак:

Dd < 0

di Ј 0 - выбор горизонтального пиксела Pg

di > 0 - выбор диагонального пиксела Pd

Dd > 0

si Ј 0 - выбор диагонального пиксела Pd

si > 0 - выбор вертикального пиксела Pv

Dd = 0

выбор диагонального пиксела Pd.

Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.

1. Для горизонтального шага к X_i+1, Y_i

X_i+1 = X_i + 1
Y_i+1 = Y_i
Dd_i+1 = (X_i+1+1)² + (Y_i+1-1)² - R² =
X_i+1² + 2·X_i+1 + 1 + (Y_i+1-1)² - R² =
(X_i+1)² + (Y_i-1)² - R² + 2·X_i+1 + 1 =
Dd_i + 2·X_i+1 + 1

2. Для диагонального шага к X_i+1, Y_i-1

X_i+1 = X_i + 1
Y_i+1 = Y_i - 1
Dd_i+1 = Dd_i + 2 ·X_i+1 - 2 ·Y_i+1 + 2

3. Для вертикального шага к X_i, Y_i-1

X_i+1 = X_i
Y_i+1 = Y_i - 1
Dd_i+1 = Dd_i - 2 ·Y_i+1 + 1

В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:

X= 0

Y= R

Dd = (X+1)² + (Y-1)² - R² = 1 + (R-1)² - R² = 2*(1 - R)

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

В Приложении приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.

0.15 Приложение 4. Процедуры генерации окружности

В данном приложении помещены процедуры генерации окружностей по алгоритму Брезенхема и Мичнера, а также программа T_Circle для тестирования данных процедур.

/*--------------------------------------------------- V_Circle
 * Подпрограммы для генерации окружности
 * Pixel_circle - занесение пикселов с учетом симметрии
 * V_BRcirc     - генерирует окружность по алгоритму
 *                Брезенхема.
 * V_MIcirc     - генерирует окружность по алгоритму
 *                Мичнера.
 */

#include <graphics.h>

/*----------------------------------------------- Pixel_circle
 * Заносит пикселы окружности по часовой стрелке
 */

static void Pixel_circle (xc, yc, x, y, pixel)
int  xc, yc, x, y, pixel;
{
   putpixel(xc+x, yc+y, pixel);
   putpixel(xc+y, yc+x, pixel);
   putpixel(xc+y, yc-x, pixel);
   putpixel(xc+x, yc-y, pixel);
   putpixel(xc-x, yc-y, pixel);
   putpixel(xc-y, yc-x, pixel);
   putpixel(xc-y, yc+x, pixel);
   putpixel(xc-x, yc+y, pixel);
}  /* Pixel_circle */


/*--------------------------------------------------- V_BRcirc
 * Генерирует 1/8 окружности по алгоритму Брезенхема
 *
 * Процедура может строить 1/4 окружности.
 * Для этого надо цикл while заменить на for (;;)
 * и после Pixel_circle проверять достижение конца по условию
 * if (y <= end) break;
 * Где end устанавливается равным 0
 * В этом случае не нужен и последний оператор
 * if (x == y) Pixel_circle (xc, yc, x, y, pixel);
 * Генерацию 1/8 можно обеспечить задав end = r / sqrt (2)
 */

void V_BRcirc (xc, yc, r, pixel)
int  xc, yc, r, pixel;
{  int  x, y, z, Dd;
   x= 0;  y= r;  Dd= 2*(1-r);
   while (x < y) {
      Pixel_circle (xc, yc, x, y, pixel);
      if (!Dd) goto Pd;
      z= 2*Dd - 1;
      if (Dd > 0) {
         if (z + 2*x <= 0) goto Pd; else goto Pv;
      }
      if (z + 2*y > 0) goto Pd;
Pg:   ++x;      Dd= Dd + 2*x + 1;   continue; /* Горизонт */
Pd:   ++x; --y; Dd= Dd + 2*(x-y+1); continue; /* Диагонал */
Pv:   --y;      Dd= Dd - 2*y + 1;             /* Вертикал */
   }
   if (x == y) Pixel_circle (xc, yc, x, y, pixel);
}  /* V_BRcirc */


/*--------------------------------------------------- V_MIcirc
 * Генерирует 1/8 окружности по алгоритму Мичнера
 */

void V_MIcirc (xc, yc, r, pixel)
int  xc, yc, r, pixel;
{  int  x, y, d;
   x= 0;  y= r;  d= 3 - 2*r;
   while (x < y) {
      Pixel_circle (xc, yc, x, y, pixel);
      if (d < 0) d= d + 4*x + 6; else {
         d= d + 4*(x-y) + 10;  --y;
      }
      ++x;
   }
   if (x == y) Pixel_circle (xc, yc, x, y, pixel);
}  /* V_MIcirc */




/*=============================================== T_CIRCLE.C
 *
 * ТЕСТ ГЕНЕРАЦИИ ОКРУЖНОСТЕЙ
 *
 * Запрашивает ввод четырех чисел - координат центра,
 * радиуса и цвета построения: Xc Yc R Pix
 *
 * Затем строит заданную окружность по алгоритму Брезенхема
 * и концентрично с ней с радиусом, уменьшенным на 2, и
 * номером цвета, уменьшенным на 1, выдает окружность по
 * алгоритму Мичнера.
 *
 * При вводе Xc < 0 программа прекращает работу
 */

#include <graphics.h>
#include <stdio.h>
#include "V_CIRCLE.C"


/*-------------------------------------------- MAIN T_CIRCLE.C
 */
void main (void)
{
   int   ii, Xc=300, Yc=240, R=238, Pix=14;
   int   gdriver = DETECT, gmode;

   initgraph(&gdriver, &gmode, "c:\tc\bgi");
   if ((ii= graphresult()) != grOk) {
      printf ("Err=%d\n", ii); goto all;
   }
   setbkcolor(0);
   cleardevice();

for (;;) {
gotoxy (1,1);
printf("                                                 \r");
printf("Xc, Yc, R, Pix= (%d %d %d %d) ? ", Xc,Yc,R,Pix);
scanf ("%d%d%d%d", &Xc, &Yc, &R, &Pix);
if (Xc < 0) break;
V_BRcirc (Xc, Yc, R, Pix);
V_MIcirc (Xc, Yc, R-2, Pix-1);
}
all:
   closegraph();
}

Исходники этого алгоритма, взятые из других источников

void Circle(int x, int y, int r,unsigned char color)
{
        int x1,y1,yk = 0;
        int sigma,delta,f;

        x1 = 0;
        y1 = r;
        delta = 2*(1-r);

        do
        {
                PutPixel(x+x1,y+y1,color);
                PutPixel(x-x1,y+y1,color);
                PutPixel(x+x1,y-y1,color);
                PutPixel(x-x1,y-y1,color);

                f = 0;
                if (y1 < yk)
                        break;
                if (delta < 0)
                {
                        sigma = 2*(delta+y1)-1;
                        if (sigma <= 0)
                        {
                                x1++;
                                delta += 2*x1+1;
                                f = 1;
                        }
                }
                else
                if (delta > 0)
                {
                        sigma = 2*(delta-x1)-1;
                        if (sigma > 0)
                        {
                                y1--;
                                delta += 1-2*y1;
                                f = 1;
                        }
                }
                if (!f)
                {
                        x1++;
                        y1--;
                        delta += 2*(x1-y1-1);
                }
        }
        while(1);
}

На Паскале:

	Procedure Circle(x,y,rr:integer);
var xi,yi,r,di,lim,s,ss:integer;
label 1,2,3,4,10,20,30;
Begin
r:=rr;
xi:=0; yi:=r; di:=2*(1-r); lim:=0;
1: SetPixel(xi+x,yi+y);
   SetPixel(xi+x,-yi+y);
   SetPixel(-xi+x,yi+y);
   SetPixel(-xi+x,-yi+y);
   if yi<limthen goto 4;
   if di<0then goto 2;
   if di>0then goto 3;
   if di=0 then goto 20;
2: s:=2*di+2*yi-1;
   if s<=0then goto 10;
   if s>0then goto 20;
3: s:=2*di+2*xi-1;
   if s<=0then goto 20;
   if s>0then goto 30;
10:xi:=xi+1;
   di:=di+2*xi+1;
   goto 1;
20:xi:=xi+1;
   yi:=yi-1;
   di:=di+2*xi-2*yi+2;
   goto 1;
30:yi:=yi-1;
   di:=di-2*yi+1;
   goto 1;4:
end;