이 알고리즘은 라인을 스캔 변환하는 데 사용됩니다. Bresenham이 개발했습니다. 정수 덧셈, 뺄셈, 곱셈 연산만 포함하기 때문에 효율적인 방법입니다. 이러한 작업은 매우 빠르게 수행될 수 있으므로 선을 빠르게 생성할 수 있습니다.

이 방법에서는 실제 선과의 거리가 가장 짧은 픽셀을 다음 픽셀로 선택합니다.

이 방법은 다음과 같이 작동합니다.

픽셀 P를 가정합니다.₁'(엑스₁',그리고₁') 그런 다음 밤까지 작업하면서 다음 픽셀을 선택합니다. P 방향으로 수평 방향으로 한 번에 한 픽셀씩 위치합니다.₂'(엑스₂',그리고₂').

어떤 단계에서든 픽셀을 선택하면

다음 픽셀은

1. 오른쪽에 있는 것(선의 하한)
2. 하나는 오른쪽 위로 올라갑니다(선의 위쪽 경계).

선은 P 사이의 경로에서 가장 짧은 거리에 있는 픽셀에 의해 가장 잘 근사화됩니다.₁',피₂'.

하단 픽셀 S와 상단 픽셀 T 사이에서 다음 픽셀을 선택합니다.
S를 선택한 경우
우리에겐 x가 있어요_나+1=x_나+1과 y_나+1=y_나
T를 선택한 경우
우리에겐 x가 있어요_나+1=x_나+1과 y_나+1=y_나+1

x = x에서 선의 실제 y 좌표_나+1~이다
y=mx_나+1+b

S에서 y 방향의 실제 선까지의 거리
s = y-y_나

T에서 y 방향의 실제 선까지의 거리
티 = (와이_나+1)-y

이제 이 두 거리 값의 차이를 고려해보세요.
성

언제 (s-t)<0 ⟹ s < t< p>

가장 가까운 픽셀은 S입니다.

(s-t) ≧0 ⟹ 초일 때

가장 가까운 픽셀은 T

이 차이는
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

m을 다음으로 대체하면 그리고 의사결정 변수 도입
디_나=Δx(s-t)
디_나=Δx (2 (엑스_나+1)+2b-2y_나-1)
=2Δxy_나-2Δy-1Δx.2b-2y_나△x- △x
디_나=2Δy.x_나-2Δx.y_나+c

여기서 c= 2Δy+Δx (2b-1)

결정 변수 d를 쓸 수 있습니다._나+1다음 슬립온을 위해
디_나+1=2Δy.x_나+1-2Δx.y_나+1+c
디_나+1-디_나=2Δy.(x_나+1-엑스_나)- 2Δx(y_나+1-그리고_나)

x_(i+1)=x이므로_나+1, 우리는
디_나+1+디_나=2Δy.(x_나+1-x_나)- 2Δx(y_나+1-그리고_나)

특수한 상황들

선택한 픽셀이 상단 픽셀 T에 있는 경우(즉, d_나≧0)⟹ 그리고_나+1=y_나+1
디_나+1=d_나+2Δy-2Δx

선택한 픽셀이 아래쪽 픽셀 T에 있는 경우(즉, d_나<0)⟹ y_{나는+1=y나
디나+1=d나+2Δy}

마지막으로 d를 계산합니다.₁
디₁=Δx[2m(x₁+1)+2b-2y₁-1]
디₁=Δx[2(mx₁+b-y₁)+2m-1]

mx 이후₁+b-y_나=0 및 m = , 우리는
디₁=2Δy-Δx

이점:

1. 정수 연산만 포함하므로 간단합니다.

2. 중복 포인트 생성을 방지합니다.

3. 곱셈과 나눗셈을 사용하지 않기 때문에 하드웨어를 이용하여 구현이 가능하다.

4. DDA 알고리즘과 같은 부동소수점 계산을 포함하지 않기 때문에 DDA(Digital Differential Analyser)에 비해 속도가 빠릅니다.

그렇지 않으면 자바에서 루프가 발생합니다.

불리:

1. 이 알고리즘은 기본 선 그리기에만 사용됩니다. 초기화는 Bresenham 선 알고리즘의 일부가 아닙니다. 따라서 부드러운 선을 그리려면 다른 알고리즘을 살펴봐야 합니다.

Bresenham의 선 알고리즘:

1 단계: 알고리즘 시작

2 단계: 변수 x 선언₁,엑스₂,그리고₁,그리고₂,디,나₁,나₂,dx,dy

3단계: x 값을 입력하세요.₁,그리고₁,엑스₂,그리고₂
여기서 x₁,그리고₁시작점 좌표입니다
그리고 x₂,그리고₂끝점 좌표입니다

4단계: dx = x 계산₂-엑스₁
dy = y 계산₂-그리고₁
i를 계산하다₁=2*당신
i를 계산하다₂=2*(dy-dx)
d=i 계산₁-dx

5단계: (x, y)를 시작점으로 고려하고 x_끝x의 가능한 최대값으로.
만약 dx라면<0
그러면 x = x₂
와이 = 와이₂
엑스_끝=x₁
dx > 0인 경우
그러면 x = x₁
와이 = 와이₁
엑스_끝=x₂

6단계: (x,y) 좌표에서 점을 생성합니다.

7단계: 전체 라인이 생성되었는지 확인하십시오.
x > = x인 경우_끝
멈추다.

8단계: 다음 픽셀의 좌표를 계산합니다.
만약 d<0
그러면 d = d + i₁
d ≧ 0이면
그러면 d = d + i₂
y 증가 = y + 1

9단계: 증분 x = x + 1

10단계: 최신 (x, y) 좌표의 점을 그립니다.

11단계: 7단계로 이동

12단계: 알고리즘의 끝

예: 라인의 시작과 끝 위치는 (1, 1)과 (8, 5)입니다. 중간 지점을 찾아보세요.

해결책: 엑스₁=1
그리고₁=1
엑스₂=8
그리고₂=5
dx=x₂-엑스₁=8-1=7
당신=y₂-그리고₁=5-1=4
나₁=2* Δy=2*4=8
나₂=2*(Δy-Δx)=2*(4-7)=-6
d = 나₁-Δx=8-7=1

Bresenham의 선 그리기 알고리즘을 구현하는 프로그램:

 #include #include void drawline(int x0, int y0, int x1, int y1) { int dx, dy, p, x, y; dx=x1-x0; dy=y1-y0; x=x0; y=y0; p=2*dy-dx; while(x=0) { putpixel(x,y,7); y=y+1; p=p+2*dy-2*dx; } else { putpixel(x,y,7); p=p+2*dy;} x=x+1; } } int main() { int gdriver=DETECT, gmode, error, x0, y0, x1, y1; initgraph(&gdriver, &gmode, 'c:\turboc3\bgi'); printf('Enter co-ordinates of first point: '); scanf('%d%d', &x0, &y0); printf('Enter co-ordinates of second point: '); scanf('%d%d', &x1, &y1); drawline(x0, y0, x1, y1); return 0; } 

산출:

DDA 알고리즘과 Bresenham의 라인 알고리즘을 구별합니다.