Студопедия — Алгоритм Брезенхема
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм Брезенхема






Будем рассуждать подобно алгоритму Брезенхема для отрезков (с соответствующими поправками на 4-й октант) [17]. Из двух возможных пикселов в 4-м октанте (соответствующих вертикальному и диагональному смещениям, которые обозначаются аналогично прежним s и d, см. рис. 4.10) будем выбирать тот, расстояние от окружности до которого меньше.

Рис. 4.8. Расстояния до окружности.

Для того чтобы выбрать один из двух возможных пикселей, будем сравнивать расстояния от них до окружности: где расстояние меньше - тот пиксел и будет искомым. В примере на рис. 4.8 сравниваются расстояния от точек S(xs, ys) и D(xd, yd) до окружности с радиусом R. Из евклидовой метрики получаем:

Но вычисление квадратного корня - вычислительно трудоемкая операция, поэтому при достаточно больших R мы будем заменять сравнение расстояний сравнением приближенных значений их квадратов (см. рис. 4.9):

Рис. 4.9. Приближенное сравнение расстояний.

Уменьшим два слагаемых на приблизительно одинаковые величины:

заменим на ,

заменим на

получим

Таким образом, приближенно

  1. D ближе к окружности, чем S

  1. S ближе к окружности, чем D

Рис. 4.10. Алгоритм Брезенхема для окружности

Пусть (x, y) - текущий пиксель. Обозначим

Тогда из двух возможных смещений d и s выберем.

  1. , т.е. (x+1, y + 1) ближе к окружности, чем (x, y+1):

d: Переходим в (x + 1, y + 1) и придаем соответствующие приращения F, ΔF(s), ΔF(d):

F = F +ΔF(d); ΔF(s) = ΔF(s)+4; ΔF(d) = ΔF(d)+8.
  1. , т.е. (x, y+1) ближе к окружности, чем (x + 1, y+1):

s: Переходим в (x, y + 1) и придаем соответствующие приращения F, ΔF(s), ΔF(d):

F = F +ΔF(s); ΔF(s) = ΔF(s)+4; ΔF(d) = ΔF(d)+4.

Если мы начинаем из (-R, 0), то начальные значения будут следующими:

Легко видеть, что в алгоритме все величины, связанные с F, кроме F начального, будут кратны 2. Но, если мы поделим все эти величины на 2 (в дальнейшем значения всех величин уже понимаются в этом смысле), то . Так как приращения F могут быть только целочисленными, то , где ; т.е. если отнять от всех значений, то знак F не изменится для всех T, кроме T = 0. Для того чтобы результат сравнения остался прежним, будем считать, что F = 0 теперь соответствует смещению s.

x = -r; y = 0; F = 1-r;ΔFs = 3;ΔFd = 5-2*r; while(x + y < 0){ plot8(x, y); if(F > 0) { // d: Диагональное смещение F += ΔFd; x++; y++; ΔFs += 2; ΔFd += 4; } else { // s: Вертикальное смещение F += ΔFs; y++; ΔFs += 2; ΔFd += 2; }}

Листинг 4.5. Алгоритм Брезенхема для окружности

Размерность вычислений этого алгоритма (т.е. отношение максимальных модулей значений величин, с которыми он оперирует к модулям исходных данных (в данном случае R)) равна 2.







Дата добавления: 2015-10-01; просмотров: 509. Нарушение авторских прав; Мы поможем в написании вашей работы!



Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Типовые ситуационные задачи. Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической   Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической нагрузке. Из медицинской книжки установлено, что он страдает врожденным пороком сердца....

Типовые ситуационные задачи. Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт. ст. Влияние психоэмоциональных факторов отсутствует. Колебаний АД практически нет. Головной боли нет. Нормализовать...

Эндоскопическая диагностика язвенной болезни желудка, гастрита, опухоли Хронический гастрит - понятие клинико-анатомическое, характеризующееся определенными патоморфологическими изменениями слизистой оболочки желудка - неспецифическим воспалительным процессом...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

Факторы, влияющие на степень электролитической диссоциации Степень диссоциации зависит от природы электролита и растворителя, концентрации раствора, температуры, присутствия одноименного иона и других факторов...

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия