원의 수학적 표현, Bresenham Circle

--- ---

이전 포스팅에서 직선인 경우 Bresenham Algorithm 을 다루었다. 이는 래스터화 시키는 알고리즘이다.

원에서도 해당 알고리즘이 적용 가능하다. 하지만, 해상도의 문제점을 가지고 있다.

Bresenham Algorithm

직선의 경우 우측 이동(E), 우상측 이동 (NE)이동을 통해 묘사하였다.

원의 경우는 우측이동 (E) 와 우하측 이동(SE) 이동을 통해 해당 알고리즘을 적용해볼 수 있다. NE와 SE이동은 직선과 곡선의 차이점이 아니라, 기울기에 따라 달라지는 것이다.

원의 경우 8 대칭을 가지고 있다. 이 중 2번째 파이에(y,x) 해당하는 것을 묘사하는 것이 좋다. 만약 1번째 파이(x,y)에 해당하는 경우를 사용한다면, 기울기가 큰 경우가 있어 알고리즘 구현이 애매하다는 것을 알 수 있다.

원의 방정식은 다음과 같이 표현한다.

Implict

$$F(x,y)= x^2+y^2-r^2 \\ F(x,y) >0 \to (x,y) \text{ Outside} \\ F(x,y) <0 \to (x,y) \text{ Inside}$$

여기에서 마찬가지로, Outside에 해당하는 경우 Inside로 들어오기 위하여 SE 방향으로 이동, Inside인 경우 outside 방향인 E 방향으로 이동하면 된다.

$$\begin{cases} F(M) \ge 0 \to SE \\ F(M) <0 \to E \end{cases}$$

곡선의 경우 x,y 관계가 Linear하지 않아, Decision Variable $d$ 는 일정하지 않다. 이에 매 step마다 $d$ 값을 구해주어야 한다.

상세 내용은 아래 코드를 참고해보면 된다. 코드 실행 결과 아래와 같으며 Anti - aliasing 문제를 가지고 있다.

Python Code

import matplotlib.pyplot as plt
import numpy as np 
Xset = np.linspace(0,10,50)
Yset = []
radius = 5
for X in Xset:
    # x^2+y^2 = r^2
    y=np.sqrt(radius**2-X**2)
    Yset.append(y)
# plt.plot(Xset,Yset)

def circleeq (x,y,r):
    return x**2+y**2-r**2
# Making 
def directionESE(dold,x_,y_,r):
    if (dold<0):
        x_=x_+1
        dnew=circleeq(x_+1,y_-0.5,r)
    else :
        dnew=circleeq(x_+1,y_-0.5,r)
        y_=y_-1
        x_=x_+1        
    return dnew,x_,y_

xl=[]
y=[]
xl.append(Xset[0])
y.append(Yset[0])
px=float(xl[-1])
py=float(y[-1])
dold=circleeq (xl[-1]+1,py-0.5,radius)
for _ in range(3):
    dold,px,py=directionESE(dold,px,py,radius)
    xl.append(px)
    y.append(py)
# duplicate circle 8pts symmetriy
for i in range(len(xl)):
    #(-x,y)
    xl.append(xl[i]*(-1))
    y.append(y[i])
    #(-x,-y)
    xl.append(xl[i]*(-1))
    y.append(y[i]*(-1))
    #(x,-y)
    xl.append(xl[i])
    y.append(y[i]*(-1))
    #(y,x)
    xl.append(y[i])
    y.append(xl[i])
    #(-y,x)
    xl.append(y[i]*(-1))
    y.append(xl[i])
    #(y,-x)
    xl.append(y[i])
    y.append(xl[i]*(-1))
     #(-y,-x)
    xl.append(y[i]*(-1))
    y.append(xl[i]*(-1))
    
plt.scatter(xl,y)
plt.show()