DDA - KimTaebin-ai/study_posts GitHub Wiki

DDA 알고리즘은 직선 방정식을 이용해 x와 y 값을 계산하고, 이 값들을 따라 점을 찍어 선을 그립니다. 직선의 기울기 mmm를 이용해 x가 1씩 증가할 때 y 값이 얼마나 변하는지 계산하고, 반대로 y가 1씩 증가할 때 x가 얼마나 변하는지를 계산하여 점을 찍습니다.

직선 방정식은 다음과 같이 표현됩니다:

y=mx+by = mx + by=mx+b

여기서 mmm은 기울기입니다. DDA 알고리즘에서는 이 기울기 mmm을 사용해 x와 y가 증가할 때의 변화를 계산합니다.

1. 기울기 계산:

   • 시작점 (x0, y0)과 끝점 (x1, y1) 사이의 기울기 mmm을 계산합니다.
   • 기울기 mmm은 다음과 같이 구합니다: m=ΔyΔx=y1−y0x1−x0m = \frac{\Delta y}{\Delta x} = \frac{y1 - y0}{x1 - x0}m=ΔxΔy​=x1−x0y1−y0​

2. 증가값 결정:

   • x와 y의 증가량을 결정합니다.
   • 만약 dx가 dy보다 크면 x를 기준으로 움직이면서 y 값을 계산하고, 그렇지 않으면 y를 기준으로 움직이면서 x 값을 계산합니다.
   • 증가량을 다음과 같이 설정합니다:
     • dx가 크면 x가 1씩 증가할 때 y는 mmm만큼 증가합니다.
     • dy가 크면 y가 1씩 증가할 때 x는 1m\frac{1}{m}m1​만큼 증가합니다.

3. 한 픽셀씩 점 찍기:

   • 시작점에서 끝점까지 x와 y 값을 계산하면서 점을 찍어 나갑니다.
   • 각각의 계산된 x와 y 값에서 반올림하여 해당 픽셀을 채웁니다.

예를 들어, (0, 0)에서 (5, 3)까지 선을 그려보겠습니다.

1. 기본 값 계산:

   • 시작점: (0,0)(0, 0)(0,0)
   • 끝점: (5,3)(5, 3)(5,3)
   • dx=x1−x0=5−0=5dx = x1 - x0 = 5 - 0 = 5dx=x1−x0=5−0=5
   • dy=y1−y0=3−0=3dy = y1 - y0 = 3 - 0 = 3dy=y1−y0=3−0=3
   • steps: max⁡(∣dx∣,∣dy∣)=5\max(|dx|, |dy|) = 5max(∣dx∣,∣dy∣)=5 (이동 횟수)

2. 증가량 계산:

   • x 증가량 xinc=dxsteps=55=1x_{\text{inc}} = \frac{dx}{\text{steps}} = \frac{5}{5} = 1xinc​=stepsdx​=55​=1
   • y 증가량 yinc=dysteps=35=0.6y_{\text{inc}} = \frac{dy}{\text{steps}} = \frac{3}{5} = 0.6yinc​=stepsdy​=53​=0.6

3. 점 찍기:

   • 시작점에서 x는 1씩 증가하고, y는 0.6씩 증가하며 점을 찍습니다.

이렇게 하면 DDA 알고리즘에 따라 각 좌표를 따라 점들이 찍히며, (0,0)에서 (5,3)으로 이어지는 선을 얻을 수 있습니다.