Análise matemática de dois algoritmos de traçado de retas

Traçar linhas
Gean Carlo Peixoto, Mauriverti da Silva Junior [e-mail], [e-mail]

UNIOESTE - Universidade do Oeste do Paraná
Cascavel – Paraná – Brasil
Resumo: Este documento possui como objetivo descrever o processo de análise, matemática e empírica, de dois algoritmos para traçar linhas retas em qualquer direção, o algoritmo incremental e o algoritmo do ponto médio (Bresenham).
Descrevendo a eficiência de cada um e comparando seus resultados.

1 Análise Matemática
1.1 Algoritmo incremental

1.

DrawLine(x0, y0, x1, y1) {

2.

width = y2 – y1;

3.

height = x2 – x1;

4.

m = height/width;

5.

y = y0;

5.

para x=x0 até x1 faça

6.

DrawPoint(x, arredonda(y))

7.

y += m;
Imagem 1.1 – Pseudocódigo do Algoritmo Incremental de traçado de retas.

Levando em consideração que o algoritmo vai executar 𝑛 vezes, sendo 𝑛 = (𝑥1 − 𝑥0 ) podemos utilizar o seguinte somatório para encontrarmos a complexidade do Algoritmo
Incremental (𝑓(𝑛)):
𝑛

𝑓(𝑛) = ∑ 1
𝑖=1

𝑓(𝑛) = 𝑛

Ou seja, o algoritmo 𝑓(𝑛) pertence à complexidade O(𝑛).

1.2 Algoritmo de Bresenham
1.

DrawLine(x0, y0, x1, y1) {

2.

width = y2 – y1;

3.

height = x2 – x1;

4.

error = trunca (height / 2);

5.

y = y0;

6.

para x=x0 até x1 faça

7.

DrawPoint(x, y)

8.

error = error – height;

9.

se error < 0 entâo

10.

y = y+1;

11.

error = error + width;
Imagem 1.2 – Pseudocódigo do Algoritmo de Bresenham de traçado de retas.

Como no algoritmo anterior, podemos levar em consideração que o algoritmo execute 𝑛 vezes, onde 𝑛 = (𝑥1 − 𝑥0 ) e encontraremos o mesmo somatório:
𝑛

𝑓(𝑛) = ∑ 1
𝑖=1

Ou seja, ambos os algoritmos pertencem a mesma complexidade, sendo ela 𝑂(𝑛).

2 Análise Empírica
A análise empírica dos algoritmos não conta apenas a parte de desenhar uma linha, pois como isto é executado muito rapidamente (no máximo 1 milissegundo) ficaria