- •Синхронизация процессов и цепочек
- •Венгерская нотация, ссылки и ресурсы
- •Стандартные кисти, иконки, курсоры
- •Пример:
- •Введение в ресурсы
- •Курсоры, пиктограммы и растровые изображения
- •Работа с текстом
- •Работа с мышью
- •Ресурс панель диалога
- •Основные понятия машинной графики
- •Рассмотрим такие примитивы, как вершина, отрезок, воксель и модели, строящиеся на их основе, а также функциональные модели. Полигональные модели
- •Воксельные модели
- •Поверхности свободных форм (функциональные модели)
- •Проекции
- •Различают следующие проекции.
- •Алгоритм Коэна - Сазерленда отсечения прямоугольной областью
- •Метод дихотомии
- •Задача удаления невидимых линий и поверхностей
- •Удаление нелицевых граней многогранника. Алгоритм Робертса
- •Алгоритм Варнока
- •Алгоритм Вейлера-Азертона
- •Метод z-буфера
- •Методы приоритетов. Алгоритм художника.
- •Алгоритм плавающего горизонта
- •Алгоритмы построчного сканирования для криволинейных поверхностей
- •Библиотека OpenGl
- •Простейшая программа
- •Создание формы
- •Формат пикселя
- •Вершины и система координат
- •Треугольники
- •Многоугольники
- •Область рисования
- •Преобразование координат. Матрицы
- •Видовое преобразование. Масштабирование, поворот и перенос
- •Параметры вида. Перспективная проекция
- •Буфер глубины
- •Надстройки над OpenGl
- •Источник света
- •Свойства материала и модель освещения
- •Отсечение
- •Анализ алгоритмов. Модель вычислений
- •Асимптотический анализ алгоритмов
- •Анализ рекурсивных алгоритмов
- •Метод заметающей прямой
- •Метод локусов. Задачи геометрического поиска
- •Задачи регионального поиска. Многомерное двоичное дерево
- •Задачи локализации точки. Метод луча
- •Локализация точки на планарном подразбиении. Метод полос
- •Некоторые основные понятия вычислительной геометрии
- •Построение звездчатого полигона
- •Предварительная разработка алгоритма построения выпуклой оболочки на плоскости
- •Метод обода Грэхема
- •Триангуляция Делоне
- •Диаграмма Вороного
- •Построение диаграммы Вороного
- •Модель osi
- •Уровни модели tcp/ip
Задачи локализации точки. Метод луча
Рассмотрим алгоритм для решения проблемы принадлежности точки произвольному полигону. Предположим, что необходимо определить принадлежность точки а полигону р.
Для этого из некоторой удаленной точки проведем прямую линию в точку а. На этом пути может встретиться 0 или несколько пересечений границы полигона: при первом пересечении входим внутрь полигона, при втором выходим и т.д. Т. об. каждое нечетное пересечение обозначает попадание внутрь полигона р, а каждое четное – выход из него (см. рис.).
остроение
алгоритма на основе этой идеи базируется
на двух особенностях:
для решения задачи подходит любой луч, начинающийся в анализируемой точке а. Поэтому, для простоты выберем правый горизонтальный луч, начинающийся в точке а и направленный вправо параллельно полуоси +Х.
порядок расположения ребер, пересекаемых лучом безразличен, имеет значение только их количество. Следовательно, вместо моделирования движения вдоль луча определить все пересечения ребер в любом порядке, определяя четность по мере продвижения. Простейшим решением будет обход границы полигона с переключением бита четности при каждом обнаружении ребра, пересекаемого лучом.
Выделим три типа ребер полигона:
касательное ребро, если оно содержит точку а (b).
пересекающее ребро, если оно не горизонтально и луч пересекает его в некоторой точке, отличающейся от его нижней конечной точки (с).
безразличное ребро, если оно не касательное и не пересекающее (d).
При прохождении луча через пересекающие ребра бит четности меняется и результат выдается по достижению касательного ребра или завершению обхода границы полигона.
Но при прохождении луча через вершины полигона возникают особые ситуации.
Если луч проходит полностью через ребро полигона, то вообразив бесконечно малый поворот, можно увидеть, что если обе вершины ребра принадлежат лучу, то это ребро можно отбросить; если же ровно одна вершина лежит на луче, то пересечение будет учтено, когда эта вершина с большей ординатой (y).
Локализация точки на планарном подразбиении. Метод полос
Опр. Граф G=(V,E) (где V – множество вершин, E – множество ребер) называется планарным, если его можно уложить на плоскости без самопересечений. Прямолинейная укладка ребер планарного графа определяет разбиение плоскости, называемое планарным подразбиением. Пусть v – число вершин, e – число ребер и f – число граней (включая единственную бесконечную грань) такого подразбиения. Эти три параметра связаны формулой Эйлера:
v-e+f=2
Планарный граф всегда может быть уложен на плоскость так, что его ребра перейдут в прямолинейные отрезки. Графы, уложенные подобным образом называются плоскими прямолинейными графами (ППЛГ).
В основе локализации точки в подобной ситуации лежит дихотомия.
Пусть задан ППЛГ G. Проведем горизонтальные прямые через каждую его вершину (рис.1). Они разделяют плоскость на N+1 горизонтальных полос. Если провести сортировку этих полос по координате у как часть предобработки, то появится возможность найти ту полосу, в которой лежит точка z за время O(logN).
Поэтому данные отрезки можно упорядочить слева направо и использовать двоичный поиск для определения той трапеции, в которую попала точка z, потратив на это O(log N) времени. Отсюда получаем оценку времени запроса для худшего случая, равную O(logN).
Заметим, что если ребро проходит через несколько полос, то эти полосы следуют одна за другой. Т.е. нет необходимости повторять сортировку внутри каждой полосы, а можно при переходе от одной полосы к другой исключать из списка предыдущей полосы ребра, заканчивающиеся в полосе и добавлять ребра, начинающиеся в этой полосе. Будем условно считать ребра ориентированными снизу вверх. Заметающая прямая горизонтальна, движется снизу вверх. Списком точек событий являются вершины графа, упорядоченные по ординате. А статусом является последовательность ребер данной полосы. Если статус хранить в виде сбалансированного по высоте дерева, то операции “вставить” и “удалить” будут занимать время logN.
