s
Sesiya.ru

Разбиение картинной плоскости

Информация о работе

Тема
Разбиение картинной плоскости
Тип Статьи
Предмет Информатика
Количество страниц 2
Язык работы Русский язык
Дата загрузки 2014-07-02 09:47:12
Размер файла 56.87 кб
Количество скачиваний 2
Узнать стоимость учебной работы online!
  • Тип работы
  • Часть диплома
  • Дипломная работа
  • Курсовая работа
  • Контрольная работа
  • Решение задач
  • Реферат
  • Научно - исследовательская работа
  • Отчет по практике
  • Ответы на билеты
  • Тест/экзамен online
  • Монография
  • Эссе
  • Доклад
  • Компьютерный набор текста
  • Компьютерный чертеж
  • Рецензия
  • Перевод
  • Репетитор
  • Бизнес-план
  • Конспекты
  • Проверка качества
  • Единоразовая консультация
  • Аспирантский реферат
  • Магистерская работа
  • Научная статья
  • Научный труд
  • Техническая редакция текста
  • Чертеж от руки
  • Диаграммы, таблицы
  • Презентация к защите
  • Тезисный план
  • Речь к диплому
  • Доработка заказа клиента
  • Отзыв на диплом
  • Публикация статьи в ВАК
  • Публикация статьи в Scopus
  • Дипломная работа MBA
  • Повышение оригинальности
  • Копирайтинг
  • Другое
Узнать стоимость

Скачать файл с работой

Помогла работа? Поделись ссылкой

Разбиение картинной плоскости


На принципах разбиения картинной плоскости основан ряд алгоритмов. Этот прием используется и для улучшения работы других алгоритмов. Например, с помощью разбиения можно сократить количество проверок в алгоритме Робертса. Для этого картинная плоскость разбивается на равные клетки, для каждой клетки составляется список граней, проекции которых попадают в данную клетку. Для определения таких проекций они вписываются в прямоугольник, затем фиксируются клетки, занятые этим прямоугольником. Для произвольного ребра ищутся все клетки, ку¬да попадает проекция данного ребра. В итоге рассматриваются только грани, попавшие в список данных клеток.
Оценим выгоду. При прямом переборе оценка количества операций O(N2), при разбиении - O(N). Однако, требуется память для хранения информации о клетках, в которые попадает проекция ребра.
На этих же принципах основан алгоритм Варнака. Картинная плоскость разбивается на 4 равные части. При этом возможны следующие случаи:
• область пуста (в нее не попадает ни одной проекции), следовательно она закрашивается цветом фона;
• область целиком занята проекцией одной грани, следовательно она закрашивается цветом грани;
• не выполняется ни одно из вышеуказанных условий, область разбивается на части, анализ повторяется.
Очевидно, разбиение имеет смысл проводить до тех пор, пока размер области превышает один пиксел. Для части размером в 1 пиксел принимается специальное решение, например, закраска цветом ближайшей грани. Возможны и иные правила анализа активной области.
МЕТОДОД ДВОИЧНОГО РАЗБИЕНИЯ ПРОСТРАНСТВА

В основе - известный прием дихотомии (половинного деления). Пространство делится плоскостью на два полупространства. Далее используется исходная эвристика №2 (п. 6.5.1). Внутри каждого полупространства разбиение повторяется. Можно также секущую плоскость провес через произвольно выбранную грань (модификация алгоритма). Фактически строится двоичное дерево, узла! которого являются грани. Древовидные структуры достаточно легко программируются с помощью списков объектно-ориентированного подхода. Объект - грань, методы - различные виды прохода по дереву (получить следующий выше/нижележащий элемент, получить следующий элемент на том же уровне соседней ветви и т.д
Как выбрать грани для разбиения? Существует два основных критерия:
• получить как можно более сбалансированное дерево;
• минимизировать количество разбиений.
Эти критерии обычно являются взаимно исключающими, требуется компромисс.
Алгоритм работает в объектном пространстве. Его сильная сторона - независимость от положения центра проектирования (точки наблюдения). Одну и ту же сцену можно перерисовывать для разных точек наблюдение
К методам упорядочения относится также МЕТОД ПЛАВАЮЩЕГО ГОРИЗОНТА. В отличие от вышеизложенных, в этом методе сначала выводятся ближние к наблюдателю фрагменты. Пусть требуется получи каркасное изображение гладкой поверхности. Для изображения проекции ребра на картинную плоскость и пользуется растровый алгоритм, например, алгоритм Брезенхейма. При выводе очередной точки проекции видимость анализируется с учетом нижней и верхней границ уже полученной части изображения. Эти границы и зывают соответственно нижним и верхним плавающим горизонтом, т.к. в процессе работы алгоритма их пол жение меняется. Горизонты можно представить как 2 целочисленных массива. В процессе работы изображения достраивается вне области, где оно уже построено.

© Copyright 2012-2021, Все права защищены.