Capítulo 1 - Criando Linhas utilizando o Algoritmo Bresenham's Line
1. Introdução
Um dos algoritmos mais fundamentais no Universo inteiro de Tipo de Algoritmo é a analise de diferença digital (DDA), isso é mais ou menos que o algoritmo da linha de Bresenham é em toda sua parte. De fato, este algoritmo é considerado um gráfico primitivo. Porém, também tem muitos outros usos não-graficos como localizando uma linha pelo mapa , ou localizando a linha de visão ou qualquer outro problemas de 'linha'.
2. Bastidores
Antes de começar, iremos analisar o problema. Nós temos uma grade 2D de pares ordenados, como um mapa; Porém, os pares ordenados que faz referência a um ponto neste "grid" devem ser números inteiros porque isto é um computador e você não pode ter 0.3 de um byte.Infelizmente, no mundo real, uma linha não se compõe apenas de pares inteiros (figura abaixo).
De fato, não a interesse na interseção das linhas na grade. A grade, estando em um computador, é uma matriz organizada assim:
0 1 2 3 4 5
+-+-+-+-+-+-+
0| | | | | | |x
+-+-+-+-+-+-+
1| | | | | | |
+-+-+-+-+-+-+
2| | | | | | |
+-+-+-+-+-+-+
3| | | | | | |
+-+-+-+-+-+-+
y
Onde (0,0) é o primeiro elemento, (1,0) é o próximo, indo até (5,3).
Você pode notar que as coordenadas cartesianas estão invertidas verticalmente. Isto é somente conceitual, você poderá inverter a gosto no seu programa. Para ver uma linha com inclinação (slope) 1/2, olhe nesta matriz (figura 007-2). Para criar a linha, eu apenas andei uma casa para baixo para cada duas casas à frente. O resultado é satisfatório, embora um tanto quadrado ( tecnicamente falando, o termo usado é "alised"). Porém, se nós tentamos uma inclinação realmente esquisita, como 0.397, nós teríamos uma estranha série de caixas. De fato, seria bem trabalhoso de desenhar usando a metodologia "1 para baixo para cada 2 ao lado". Mas felizmente, o algoritmo de Bresenham chegou para salvar a pátria.
