Introdução ao algoritmo de desenho de linha

Neste artigo, veremos um esboço do algoritmo de desenho de linha. O desenho de linhas no computador significa que a tela do computador está dividida em duas partes de linhas e colunas. Essas linhas e colunas também são conhecidas como pixels. Caso tenhamos que desenhar uma linha no computador, precisamos saber em quais pixels devem estar. Uma linha é parte de uma linha reta que se estende na direção oposta indefinidamente. A linha é definida por dois pontos finais. Sua densidade deve ser separada do comprimento da linha.
A fórmula para uma interceptação de reta da inclinação: Y = mx + b
Nesta fórmula, m é uma linha da inclinação eb é intercepto de y na linha. Nas posições (x1, y1) e (x2, y2), dois pontos de extremidade são especificados para o segmento de linha.

O valor da inclinação m e b pode ser determinado de acordo
• m = y2 - y1 / x2 - x1
• ie M = Δy / Δx

Exemplo:

Os pontos finais da linha são (0, 0) e (4, 12). Plote o resultado para calcular cada valor de y como as etapas x de 0 a 4.

Solução:

Portanto, temos uma fórmula da equação da reta: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12 - 0/4 - 0
• m = 3
A interceptação em y b é então encontrada ligando y1 e x1 à fórmula y = 3 x + b, 0 = 3 (0) + b. Portanto, b = 0, então a fórmula da linha y = 3x.
O objetivo é determinar o próximo local x, y o mais rápido possível pelo anterior.

Tipos de algoritmo de desenho de linha

Abaixo estão os tipos do algoritmo:

1. Algoritmo Diferencial Digital (DDA)

Um método de conversão incremental é um algoritmo DDA e também chamado de algoritmo diferencial digital (DDA). Essa abordagem é caracterizada pelo uso dos resultados da etapa anterior em cada cálculo.

Vejamos os exemplos abaixo:

Exemplo 1

A linha do ponto final é (x1, y1) e (x2, y2)

  • dx = x2 - x1
  • dy = y2 - y1

então, agora vamos determinar o comprimento da linha se abs (dx)> = abs (dy) então length = abs (dx) else length = abs (dy)

  • Δx = dx / comprimento
  • Δy = dy / comprimento
  • X = x1
  • Y = y1

Setpixel (redondo (x), redondo (y));

  • i = 1

while (i <= comprimento)

  • x = x + Δx;
  • y = y + A;

setpixel (arredondado (x), arredondado (y));
i = i + 1
terminar enquanto

Exemplo 2

Uma linha de pontos finais (5, 4) e (6, 9) pode ser convertida com o DDA.

Solução:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Como, dx <dy então,
• comprimento = y2 - y1 = 5
• dx = (x2 - x1) / comprimento = 1/5 = 0, 2
• dy = (y2-y1) / comprimento = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Resultado:

X1

Y1

X2

Y2

eu

Dx

Dy

Eu

X

Y

Resultado

3

2

4

7

5

.2

1

0 0

3.5

5.5

3.5, 5.5

1

3.9

1.5

3.9, 1.5

2

4.9

3.5

4.9, 3, 5

3

5.1

7, 5

5.1, 7.5

4

3.7

4.5

3.7, 4.5

5

4.5

7, 5

4.5, 7, 5

Limitação do algoritmo DDA

  • A aritmética para pontos flutuantes e arredondados são procedimentos demorados.
  • Um erro de arredondamento pode levar a uma distância do caminho real do segmento de linha longa pela localização do pixel medido.

2. O algoritmo da linha de Bresenham

O algoritmo de conversão de digitalização é o algoritmo de Bresenham. Esse algoritmo oferece a principal vantagem de usar apenas cálculos inteiros.

1. Pontos finais da linha e armazene o ponto final esquerdo em (x1, y1)
2. Para o parâmetro de decisão obter o primeiro valor Δx, ou seja, Dx, Δy, ou seja, Dy, 2 Δy e 2 Δx.
3. Inicialize o início
4. Inicialize i = 1 como um contador,
Caso contrário, o próximo ponto a ser plotado é (xk + 1, yk + 1) e repita a etapa 4 (Δx - 1) vezes.
Ajustamento
Para m> 1, podemos dizer se aumentamos x toda vez que aumentamos y.
Depois que a variável de decisão pk for resolvida, a fórmula será muito semelhante, apenas os xey na equação serão substituídos.

Resumo do algoritmo de linha de Bresenham

Essas são as seguintes vantagens do algoritmo de linha Bresenham:
• Um algoritmo incremental rápido.
• Isso usa apenas cálculos inteiros.
O DDA tem os seguintes problemas quando comparado ao algoritmo DDA:
• A linha pixelizada pode estar distante da acumulação esperada de erros de arredondamento.
• É necessário tempo para operações de arredondamento e aritmética de pontos flutuantes.

Artigos recomendados

Este foi um guia para o algoritmo de desenho de linha. Aqui discutimos o que é o algoritmo de desenho de linha, juntamente com os vários exemplos. Você também pode dar uma olhada nos seguintes artigos para saber mais:

  1. Algoritmos de aprendizado de máquina
  2. Algoritmo SVM
  3. Regressão linear simples
  4. Regressão multivariada
  5. Top Comparação de Regressão Linear vs Regressão Logística

Categoria:

Big Data