[알고리즘] DDA알고리즘

선분그리기를 할 때 이런저런알고리즘이 있는데요~

그 중 간단하고 직선의 방정식에 원리에 가장 가까운 방법인(오차가 있긴하지만)

DDA알고리즘에 대해 포스팅하겠습니다.

Digital Differential Analyzer

Digital : 디지털 방식을 쓰는

Differential : 차이, 격차

Analyzer : 분석자, 분해자, 분석적으로 검토하는 사람, 분석기

먼저 Digital의 뜻은 대충은 알지만 정확히 정의하기 위해 사전을 찾아봤습니다.

---------------------------------------------------------------------------------------------

디지트(digit)는 사람의 손가락이나 동물의 발가락이라는 의미에서 유래한 말이다. 

아날로그와 대응되는 의미로, 임의의 시간에서 값이 최소값의 정수배로 되어 있고, 

그 이외의 중간값을 취하지 않는 양을 가리킨다. 

구체적 예로, 디지털 시계가 있다. 

데이터를 한 자리씩 끊어서 다루므로 애매모호한 점이 없고 정밀도를 높일 수 있다

[네이버 지식백과] 디지털 [digital] (두산백과)

http://terms.naver.com/entry.nhn?docId=1086177&cid=40942&categoryId=32828

---------------------------------------------------------------------------------------------

중간값을 취하지 않는 양

<- 중요, 이게 DDA알고리즘의 핵심이라고 생각됩니다.

 

 

 

직선의 방정식

 

위와 같은 건 직선의 방정식 그대로인 직선입니다.

이런 순으로 좌표가 찍혀 기울기가 0.5, y절편이 1인 직선이 만들어집니다.

앞으로 기울기는 m이나 기울기라고 표시하겠습니다.

 

 

 

 

 

 

 

DDA알고리즘 원리 및 조건

1. x축 좌표를 1씩 움직여줍니다.
2. 그 때 y축 좌표는 직선의 기울기(m)만큼 변화시켜 다음 점을 계산합니다.
3. 계산된 다음 점을 찍어줍니다.

위는 DDA알고리즘을 간단히 설명한것이구요
이해하기 쉽고 자세한건 아래 그림과 글로 설명하겠습니다. 

1. 먼저 기울기의 절대값을 확인해줍니다.   2. 기울기가 1보다 작으면 x축을 기준으로 잡고 (반대로 기울기가 1보다 크면 y축을 기준)   3. x축을 1씩 이동시키고 y값은 y값에 기울기를 더 해줍니다.  (반대로 기울기가 1보다 크면 y축을 기준으로 잡고 y축을 1씩 이동시키고 그 때  x값은 x값에 기울기의 역수를 더 해줍니다.)   4. 나온값이 실수라면 반올림을 한 좌표에 점을 찍어줍니다.

 

 

| 기울기 기준

먼저 기울기로 왜 x축과 y축을 결정하냐에 대해서는

기울기가 1보다 커지면 x를 1만큼 이동하는 걸 기준으로 잡을 수 없기 때문입니다.

y축을 기준으로 잡으면 y를 1씩 옮기는것이 (기울기가 1보다 작을 때)x를 1 옮기는 것과 같아집니다.

 

 

 

 

| 다음 좌표 구하기 원리

다음 좌표를 구할 때 기울기를 더해주는것에 관한건데요.

x축을 기준으로 하면 y값에 기울기를 더하고 그 반대는 기울기의 역수를 더하는것에 대한 건 아래를 보면 알 수 있습니다.

 

y = mx + b 에서 m은 y증가량 / x증가량입니다.

 

 

여기서 x값의 증가량은 1, y값의 증가량은 0.5이므로 0.5/1 -> 분모가 1이니 생략 -> 기울기는 0.5라고 나옴

이 때 첫번째 좌표값(x0, y0)을 직선의 방정식에 대입해 구해주면 y값은 1

그 다음부터는 기존 y값에 m을 더 한 값이 다음 y값이 됩니다.

x0 = 0일 때 y0 = mx(0.5 * 0) + 1(y절편) = 1 x1 = 1일 때 y1 = 1(y0) + m = 1.5   x2 = 2일 때 y2 = 1.5(y1) + m = 2

반대로 x값은 왜 기울기의 역수냐?하면

x는 기울기의 역수를 y에 곱해줘서 구하기 때문입니다.

(위는 계산하기 편하게 y절편이 0이라고 정의한 직선의 방정식)

 

 

그리고 기존 그림에 직선의 방정식으로 x값을 계산해보면 아래와 같이 나옵니다.

정리하자면 다음 좌표를 찍기 위한 공식은

y1 = y0 + m  x1 = x0 + m의 역수

 

 

| 정수로 반올림

 

아까 x0과 y0의 좌표 후 x1, y1의 좌표를 구했죠?

좌표가 실수라면 반올림해서 정수로 만들어 점을 찍는 것이 DDA알고리즘입니다.

 

디지털의 설명과 같은 의미가 있는듯합니다~ 중간값을 취하지 않는 양 말이죠~

 

 

 

 

 

위 그림 나온값이 실수면 반올림을 해서 좌표를 찍어줘야되니

이런 식이 되겠습니다. 반대로 y축 기준일때는 역수랑 반대로 써주면 되구요.

 

 

 

 

 

 

 

DDA 알고리즘 구현

 

void DDA(int _iStartX, int iStartY, int iEndX, int iEndY) {      int iDisX = iEndX - _iStartX;                     // 먼저 X와 Y의 끝점에서 시작점을 때 각각의 증가량(거리)를 구해줍니다.      int iDisY = iEndY - _iStartY;      float fCurX = _iStartX;                            // 현재 X와 Y좌표      float fCurY = _iStartY;      int iTotalDis = 0;                                   // 기준축의 총 거리          iTotalDis =  abs(iDisX) > abs(iDisY) ? abs(iDisX) : abs(iDisY);     // X와 Y의 거리(증가량)을 비교해서 더 큰 게 기준축이 됩니다.           PutPixel( Round(fCurX), Round(fCurY) );     // 처음 시작 좌표를 실수라면 반올림해서 찍어줍니다.             float fIncX = abs(iDisX) / iTotalDis;           // X의 길이를 기준으로 잡은 TotalDis로 나눠줍니다.                                                             // (만약 DisX의 길이가 5이고 iTotalDis가 5면 X축 기준이고 증가량은 1입니다.             float fIncY = abs(iDisY) / iTotalDis;           // Y의 증가량도 기준으로 잡은 TotalDis로 나눠줘 구해줍니다.                                                             // (만약 DisY의 길이가 2이면 기준축은 X, 나눠주면 Y의 증가값 나옴->)        for( int i = 0; i < TotalDis; ++i )              // 0부터 기준축의 거리만큼 1씩 증가하면서 반복      {           fCurX += fIncX;                              // 아까 X축 기준이라면 1증가함            fCurY += fIncY;                              // Y는 기존 Y값에 Y증가량 더해줌           PutPixel( Round(fCurX), Round(fCurY) );   // 반올림해서 찍어주기      } }

 

 

 

 

 

단점

- 긴 선분일수록 오차가 누적되 잘 못 그려질 수 있습니다.

- 소수점계산 및 반올림을 해서 연산속도가 오래 걸립니다.

 

 

 

여태까지 봐주셔서 감사합니다~

다음은 브레젠헴 알고리즘을 포스팅하겠습니다.