Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Ускорение алгоритма Брезенхэма
|
|
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-ая и последняя группы состоят из нечетного числа , получатся несимметричные начала и конец.