Bresenham 선 그리기 알고리즘

펌 :http://blog.naver.com/gyuhwa_kim?Redirect=Log&logNo=40056228173

한참을 고민했던 확장판 Bresenham 선 그리기 알고리즘 이렇게도 하는구나!!

---

(1) 0 ≤ m ≤ 1

기본적인 Bresenham 알고리즘 사용

(2) 1 < m ≤ ∞

원래 직선 l 상의 점 (x,y)들을 y' = x, x' = y 로 변환시킨 직선 l'의 기울기 m'는 0 ≤ m' < 1의 기울기를 갖는다. 즉 직선 l을 l'로 변환(전처리)시킨 후, 이것에 Bresenham 알고리즘을 적용하여 직선을 그리고, 다시 원래대로 x와 y의 값을 바꾸어 복구시킨다.

(3) -1 ≤ m ≤ 0

위의 기울기를 갖는 직선 l를 y축 대칭(x'=-x) 시킨 직선 l'의 기울기 m'는 0 ≤ m' ≤ 1의 기울기를 갖게 되므로, 직선을 y축 대칭시킨 후, Bresenham 알고리즘을 적용하여 직선을 그리고, 다시 y축 대칭을 시켜 원래의 직선을 구한다. (4) -∞ ≤ m < -1

위의 기울기를 갖는 직선 l의 경우엔 y=-x 직선에 대해 대칭시키고, x축 대칭을 시키면 0과 1사이의 기울기를 갖는 직선이 되므로, 전처리에서 y=-x 직선에 대해 대칭변환을 하고, Bresenham 알고리즘을 적용한 후 다시 x축 대칭 변환을 한 수 y=-x 직선에 대해 대칭변환을 시켜 그린다.



-위의 각 조건들을 정리한다면
① 전처리 단계

직선의 기울기 m에 대해서,

0 ≤ m ≤ 1 : 아무것도 하지 않는다.
1 < m ≤ ∞ : y=x 대칭변환을 한다.
-1 ≤ m ≤ 0 : y축 대칭변환을 한다.
-∞ ≤ m < -1 : y=-x 대칭변환, x = 0 대칭 변환을 한다.

② Bresenham 알고리즘 적용
③ 후처리 단계

원래 직선의 기울기 m에 대해서, Bresenham 알고리즘을 적용한 직선을

0 ≤ m ≤ 1 : 아무것도 하지 않는다.
1 < m ≤ ∞ : y=x 대칭변환을 한다.
-1 ≤ m ≤ 0 : y축 대칭변환을 한다.
-∞ ≤ m < -1 : x = 0 대칭 변환 y=-x 대칭변환을 한다.

---

기본 Bresenham 알고리즘. 
http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html