Учебники

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

Ноябрь 13, 2018

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

Уравнение окружности: X2+Y2=r2, где 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 и центр круга (xc,yc) и получите первую точку на окружности окружности с центром в начале координат как 

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

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

P0 = 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 — На каждой позиции XK, начиная с 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) на круговую траекторию с центром в (XC,YC) и нанесите значения координат. 

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

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

227
Share: