Построить растровое изображение окружности. Использовать в вычислениях только целые числа

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

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

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

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

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

Реальная окружность может быть расположена относительно точек 1 и 2 одним из пяти способов 1-5. Если мы выбераем точку 1, то тем самым говорим, что (x_i+1)²+(y_i-1)² > R². Если же выбераем точку 2, то допускаем, что (x_i+1)²+(y_i)² > R². Рассмотрим две погрешности Δⁱ₁ и Δⁱ₂:

и контрольную величинуΔⁱ = Δⁱ₁+Δⁱ₂. При выборе точки, следующей за (x_i, y_i), станем руководствоваться следующим критерием:

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

если Δⁱ ≤ 0, выберем точку 2.

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

Для положения 1.

Δⁱ₁ < 0, Δⁱ₂ < 0 ⇒ Δⁱ₁+Δⁱ₂ < 0 ⇒ выбирается 2.

Для положения 2.

Δⁱ₁ < 0, Δⁱ₂ = 0 ⇒ Δⁱ₁+Δⁱ₂ < 0 ⇒ выбирается 2.

Для положения 3 возможны варианты (учитывая, что Δⁱ₁ < 0, Δⁱ₂ > 0).

Вариант 3.1. |Δⁱ₁| ⇒ |Δⁱ₂| ⇒ Δⁱ₁+Δⁱ₂ < 0 ⇒ выбирается 2.

Вариант 3.2. |Δⁱ₁| < |Δⁱ₂|⇒Δⁱ₁+Δⁱ₂ > 0 ⇒ выбирается 1.

Для положения 4.

Δⁱ₁ = 0, Δⁱ₂ > 0 ⇒ Δⁱ₁+Δⁱ₂ > 0 ⇒ выбирается 1.

Для положения 5.

Δⁱ₁ > 0, Δⁱ₂ > 0 ⇒ Δⁱ₁+Δⁱ₂ > 0 ⇒ выбирается 1.

Далее получим выражение для контрольной величины Δⁱ

Δⁱ = Δⁱ₁+Δⁱ₂ = (x_i+1)²+(y_i-1)²-R²+(x_i+1)²+(y_i)²-R² = 2x_i²+2y_i²+4x_i-2y_i+3-2R².

Выражение для Δⁱ⁺¹ существенным образом зависит от выбора
следующей точки. Необходимо рассмотреть два случая: y_i+1 = y_i и
y_i+1 = y_i-1.

Теперь, когда получено рекуррентное выражение для Δⁱ⁺¹ через Δⁱ, остается получить Δ¹ (контрольную величину в начальной точке.) Она не может быть получена рекуррентно, ибо не определено предшествующее значение, зато легко может быть найдена непосредственно

Таким образом, алгоритм построения окружности, реализованный в V_BRcirc, основан на последовательном выборе точек; в зависимости от знака контрольной величины Δⁱ выбирается следующая точка и нужным образом изменяется сама контрольная величина. Процесс начинается в точке (0, r), а первая точка, которую ставит процедура Pixel_circle, имеет координаты (xc, yc+r). При x = y процесс заканчивается.

#include <conio.h>
 
#define VGA_MODE  0x0013
#define TEXT_MODE 0x0003
typedef unsigned char byte;
byte far* vga = (byte far *)0xA0000000L;
 
void SetMode(unsigned short mode)
{
  asm {
    mov ax, [mode]
    int 10h
    }
}
 
void putpixel(int x, int y, byte color)
{
  vga[y*320+x] = color;
}
 
/*--------------------------------------------------- V_Circle
 * Подпрограммы для генерации окружности
 * Pixel_circle - занесение пикселов с учетом симметрии
 * V_BRcirc     - генерирует окружность по алгоритму
 *                Брезенхема.
 * V_MIcirc     - генерирует окружность по алгоритму
 *                Мичнера.
 */
 
/*----------------------------------------------- Pixel_circle
 * Заносит пикселы окружности по часовой стрелке
 */
 
static void Pixel_circle (int xc,int  yc,int  x,int  y,int  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 */
 
/* Генерирует 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 (int xc,int  yc,int  r,int  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 (int xc,int  yc,int  r,int  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 */
 
 
 
int main()
{
/* Устанавливаем видеорежим */
  SetMode(VGA_MODE);
 
/*
 * ТЕСТ ГЕНЕРАЦИИ ОКРУЖНОСТЕЙ
 *
 * Cтроит заданную окружность по алгоритму Брезенхема
 * и концентрично с ней с радиусом, уменьшенным на 2, и
 * номером цвета, уменьшенным на 1, выдает окружность по
 * алгоритму Мичнера.
 *
 
 */
 
int   ii, Xc=150, Yc=80, R=50, Pix=14;
V_BRcirc (Xc, Yc, R, Pix);
V_MIcirc (Xc, Yc, R-2, Pix-1);
 
 
 getch();
  SetMode(TEXT_MODE);
   return 0;
}