Este algoritmo é usado para converter uma linha em varredura. Foi desenvolvido por Bresenham. É um método eficiente porque envolve apenas operações de adição, subtração e multiplicação de inteiros. Essas operações podem ser executadas muito rapidamente para que as linhas possam ser geradas rapidamente.

Neste método, o próximo pixel selecionado é aquele que possui a menor distância da linha verdadeira.

O método funciona da seguinte maneira:

Suponha um pixel P₁'(x₁',e₁'), em seguida, selecione os pixels subsequentes à medida que avançamos até a noite, uma posição de pixel por vez na direção horizontal em direção a P₂'(x₂',e₂').

Uma vez que um pixel é escolhido em qualquer etapa

O próximo pixel é

1. Qualquer um à sua direita (limite inferior da linha)
2. Um no canto superior direito e para cima (limite superior da linha)

A linha é melhor aproximada pelos pixels que ficam a menor distância do caminho entre P₁',P₂'.

Para escolher o próximo entre o pixel inferior S e o pixel superior T.
Se S for escolhido
Nós temos x_eu+1=x_eu+1 e você_eu+1=s_eu
Se T for escolhido
Nós temos x_eu+1=x_eu+1 e você_eu+1=s_eu+1

As coordenadas y reais da linha em x = x_eu+1é
y=mx_eu+1+b

A distância de S até a linha real na direção y
s = aa_eu

A distância de T até a linha real na direção y
t = (s_eu+1)-s

assistente do comissário de polícia

Agora considere a diferença entre esses 2 valores de distância
s-t

Quando (s-t)<0 ⟹ s < t< p>

O pixel mais próximo é S

Quando (st) ≧0 ⟹ s

O pixel mais próximo é T

Essa diferença é
st = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Substituindo m por e introduzindo variável de decisão
d_eu= △x (st)
d_eu=△x (2 (x_eu+1)+2b-2y_eu-1)
=2△xy_eu-2△y-1△x.2b-2y_eu△x-△x
d_eu=2△y.x_eu-2△x.y_eu+c

Onde c= 2△y+△x (2b-1)

Podemos escrever a variável de decisão d_eu+1para o próximo deslizamento
d_eu+1=2△y.x_eu+1-2△x.y_eu+1+c
d_eu+1-d_eu=2△y.(x_eu+1-x_eu)- 2△x(y_eu+1-e_eu)

Como x_(i+1)=x_eu+1, temos
d_eu+1+d_eu=2△y.(x_eu+1-x_eu)- 2△x(y_eu+1-e_eu)

Casos especiais

Se o pixel escolhido estiver no pixel superior T (ou seja, d_eu≧0)⟹ e_eu+1=s_eu+1
d_eu+1=d_eu+2△y-2△x

Se o pixel escolhido estiver no pixel inferior T (ou seja, d_eu<0)⟹ y_{eu+1=yeu
deu+1=deu+2△y}

Finalmente, calculamos d₁
d₁=△x[2m(x₁+1)+2b-2y₁-1]
d₁=△x[2(mx₁+por₁)+2m-1]

Desde mx₁+por_eu=0 e m = , Nós temos
d₁=2△y-△x

Vantagem:

1. Envolve apenas aritmética inteira, por isso é simples.

2. Evita a geração de pontos duplicados.

3. Pode ser implementado em hardware porque não utiliza multiplicação e divisão.

4. É mais rápido em comparação com DDA (Digital Differential Analyzer) porque não envolve cálculos de ponto flutuante como o Algoritmo DDA.

Desvantagem:

1. Este algoritmo destina-se apenas ao desenho de linha básico. A inicialização não faz parte do algoritmo de linha de Bresenham. Portanto, para desenhar linhas suaves, você deve procurar um algoritmo diferente.

Algoritmo de linha de Bresenham:

Passo 1: Iniciar Algoritmo

Passo 2: Declarar variável x₁,x₂,e₁,e₂,d,eu₁,eu₂,dx,dy

Etapa 3: Insira o valor de x₁,e₁,x₂,e₂
Onde x₁,e₁são coordenadas do ponto de partida
E x₂,e₂são coordenadas do ponto final

Passo 4: Calcular dx = x₂-x₁
Calcule dy = y₂-e₁
Calcule eu₁=2*você
Calcule eu₂=2*(dy-dx)
Calcule d = eu₁-dx

Etapa 5: Considere (x, y) como ponto de partida e x_fimcomo valor máximo possível de x.
Se dx<0
Então x = x₂
s = s₂
x_fim=x₁
Se dx > 0
Então x = x₁
s = s₁
x_fim=x₂

Etapa 6: Gere ponto nas coordenadas (x,y).

Etapa 7: Verifique se a linha inteira foi gerada.
Se x > = x_fim
Parar.

Etapa 8: Calcule as coordenadas do próximo pixel
Se d<0
Então d = d + eu₁
Se d ≧ 0
Então d = d + eu₂
Incremento y = y + 1

Etapa 9: Incremento x = x + 1

Etapa 10: Desenhe um ponto das últimas coordenadas (x, y)

Etapa 11: Vá para a etapa 7

Etapa 12: Fim do Algoritmo

Exemplo: As posições inicial e final da linha são (1, 1) e (8, 5). Encontre pontos intermediários.

Solução: x₁=1
e₁=1
x₂=8
e₂=5
dx = x₂-x₁=8-1=7
você = você₂-e₁=5-1=4
EU₁=2* ∆y=2*4=8
EU₂=2*(∆y-∆x)=2*(4-7)=-6
d = eu₁-∆x=8-7=1

Programa para implementar o algoritmo de desenho de linha de 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; } 

Saída:

Diferencie entre Algoritmo DDA e Algoritmo de Linha de Bresenham:

função de protótipo c++