Ускорение алгоритма Брезенхэма


 

1) Частные случаи – горизонтальные, вертикальные и диагональные линии.

2) При разложении отрезка можно заметить, что при движении вдоль основной оси (X) по 1 , получаются группы , имеющие постоянную координату по неосновной оси (Y).

В стандартном алгоритме Брезенхэма проверка производится на каждом шаге, используя же группы , количество проверок можно .

 
 

Пусть есть отрезок длиной 35 по X и 10 по Y.

 

 

Рис. 3.3

 

. Тогда группы с неизменной Y – координатой будут иметь то 3 то 4 .

Поэтому достаточно 1 раз вычислить m, чтобы определить группы . Количество вычислений на 70%.

 

Минимальная длина группы:

Максимальная длина группы:

 

Как же располагать группы с максимальной и минимальной длиной? На каждый шаг по неосновной оси мы ставим вдоль основной. После этого решается ставить ли еще 1 или y на 1. Для этого анализируется накопленная ошибка отклонения.

 
 

Рис. 3.4

 

2-ой момент – балансирование групп . Это делается так: вначале оценивается ошибка накопления не за полный шаг на 1 , а за . Если 1-ая и последняя группы состоят из нечетного числа , получатся несимметричные начала и конец.

 



Дата добавления: 2016-07-18; просмотров: 1280;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.