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

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

Обзор теории






В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений т. е. окружностей, эллипсов, парабол, гипербол, было посвящено значительное число работ. Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями, как это показано на рис. 1. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис. 1 приведены двумерные матрицы соответствующих преобразований.

Рис. 1. Генерация полной окружности из дуги в первом октанте

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке х = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргументах (рис. 2). Аналогично, если исходной точкой является у = 0, х = R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке х = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.

Рис. 2. Окружность в первом квадранте

Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис. 3 эти направления обозначены соответственно тн, тD, тv. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из:

Здесь минимизируется не квадрат расстояния, а абсолютное значение разности квадратов расстояний от центра окружности до пиксела и до окружности.

Рис. 3. Выбор пикселов в первом квадранте

Вычисления можно упростить, если заметить, что в окрестности точки (xi, уi) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис. 4.

Разность между квадратами расстояний от центра окружности до диагонального пиксела (xi + 1, yi - 1) и от центра до точки на окружности R2 равна

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

Рис. 4. Пересечение окружности и сетки растра

При i < 0 диагональная точка (xi + 1, yi - 1) находится внутри реальной окружности, т. е. это случаи 1 или 2 на рис. 4. Ясно, что в этой ситуации следует выбрать либо пиксел (xi + 1, yi) т. е. тН либо пиксел (xi + 1, yi - 1), т. е. mD. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:

При б < 0 расстояние от окружности до диагонального пиксела (mD) больше, чем до горизонтального (тН).

Напротив, если б > 0, расстояние до горизонтального пиксела (тН) больше. Таким образом,

при 6 0 выбираем тН в (xi + 1, yi)

при б > 0 выбираем mD в (xi + 1, yi - 1)

При б = 0, когда расстояние от окружности до обоих пикселов, одинаковы, выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины б, можно сократить, если заметить, что в случае 1.

так как диагональный пиксел (xi + 1, yi - 1) всегда лежит внутри окружности, а горизонтальный (xi + 1, yi) - вне ее. Таким образом, б можно вычислить по формуле

Дополнение до полного квадрата члена (уi) с помощью добавления и вычитания - 2yi + 1 дает

В квадратных скобках стоит по определению i и его подстановка

существенно упрощает выражение.

Рассмотрим случай 2 на рис. 4 и заметим, что здесь должен быть выбран горизонтальный пиксел (xi + 1, yi), так как у является монотонно убывающей функцией. Проверка компонент б показывает, что

поскольку в случае 2 горизонтальный (xi + 1, yi) и диагональный (xi + 1, yi -1) пикселы лежат внутри окружности. Следовательно, б < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (xi + 1, yi).

Если i > 0, то диагональная точка (xi + 1, yi -1) находится вне окружности, т. е. это случаи 3 и 4 на рис. 4. В данной ситуации ясно, что должен быть выбран либо пиксел (xi + 1, yi -1), т. е. mD, либо (xi, yi -1), т. е. ту. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального mD и вертикального ту пикселов, т. е.

При б' < 0 расстояние от окружности до вертикального пиксела (xi, yi -1) больше и следует выбрать диагональный шаг mD, к пикселу (xi + 1, yi -1). Напротив, в случае б' > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (xi, yi -1). Таким образом,

при б' ^ 0 выбираем mD в (xi + 1, yi -1)

при б' > 0 выбираем mv в (xi, yi -1)

Здесь в случае б' = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент б' показывает, что

поскольку для случая 3 диагональный пиксел (xi + 1, yi -1) находится вне окружности, тогда как вертикальный пиксел (xi, yi -1) лежит внутри ее. Это позволяет записать б' в виде

Дополнение до полного квадрата члена (хi) с помощью добавления и вычитания 2хi + 1 дает

Использование определения i - приводит выражение к виду

Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (xi, yi -1), так как у является монотонно убывающей функцией при возрастании x.

Проверка компонент б' для случая 4 показывает, что

поскольку оба пиксела находятся вне окружности. Следовательно, б' > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор тv.

Осталось проверить только случай 5 на рис. 4, который встречается, когда диагональный пиксел (xi + 1, yi -1) лежит на окружности, т. е. i = 0. Проверка компонент б показывает, что

Следовательно, б > 0 и выбирается диагональный пиксел (xi + 1, yi -1). Аналогичным образом оцениваем компоненты б':

б' < 0, что является условием выбора правильного диагонального шага к (xi + 1, yi -1). Таким образом, случай i = 0 подчиняется тому же критерию, что и случай i < 0 или i > 0.

Подведем итог полученных результатов:

i < 0

б 0 выбираем пиксел (xi + 1, yi) → тН

б > 0 выбираем пиксел (xi + 1, yi -1) → mD

i > 0

б' 0 выбираем пиксел (xi + 1, yi -1) → mD

б' > 0 выбираем пиксел (xi, yi -1) → тv

i = 0 выбираем пиксел (xi + 1, yi -1) → mD

Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг тН к пикселу (xi + 1, yi). Обозначим это новое положение пиксела как (i + 1). Тогда координаты нового пиксела и значение I равны

Аналогично координаты нового пиксела и значение i для шага mD к пикселу (xi + 1, yi -1) таковы:

То же самое для шага тv, к (xi, yi -1)







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



Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

Правила наложения мягкой бинтовой повязки 1. Во время наложения повязки больному (раненому) следует придать удобное положение: он должен удобно сидеть или лежать...

ТЕХНИКА ПОСЕВА, МЕТОДЫ ВЫДЕЛЕНИЯ ЧИСТЫХ КУЛЬТУР И КУЛЬТУРАЛЬНЫЕ СВОЙСТВА МИКРООРГАНИЗМОВ. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА БАКТЕРИЙ Цель занятия. Освоить технику посева микроорганизмов на плотные и жидкие питательные среды и методы выделения чис­тых бактериальных культур. Ознакомить студентов с основными культуральными характеристиками микроорганизмов и методами определения...

САНИТАРНО-МИКРОБИОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ ВОДЫ, ВОЗДУХА И ПОЧВЫ Цель занятия.Ознакомить студентов с основными методами и показателями...

Вопрос 1. Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации К коллективным средствам защиты относятся: вентиляция, отопление, освещение, защита от шума и вибрации...

Задержки и неисправности пистолета Макарова 1.Что может произойти при стрельбе из пистолета, если загрязнятся пазы на рамке...

Вопрос. Отличие деятельности человека от поведения животных главные отличия деятельности человека от активности животных сводятся к следующему: 1...

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