Line characterizations
직선은 1차원으로 일정한 기울기를 가진다는 특성이 있다. 직선의 수학적 표현 방법으로는 Explicit 하게 또는 Implicit 하게 표현할 수 있다.
2차원인 경우 다음과 같이 나타낸다.
$$ y= mx+B$$
$$ F(x,y)=ax+by+c=0$$
두 개의 표현 방법은 실질적으로 같은 식이 된다. 수학적으로는 차이는 있지만, 방정식을 세우고 푸는데 있어서는 동일하다.
$$ \\dy= y_1-y_0 \\ dx= x_1-x0 \\ y=\frac{dy}{dx}x+B$$
우리는 Computing 하기 편하게 하기 위해서 위의 관계들을 조금 더 여러가지 관계식으로 알아두는 것이 좋다.
$$ (dy)x+(-dx)y+(dx)B =0 \\ \therefore F(x,y)=(dy)x+(-dx)y+(dx)B \\ where, \, A=dy, B=-dx , C=Bdx $$
만약 2개의 점이 주어진다고 보았을 때, 2 점 사이에 존재하는 점은 다음과 같이 표현한다.
$$ P(t)=(1-t)P_0 + tP_1 $$
이러한 관계를 가지는 것을 Affine Set에 있다고 본다.
대략적인 파이썬 코드를 가지고 그려보면, 다음과 같이 P0와 P1 사이에 점들이 존재하는 것을 알 수 있다. 여기서 P0는 1,1에 존재하고 P1은 2,2로 설정하였다.
Bresenham Algorithm
Bresenham Algorithm은 Line Rasterization 시켜서 그리는 알고리즘이다. 쉽게 말하면, 선을 Pixel 처럼 나타낸다. 이는 앞으로 이미지를 픽셀처럼 나타내기 위한 기초적인 알고리즘 이다.
Pixel의 좌표계는 정수만 허용하므로, 정수에 해당하는 값만 잘 맞추어 가져오는 것이 중요하다. 컴퓨터에서는 다음과 같은 표현으로 나타내는 것을 좋아한다. (수열의 형태)
$$f(x_{i+1}) =f(x_i)+\Delta (x_i)$$
그림만 본다면, 선을 나타내는 것은 쉽게 느껴진다. 하지만, 착각하여 점을 잘못 찍는다면 누락되는 점이 나타날 것이다. 모든 점을 표현하기 위해선 x방향과 y 방향에 대해서 방향의 선택이 중요하다.
직관적으로 생각해보면, 기울기가 크다면, y축으로 조금씩 이동하여 x축에 누락되지 않게 하는 것이 중요하다. 이 반대도 동일하다.
integer씩 증가하니 각각의 변화량은 다음과 같다. $$ \Delta x_i=1, \Delta y_i=1$$
여기서 mid point는 다음의 상황을 가정한다.
$$ M = (x_p +1, y_p +\frac{1}{2})$$
직선 방정식에 어떠한 점을 넣었을 때, 점이 선 아래에 있으면 양수, 선에 있으면 0, 선 위에 있으면 음수로 나타낸다. 해당 식을 통해서 우리는 x 방향으로 (E) 이동할 것인지, y 방향(NE)으로 이동할 것인지 결정할 수 있다.
$$\begin{cases}F(M)>0 &\mbox{선 아래, NE 방향} \\F(M)=0 &\mbox{선, E 방향} \\F(M)<0 &\mbox{선 위, E 방향} \\\end{cases}$$
Decide Midpoint (Update Rules)
Mid point를 결정하기 위해서는 decision variable d를 이용한다.
$$d=F(x_p+1,y_p+\frac{1}{2}) \\ \mbox{Let, } d= a(x_p+1)+b(y_p+\frac{1}{2})+c \\ \begin{cases}d>0 &\to NE \\d=0 &\to E \\F(M)<0 &\to E \\\end{cases}$$
d가 구해졌으면 E방향인지 NE방향인지 선택하면서 픽셀을 채워 나가면 된다. d의 업데이트 과정은 매우 간단한다.
\begin{cases} E &\to d_{new}=d_{old} +a &&\to \Delta d_{E}=dy \\ NE &\to d_{new}=d_{old}+a+b &&\to \Delta_{NE} =dy-dx \\\end{cases}
유도 과정은 쉬우나 한번 쯤 유도해보는 것이 좋다. 힌트를 주자면 case E, case NE를 가정하고, 각 방향에 대해서 new 값과 old 값을 평면방정식에 대입하면된다.
이제 d의 초기 값은 초기의 x0,y0 값에 의해서 결정된다.
$$F(x_0,y_0)=0 \to 2F(x_0,y_0)=0 \\ F(x_0+1,y_0+\frac{1}{2})=2a+b =2dy-dx \\ \therefore d_0=2dy-dx $$
(5,8)에서 (9,11)로 가는 직선에 대하여 해당 알고리즘을 그리면 좌측의 그림과 같다.
Bresenham Algorithm Code
import matplotlib.pyplot as plt
import numpy as np
P0 = np.array([5,8])
P1 = np.array([9,11])
dx= P1[0]-P0[0]
dy= P1[1]-P0[1]
d=2*dy-dx
x=[]
y=[]
x.append(P0[0])
y.append(P0[1])
# for _ in range(10):
while (x[-1]<P1[0] and y[-1]<P1[1]):
if (d>0) : # NE direction
y.append(y[-1]+1)
x.append(x[-1]+1)
d+=2*(dy-dx)
else : # E direction
x.append(x[-1]+1)
y.append(y[-1])
d+=2*dy
print(d)
plt.scatter(x,y)
plt.plot([P0[0],P1[0]],[P0[1],P1[1]])
plt.show()
댓글
댓글 쓰기