원 생성 알고리즘

화면에 원을 그리는 것은 선을 그리는 것보다 조금 복잡합니다. 원을 생성하는 두 가지 인기있는 알고리즘이 있습니다.Bresenham’s AlgorithmMidpoint Circle Algorithm. 이러한 알고리즘은 원을 그리는 데 필요한 후속 점을 결정한다는 아이디어를 기반으로합니다. 알고리즘에 대해 자세히 논의 해 보겠습니다.

원의 방정식은 $ X ^ {2} + Y ^ {2} = r ^ {2}, $이며 여기서 r은 반지름입니다.

Bresenham의 알고리즘

래스터 표시에 연속 호를 표시 할 수 없습니다. 대신 가장 가까운 픽셀 위치를 선택하여 호를 완성해야합니다.

다음 그림에서 픽셀을 (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)가 다음 픽셀로 선택됩니다.

연산

Step 1− 원과 반경의 중심 좌표를 구하여 각각 x, y, R에 저장합니다. P = 0 및 Q = R을 설정합니다.

Step 2 − 결정 매개 변수 D = 3 – 2R을 설정합니다.

Step 3 − P ≤ Q 동안 8 단계를 반복합니다.

Step 4 − 원 그리기 (X, Y, P, Q)를 호출합니다.

Step 5 − P 값을 증가시킵니다.

Step 6 − D <0이면 D = D + 4P + 6.

Step 7 − 그렇지 않으면 R = R-1, D = D + 4 (PQ) + 10을 설정합니다.

Step 8 − 원 그리기 (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).

중간 점 알고리즘

Step 1 − 입력 반경 r 원 중심 $ (x_ {c,} y_ {c}) $ 원점을 중심으로하는 원의 원주에 대한 첫 번째 점을 다음과 같이 구합니다.

(x0, y0) = (0, r)

Step 2 − 결정 매개 변수의 초기 값을 다음과 같이 계산합니다.

$ P_ {0} $ = 5/4 – r (이 등식을 단순화하려면 다음 설명을 참조하십시오.)

f(x, y) = x2 + y2 - r2 = 0

f(xi - 1/2 + e, yi + 1)
        = (xi - 1/2 + e)2 + (yi + 1)2 - r2 
        = (xi- 1/2)2 + (yi + 1)2 - r2 + 2(xi - 1/2)e + e2
        = f(xi - 1/2, yi + 1) + 2(xi - 1/2)e + e2 = 0
Let di = f(xi - 1/2, yi + 1) = -2(xi - 1/2)e - e2
Thus,

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

Step 3 − K = 0에서 시작하는 각 $ X_ {K} $ 위치에서 다음 테스트를 수행합니다. −

If PK < 0 then next point on circle (0,0) is (XK+1,YK) and
   PK+1 = PK + 2XK+1 + 1
Else
   PK+1 = PK + 2XK+1 + 1 – 2YK+1
	
Where, 2XK+1 = 2XK+2 and 2YK+1 = 2YK-2.

Step 4 − 다른 7 개의 8 분원에서 대칭점을 결정합니다.

Step 5 − 각 계산 픽셀 위치 (X, Y)를 $ (X_ {C,} Y_ {C}) $ 중심의 원형 경로로 이동하고 좌표 값을 플로팅합니다.

X = X + XC,   Y = Y + YC

Step 6 − X> = Y가 될 때까지 3-5 단계를 반복합니다.