Algoritmo de Linha de Bresenham
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 1 '(x 1 ',e 1 '), 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 2 '(x 2 ',e 2 ').
Uma vez que um pixel é escolhido em qualquer etapa
O próximo pixel é
- Qualquer um à sua direita (limite inferior da linha)
- 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 1 ',P 2 '.
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
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 é Substituindo m por Onde c= 2△y+△x (2b-1) Podemos escrever a variável de decisão d eu+1 para o próximo deslizamento Como x_(i+1)=x eu +1, temos Casos especiais Se o pixel escolhido estiver no pixel superior T (ou seja, d eu ≧0)⟹ e eu+1 =s eu +1 Se o pixel escolhido estiver no pixel inferior T (ou seja, d eu <0)⟹ y eu+1=y eu Finalmente, calculamos d 1 Desde mx 1 +por eu =0 e m = 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. 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. Passo 1: Iniciar Algoritmo Passo 2: Declarar variável x 1 ,x 2 ,e 1 ,e 2 ,d,eu 1 ,eu 2 ,dx,dy Etapa 3: Insira o valor de x 1 ,e 1 ,x 2 ,e 2 Passo 4: Calcular dx = x 2 -x 1 Etapa 5: Considere (x, y) como ponto de partida e x fim como valor máximo possível de x. Etapa 6: Gere ponto nas coordenadas (x,y). Etapa 7: Verifique se a linha inteira foi gerada. Etapa 8: Calcule as coordenadas do próximo pixel 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 =1 Saída:
st = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
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
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 )
d eu+1 +d eu =2△y.(x eu +1-x eu )- 2△x(y eu+1 -e eu )
d eu+1 =d eu +2△y-2△x
d eu+1 =d eu +2△y
d 1 =△x[2m(x 1 +1)+2b-2y 1 -1]
d 1 =△x[2(mx 1 +por 1 )+2m-1] , Nós temos
d 1 =2△y-△x Vantagem:
Desvantagem:
Algoritmo de linha de Bresenham:
Onde x 1 ,e 1 são coordenadas do ponto de partida
E x 2 ,e 2 são coordenadas do ponto final
Calcule dy = y 2 -e 1
Calcule eu 1 =2*você
Calcule eu 2 =2*(dy-dx)
Calcule d = eu 1 -dx
Se dx <0
Então x = x 2
s = s 2
x fim =x 1
Se dx > 0
Então x = x 1
s = s 1
x fim =x 2
Se x > = x fim
Parar.
Se d <0
Então d = d + eu 1
Se d ≧ 0
Então d = d + eu 2
Incremento y = y + 1
e 1 =1
x 2 =8
e 2 =5
dx = x 2 -x 1 =8-1=7
você = você 2 -e 1 =5-1=4
EU 1 =2* ∆y=2*4=8
EU 2 =2*(∆y-∆x)=2*(4-7)=-6
d = eu 1 -∆x=8-7=1
x e d = d + eu 1 ou eu 2 1 1 d + eu 2 =1+(-6)=-5 2 2 d + eu 1 =-5+8=3 3 2 d + eu 2 =3+(-6)=-3 4 3 d + eu 1 =-3+8=5 5 3 d + eu 2 =5+(-6)=-1 6 4 d + eu 1 =-1+8=7 7 4 d + eu 2 =7+(-6)=1 8 5 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; } 
Diferencie entre Algoritmo DDA e Algoritmo de Linha de Bresenham:
Algoritmo DDA Algoritmo de Linha de Bresenham 1. O algoritmo DDA usa ponto flutuante, ou seja, aritmética real. 1. O algoritmo de linha de Bresenham usa ponto fixo, ou seja, aritmética de inteiros 2. Algoritmos DDA usam multiplicação e divisão para sua operação 2. O algoritmo de linha de Bresenham usa apenas subtração e adição em sua operação 3. O algoritmo DDA é mais lento que o algoritmo de linha de Bresenham no desenho de linha porque usa aritmética real (operação de ponto flutuante) 3. O Algoritmo de Bresenham é mais rápido que o Algoritmo DDA em linha porque envolve apenas adição e subtração em seu cálculo e usa apenas aritmética inteira. 4. O algoritmo DDA não é preciso e eficiente como o algoritmo de linha de Bresenham. 4. O algoritmo de linha de Bresenham é mais preciso e eficiente no algoritmo DDA. 5. O algoritmo DDA pode desenhar círculos e curvas, mas não é preciso como o algoritmo de linha de Bresenham 5. O algoritmo de linha de Bresenham pode desenhar círculos e curvas com mais precisão do que o algoritmo DDA.
