1. 점과 선

1.1. 점

• 기하적 공간에서 좌표(x,y)로 저의
• 속성 : 크기, 명암, 색상, 모양 등

1.2. 선

• 시작점과 끝점의 절대좌표로 정의
• 또는 시작점 좌표와 좌표의 증가값의 상대좌표로 정의
• 속성 : 선의 유형(Line Type), 굵기(Width),색상, 선끝 모양(Line Cap)등

1.3. 다중선(Polyline)

• 시작점부터 마지막 n번째 점까지의 절대 좌표로 정의
• 또는 시작점과 각 좌표의 증가값들로 정의
• 선의 속성이외에 추가로 선이음 등의 속석을 가짐

2. DDA 선 그리기 알고리즘

• 곱하기 없이 소수점 더하기 연산만을 반복
• 매번 정수좌표를 구할 때 마다 오차가 축적

2.1. 기본 개념

• 선의 양끝 좌표로부터 래스터 출력장치로 변환하는 가장 기본적인 알고리즘
  Y = mX+b
  Yi = mXi+b
  Y(i+1) = mX(i + 1) + b
  Y(i+1) = m(Xi + △X) + b
  Y(i+1) = mXi + (m△X) + b
  Y(i+1) = Yi + (m△X)
  X축을 1씩 증가시키니 △X = 1이다.
  Y(i+1) = Yi + m
  따라서 X축이 1씩 증가 할때, Y축은 m씩 증가한다.
  (Y축값이 실수로 나오게 되는데 이대 반올림을 해주면 된다.)

2.2. 알고리즘 코드

void lineDDA(int x1, int y1, int x2, int y2)
{
	int dx=x2-x1, dy=y2-y1, step, k;
	float xinc, yinc, x=(float)x1, y=(float)y1;

	if(abs(dx) > abs(dy)) step = abs(dx);
	else step = abs(dy);
	xinc = dx/(float)step;
	yinc = dy/(float)step;

	Iarray[x1][y1] = 0; // start pixel marking(setpixel function)
	for(k=0;k<step;k++){
		x += xinc;
		y += yinc;
		Iarray[(int)(x+0.5)][(int)(y+0.5)]=0;// marking(setpixel function)
	}
}

1) 초기화

• dx,dy를 구함
• x,y값을 초기값으로 지정

2)장축구하기

• dx와 dy의 길이를 비교해 장축 구함
• x,y의 증가값 구하기

3) 시작위치에 marking

4) 다음 pixel위치 구하기

• x,y에 증가값 더함
• x,y를 반올림
• 구한 x,y의 위치에 mark

5) 4번을 장축 길이만큼 반복

3. Bresenham 선 그리기 알고리즘

• 소수점 계산 없이 정수의 더하기 연산과 시프트 연산만으로 처리

3.1 기본 개념

1) 기울기가 1이하인 경우

• p0 = 2dy - dx
• pi가 0보다 작다면, x += 1, pi+1 = pi + 2dy
• pi가 0보 이상이면, x += 1, y += 1, pi+1 = pi + 2(dy - dx)
  2) 기울기가 1초과인 경우
• p0 = 2dx - dy
• pi가 0보다 작다면, y += 1, pi+1 = pi + 2dx
• pi가 0보 이상이면, x += 1, y += 1, pi+1 = pi + 2(dx - dy)

3.2 알고리즘 코드

void lineBres(int x1, int y1, int x2, int y2)
{
	int dx=abs(x2-x1), dy=abs(y2-y1);
	int p, twoDy, twoDyDx;
	int x,y,xEnd,IorD;

	if(dx > dy){ 
		p=2*dy-dx; twoDy=2*dy; twoDyDx=2*(dy-dx);

		if(x1>x2)
		{
			x=x2;y=y2;xEnd=x1;
			if(y1-y2>0)IorD=1;
			else IorD=-1;
		}

		else
		{
			x=x1;y=y1;xEnd=x2;
			if(y2-y1>0)IorD=1;
			else IorD=-1;
		}

		Iarray[x][y][0]=r; Iarray[x][y][1]=g; Iarray[x][y][2]=b;// start point marking with a user-defined color(r,g,b) 

		while(x<xEnd){
			x++;
			if(p<0) p+=twoDy;
			else{ y+=IorD; p+=twoDyDx;}
			Iarray[x][y][0]=r; Iarray[x][y][1]=g; Iarray[x][y][2]=b;//marking
		}// end of while
	}// end of if
	else{
		p = 2 * dx - dy;
		twoDy = 2 * dx; twoDyDx = 2 * (dx - dy); //변화는값 계산해놓음

		if (x1 > x2)
		{
			x = x2; y = y2; xEnd = x1;	//아래에서 그리기
			if (y1 - y2 > 0)IorD = 1;	//기울기가 양수면 1 음수면 -1
			else IorD = -1;
		}
		else
		{
			x = x1; y = y1; xEnd = x2;	//아래에서 그리기
			if (y2 - y1 > 0)IorD = 1;	//기울기가 양수면 1 음수면 -1
			else IorD = -1;
		}

		//마지막 배열 index : RGB
		Iarray[x][y][0] = r; Iarray[x][y][1] = g; Iarray[x][y][2] = b;// start point marking with a user-defined color(r,g,b) 

		while (y < yEnd) {
			y++;	//x는 1씩증가 y는 유지 or 증가
			if (p < 0) p += twoDy; //y : 유지
			else { x += IorD; p += twoDyDx; }//y:변화
			Iarray[x][y][0] = r; Iarray[x][y][1] = g; Iarray[x][y][2] = b;//marking
		}
	}

}