Algoritmo de Geração de Linha
Uma linha conecta dois pontos. É um elemento básico em gráficos. Para desenhar uma linha, você precisa de dois pontos entre os quais você pode desenhar uma linha. Nos três algoritmos a seguir, nos referimos a um ponto da linha como $ X_ {0}, Y_ {0} $ e o segundo ponto da linha como $ X_ {1}, Y_ {1} $.
Algoritmo DDA
O algoritmo Digital Differential Analyzer (DDA) é o algoritmo de geração de linha simples que é explicado passo a passo aqui.
Step 1 - Obtenha a entrada de dois pontos finais $ (X_ {0}, Y_ {0}) $ e $ (X_ {1}, Y_ {1}) $.
Step 2 - Calcule a diferença entre dois pontos finais.
dx = X1 - X0
dy = Y1 - Y0Step 3- Com base na diferença calculada na etapa 2, você precisa identificar o número de etapas para colocar o pixel. Se dx> dy, então você precisa de mais etapas na coordenada x; caso contrário, na coordenada y.
if (absolute(dx) > absolute(dy))
Steps = absolute(dx);
else
Steps = absolute(dy);Step 4 - Calcular o incremento na coordenada xey coordenada y.
Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;Step 5 - Coloque o pixel incrementando com sucesso as coordenadas xey de acordo e conclua o desenho da linha.
for(int v=0; v < Steps; v++)
{
x = x + Xincrement;
y = y + Yincrement;
putpixel(Round(x), Round(y));
}Linha Geração de Bresenham
O algoritmo de Bresenham é outro algoritmo de conversão de varredura incremental. A grande vantagem desse algoritmo é que ele usa apenas cálculos inteiros. Movendo-se ao longo do eixo x em intervalos de unidades e em cada etapa, escolha entre duas coordenadas y diferentes.
Por exemplo, conforme mostrado na ilustração a seguir, na posição (2, 3) você precisa escolher entre (3, 3) e (3, 4). Você gostaria de ver o ponto mais próximo da linha original.
Na posição de amostra $ X_ {k} + 1, $ as separações verticais da linha matemática são rotuladas como $ d_ {superior} $ e $ d_ {inferior} $.
Da ilustração acima, a coordenada y na linha matemática em $ x_ {k} + 1 $ é -
Y = m ($ X_ {k} $ + 1) + b
Assim, $ d_ {superior} $ e $ d_ {inferior} $ são dados da seguinte forma -
$$ d_ {lower} = y-y_ {k} $$
$$ = m (X_ {k} + 1) + b - Y_ {k} $$
e
$$ d_ {superior} = (y_ {k} + 1) - y $$
$ = Y_ {k} + 1 - m (X_ {k} + 1) - b $
Você pode usá-los para tomar uma decisão simples sobre qual pixel está mais próximo da linha matemática. Esta decisão simples é baseada na diferença entre as duas posições de pixel.
$$ d_ {inferior} - d_ {superior} = 2m (x_ {k} + 1) - 2a_ {k} + 2b - 1 $$
Vamos substituir m por dy / dx onde dx e dy são as diferenças entre os pontos finais.
$$ dx (d_ {inferior} - d_ {superior}) = dx (2 \ frac {\ mathrm {d} y} {\ mathrm {d} x} (x_ {k} + 1) - 2y_ {k} + 2b - 1) $$
$$ = 2dy.x_ {k} - 2dx.y_ {k} + 2dx + 2dx (2b-1) $$
$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$
Assim, um parâmetro de decisão $ P_ {k} $ para o k- ésimo passo ao longo de uma linha é dado por -
$$ p_ {k} = dx (d_ {inferior} - d_ {superior}) $$
$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$
O sinal do parâmetro de decisão $ P_ {k} $ é o mesmo que $ d_ {inferior} - d_ {superior} $.
Se $ p_ {k} $ for negativo, então escolha o pixel inferior, caso contrário, escolha o pixel superior.
Lembre-se de que as mudanças de coordenadas ocorrem ao longo do eixo x em etapas unitárias, então você pode fazer tudo com cálculos inteiros. Na etapa k + 1, o parâmetro de decisão é dado como -
$$ p_ {k +1} = 2dy.x_ {k + 1} - 2dx.y_ {k + 1} + C $$
Subtraindo $ p_ {k} $ disto obtemos -
$$ p_ {k + 1} - p_ {k} = 2dy (x_ {k + 1} - x_ {k}) - 2dx (y_ {k + 1} - y_ {k}) $$
Mas, $ x_ {k + 1} $ é o mesmo que $ (xk) + 1 $. Então -
$$ p_ {k + 1} = p_ {k} + 2dy - 2dx (y_ {k + 1} - y_ {k}) $$
Onde, $ Y_ {k + 1} - Y_ {k} $ é 0 ou 1 dependendo do sinal de $ P_ {k} $.
O primeiro parâmetro de decisão $ p_ {0} $ é avaliado em $ (x_ {0}, y_ {0}) $ é dado como -
$$ p_ {0} = 2dy - dx $$
Agora, tendo em mente todos os pontos e cálculos acima, aqui está o algoritmo de Bresenham para inclinação m <1 -
Step 1 - Insira os dois pontos finais da linha, armazenando o ponto final esquerdo em $ (x_ {0}, y_ {0}) $.
Step 2 - Trace o ponto $ (x_ {0}, y_ {0}) $.
Step 3 - Calcule as constantes dx, dy, 2dy e (2dy - 2dx) e obtenha o primeiro valor para o parâmetro de decisão como -
$$ p_ {0} = 2dy - dx $$
Step 4 - A cada $ X_ {k} $ ao longo da linha, começando em k = 0, execute o seguinte teste -
Se $ p_ {k} $ <0, o próximo ponto a traçar é $ (x_ {k} +1, y_ {k}) $ e
$$ p_ {k + 1} = p_ {k} + 2dy $$ Caso contrário,
$$ (x_ {k}, y_ {k} +1) $$
$$ p_ {k + 1} = p_ {k} + 2dy - 2dx $$
Step 5 - Repita o passo 4 (dx - 1) vezes.
Para m> 1, descubra se você precisa incrementar x enquanto incrementa y a cada vez.
Depois de resolver, a equação para o parâmetro de decisão $ P_ {k} $ será muito semelhante, apenas o xey na equação são trocados.
Algoritmo de Ponto Médio
O algoritmo do ponto médio é devido a Bresenham que foi modificado por Pitteway e Van Aken. Suponha que você já tenha colocado o ponto P na coordenada (x, y) e a inclinação da reta seja 0 ≤ k ≤ 1, conforme mostrado na ilustração a seguir.
Agora você precisa decidir se colocar o próximo ponto em E ou N. Isso pode ser escolhido identificando o ponto de interseção Q mais próximo do ponto N ou E. Se o ponto de interseção Q estiver mais próximo do ponto N, então N é considerado como o próximo ponto; caso contrário, E.
Para determinar isso, primeiro calcule o ponto médio M (x + 1, y + ½). Se o ponto de interseção Q da linha com a linha vertical conectando E e N estiver abaixo de M, considere E como o próximo ponto; caso contrário, tome N como o próximo ponto.
Para verificar isso, precisamos considerar a equação implícita -
F (x, y) = mx + b - y
Para m positivo em qualquer X dado,
- Se y estiver na linha, então F (x, y) = 0
- Se y estiver acima da linha, então F (x, y) <0
- Se y estiver abaixo da linha, então F (x, y)> 0
