Алгоритм генерации круга

Рисование круга на экране немного сложнее, чем рисование линии. Существует два популярных алгоритма генерации круга - алгоритм Брезенхема и алгоритм средней точки круга . Эти алгоритмы основаны на идее определения последующих точек, необходимых для рисования круга. Давайте обсудим алгоритмы подробно -

Уравнение окружности: $ X ^ {2} + Y ^ {2} = r ^ {2}, $ где r - радиус.

Поколение круга

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

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

На следующем рисунке вы можете видеть, что мы поместили пиксель в положение (X, Y) и теперь нужно решить, куда поместить следующий пиксель - в N (X + 1, Y) или в S (X + 1, Y-1).

Это может быть решено параметром решения d .

  • Если d <= 0, то N (X + 1, Y) должно быть выбрано в качестве следующего пикселя.
  • Если d> 0, то S (X + 1, Y-1) должен быть выбран в качестве следующего пикселя.

Алгоритм

Шаг 1 - Получить координаты центра круга и радиуса и сохранить их в x, y и R соответственно. Установите P = 0 и Q = R.

Шаг 2 - Установите параметр решения D = 3 - 2R.

Шаг 3 - Повторите шаг 8, пока P ≤ Q.

Шаг 4 - Назовите Draw Circle (X, Y, P, Q).

Шаг 5 - Увеличить значение P.

Шаг 6 - Если D <0, то D = D + 4P + 6.

Шаг 7 - Остальное установить R = R - 1, D = D + 4 (PQ) + 10.

Шаг 8 - Назовите Draw Circle (X, Y, P, Q).

Draw Circle Method(X, Y, P, Q).

Call Putpixel (X + P, Y + Q).
Call Putpixel (X - P, Y + Q).
Call Putpixel (X + P, Y - Q).
Call Putpixel (X - P, Y - Q).
Call Putpixel (X + Q, Y + P).
Call Putpixel (X - Q, Y + P).
Call Putpixel (X + Q, Y - P).
Call Putpixel (X - Q, Y - P).

Алгоритм средней точки

Шаг 1 - Введите радиус r и центр окружности $ (x_ {c,} y_ {c}) $ и получите первую точку на окружности окружности с центром в начале координат как

(x 0 , y 0 ) = (0, r)

Шаг 2 - Рассчитайте начальное значение параметра решения как

$ P_ {0} $ = 5/4 - r (См. Следующее описание для упрощения этого уравнения.)

f(x, y) = x 2 + y 2 - r 2 = 0

f(x i - 1/2 + e, y i + 1)
        = (x i - 1/2 + e) 2 + (y i + 1) 2 - r 2 
        = (x i - 1/2) 2 + (y i + 1) 2 - r 2 + 2(x i - 1/2)e + e 2
        = f(x i - 1/2, y i + 1) + 2(x i - 1/2)e + e 2 = 0
Алгоритм средней точки
Let d i = f(x i - 1/2, y i + 1) = -2(x i - 1/2)e - e 2
Thus,

If e < 0 then di > 0 so choose point S = (x i - 1, y i + 1).
d i+1    = f(x i - 1 - 1/2, y i + 1 + 1) = ((x i - 1/2) - 1) 2 + ((y i + 1) + 1) 2 - r 2
        = d i - 2(x i - 1) + 2(y i + 1) + 1
        = d i + 2(y i + 1 - x i + 1 ) + 1
		  
If e >= 0 then di <= 0 so choose point T = (x i , y i + 1)
   d i+1 = f(x i - 1/2, y i + 1 + 1)
       = d i + 2y i+1 + 1
		  
The initial value of di is
   d 0 = f(r - 1/2, 0 + 1) = (r - 1/2) 2 + 1 2 - r 2
      = 5/4 - r {1-r can be used if r is an integer}
		
When point S = (x i - 1, y i + 1) is chosen then
   d i+1 = d i + -2x i+1 + 2y i+1 + 1
	
When point T = (x i , y i + 1) is chosen then
   d i+1 = d i + 2y i+1 + 1

Шаг 3 - На каждой позиции $ X_ {K} $, начиная с K = 0, выполните следующий тест -

If P K < 0 then next point on circle (0,0) is (X K+1 ,Y K ) and
   P K+1 = P K + 2X K+1 + 1
Else
   P K+1 = P K + 2X K+1 + 1 – 2Y K+1
	
Where, 2X K+1 = 2X K+2 and 2Y K+1 = 2Y K-2 .

Шаг 4 - Определите точки симметрии в других семи октантах.

Шаг 5 - Переместите каждую позицию расчетного пикселя (X, Y) на круговую траекторию с центром в $ (X_ {C,} Y_ {C}) $ и нанесите значения координат.

X = X + X C ,   Y = Y + Y C

Шаг 6 - Повторите шаги с 3 по 5, пока X> = Y.