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

1 Специфика геометрических алгоритмов и структур данных Специфика геометрических алгоритмов и структур данных Основные геометрические структуры данных и операции

2 Структура лекции Основные классы задач ВГ Основные классы задач ВГ Стратегии построения алгоритмов ВГ Стратегии построения алгоритмов ВГ Общие структуры данных Общие структуры данных Записи или классы? Записи или классы? Характеристики структур данных Характеристики структур данных Структуры геометрических данных Структуры геометрических данных

3 Литература по теме Препарата Ф., Шеймос М. «Вычислительная геометрия» (глава 1). Препарата Ф., Шеймос М. «Вычислительная геометрия» (глава 1). Майкл Ласло «ВГ и компьютерная графика на С++» (главы 3, 4). Майкл Ласло «ВГ и компьютерная графика на С++» (главы 3, 4).

4 Основные классы задач ВГ Задачи анализа геометрических объектов Задачи анализа геометрических объектов Поиск подмножества (по условию) Поиск подмножества (по условию) Формально: Формально: Примеры: Локализация объектов, Близость объектов, Пересекающиеся объекты и др. Примеры: Локализация объектов, Близость объектов, Пересекающиеся объекты и др. Вычисление характеристики Вычисление характеристики Формально: Формально: Примеры: Наименьшее расстояние между объектами, Диаметр множества, Минимальный габарит, Площадь, Периметр и др. Примеры: Наименьшее расстояние между объектами, Диаметр множества, Минимальный габарит, Площадь, Периметр и др. Задачи распознавания Задачи распознавания Вердикт о наличии геометрического свойства Вердикт о наличии геометрического свойства Пример: Принадлежность объекта области, Выпуклость многоугольника и др. Пример: Принадлежность объекта области, Выпуклость многоугольника и др. Задачи синтеза геометрических объектов Задачи синтеза геометрических объектов Выпуклые оболочки набора объектов Выпуклые оболочки набора объектов Триангуляции набора объектов Триангуляции набора объектов Диаграммы Вороного набора объектов Диаграммы Вороного набора объектов Пересечение и отсечение объектов Пересечение и отсечение объектов Нахождение ядра многоугольника Нахождение ядра многоугольника и др… и др…

5 Основные стратегии построения алгоритмов ВГ Метод грубой силы (brute force) Метод грубой силы (brute force) Перебор всех комбинаций элементов с проверкой признака решения Перебор всех комбинаций элементов с проверкой признака решения Стратегия пошагового ввода (online) Стратегия пошагового ввода (online) Решение задачи для одного элемента в порядке непредсказуемого ввода Решение задачи для одного элемента в порядке непредсказуемого ввода Стратегия пошаговой выборки (жадный метод) Стратегия пошаговой выборки (жадный метод) Решение задачи для одного лучшего элемента из оставшегося набора Решение задачи для одного лучшего элемента из оставшегося набора Стратегия декомпозиции (разделяй и властвуй) Стратегия декомпозиции (разделяй и властвуй) Разделение набора на подмножества (подзадачи), независимое решение подзадач с последующим объединением их решений в единое Разделение набора на подмножества (подзадачи), независимое решение подзадач с последующим объединением их решений в единое Стратегия сканирования (заметание) Стратегия сканирования (заметание) Предварительная сортировка элементов и последовательная обработка элементов Предварительная сортировка элементов и последовательная обработка элементов

6 Общие структуры данных Записи или классы Записи или классы Массивы Массивы Статические (только для ограниченного набора данных) Статические (только для ограниченного набора данных) Динамические Динамические Списки Списки Однонаправленные/Двунаправленные Однонаправленные/Двунаправленные Замкнутые/Незамкнутые Замкнутые/Незамкнутые Список/Стек/Очередь Список/Стек/Очередь Множества (только для ограниченного набора данных) Множества (только для ограниченного набора данных) Деревья Деревья Бинарные Бинарные Графы Графы

7 Записи или классы? Record или Class? Что использовать для представления геометрических объектов? Что использовать для представления геометрических объектов? Общее правило: Если объектов может быть много, то классы использовать не стоит! Если объектов может быть много, то классы использовать не стоит! Специфика ВГ: Геометрических объектов в задачах ВГ бывает очень много! Геометрических объектов в задачах ВГ бывает очень много!

8 Характеристики некоторых общих структур данных Структура Память Подсчет элементов Доступ по индексу Поиск элемента Следующий/ предыдущий Вставка/ удаление Min/ Max МассивыN*EN*EO(1) O(N)O(N) O(N)O(N)O(N)O(N) Списки -однонаправленныеN*(E+4)O(N) O(N)O(N)O(1) / O(N)O(1)O(N) -двунаправленныеN*(E+8)O(N) O(N)O(N)O(1) O(N) Сбалансированные бинарные деревья N*(E+8)O(N)O(Log N) МножествоN бит 1 O(N) O(1) 2 O(1)O(1) 2 O(1)O(N) 2 N – кол-во элементов. E – размер данных элемента. 1 В Delphi не больше 256 элементов. 2 В Delphi не реализованы.Память Все инцидентные вершины IV Все инцидентные ребра IR Матрица смежности O(N 2) O(N)O(N) Матрица инцидентности O(N*R)O(N*R)O(R) Список ребер O(N+R)O(R)O(R) N – кол-во вершин графа. R – кол-во ребер графа.

9 Структуры геометрических данных Вектор Вектор Точка плоскости Точка плоскости Отрезок прямой Отрезок прямой Прямая линия Прямая линия Полигон Полигон Базовые операции Контроль корректности – проверка условия корректности(УК) данных Сравнение элементов – проверка условия эквивалентности(УЭ) экземпляров

10 Структура данных «Вектор» Определения в разных разделах математики: Геометрия Геометрия Вектор – направленный отрезок прямой; Вектор – направленный отрезок прямой; Линейная алгебра Линейная алгебра Вектор – упорядоченный набор чисел (a 1,a 2,…,a n ) (частный случай матрицы). Вектор – упорядоченный набор чисел (a 1,a 2,…,a n ) (частный случай матрицы). //Вещественное число TReal = double; !!! Нельзя сравнивать вещественные числа через операцию «=» (A = B), только через порог сравнения Abs(A-B)

11 Структура данных «Точка плоскости» Точка (в Евклидовой геометрии) – это одно из фундаментальных понятий геометрии, поэтому "точка" не имеет определения. Евклид определил точку как то, что нельзя разделить. (Wiki)Точка (в Евклидовой геометрии) – это одно из фундаментальных понятий геометрии, поэтому "точка" не имеет определения. Евклид определил точку как то, что нельзя разделить. (Wiki) //Точка плоскости TPoint2D = packed record x, y: TReal;//Координаты точки в СК x, y: TReal;//Координаты точки в СК end; end; //Точка плоскости через её радиус-вектор TPoint2D = packed record r: TVector2R;//Радиус-вектор точки r: TVector2R;//Радиус-вектор точки... //другие данные... //другие данные end; end; //Точка плоскости через радиус-вектор (упрощенно) TPoint2D = TVector2R; !!! Это не значит что вектор и точка – одно и тоже. Для них определены совершенно разные операции. Например, нет операции сложения точек.

12 Структура данных «Отрезок прямой линии плоскости» Отрезок прямой это множество (часть прямой), состоящее из двух различных точек и всех точек, лежащих между ними. (Wiki)Отрезок прямой это множество (часть прямой), состоящее из двух различных точек и всех точек, лежащих между ними. (Wiki) //Отрезок прямой линии через концы //Отрезок прямой линии через концы TLine2D = packed record TLine2D = packed record BeginPoint, //начальная точка отрезка BeginPoint, //начальная точка отрезка EndPoint: TPoint2D; //конечная точка отрезка EndPoint: TPoint2D; //конечная точка отрезка end; end; Через начало, длину и угол к оси Через начало, длину и угол к оси BP L Aox

13 Структура данных «Прямая линия плоскости» Прямая (в геометрии) – это одно из фундаментальных понятий геометрии, поэтому «прямая» не имеет определения. (Wiki)Прямая (в геометрии) – это одно из фундаментальных понятий геометрии, поэтому «прямая» не имеет определения. (Wiki) Способы представления прямой: Уравнение с угловым коэффициентом y=k*x+b Уравнение с угловым коэффициентом y=k*x+b !!! очень вредное – забудьте его!!! 2 точки принадлежащие прямой (аналогично отрезку). 2 точки принадлежащие прямой (аналогично отрезку). Нормальное уравнение прямой Нормальное уравнение прямой Общее уравнение прямой Ax+By+C=0 Общее уравнение прямой Ax+By+C=0 Через направляющий вектор прямой Через направляющий вектор прямой //Прямая линия через направляющий вектор TStraightLine2D = packed record TStraightLine2D = packed record Point: TPoint2D; //точка прямой Point: TPoint2D; //точка прямой DirectionVector: TVector2R; //направляющий вектор прямой DirectionVector: TVector2R; //направляющий вектор прямой end; end;

14 Структура данных «Полигон» Полигон (многоугольник) - это геометрическая фигура, определяется как замкнутая ломаная. (Wiki)Полигон (многоугольник) - это геометрическая фигура, определяется как замкнутая ломаная. (Wiki) Представляется упорядоченным набором вершин полигона. //Полигон через дин. массив вершин //Полигон через дин. массив вершин TPolygon2D = array of TPoint2D; //Полигон через список вершин //Полигон через список вершин //Вершина полигона TPolygonVertex2D = packed record Point: TPoint2D; //точка вершины Point: TPoint2D; //точка вершины //указатели на следующую и предыдущую вершину //указатели на следующую и предыдущую вершину Next, Prev: ^TPolygonVertex2D; Next, Prev: ^TPolygonVertex2D;end; //Полигон – указатель на вершину TPolygon2D = ^TPolygonVertex2D;

15 О чем это мы? О специфике геометрических алгоритмов и структур данных! Основные классы задач ВГ Основные классы задач ВГ Стратегии построения алгоритмов ВГ Стратегии построения алгоритмов ВГ Общие структуры данных Общие структуры данных Базовые операции Базовые операции Характеристики некоторых Характеристики некоторых Структуры геометрических данных Структуры геометрических данных

16 Литература по теме Препарата Ф., Шеймос М. «Вычислительная геометрия» (глава 1). Препарата Ф., Шеймос М. «Вычислительная геометрия» (глава 1). Майкл Ласло «ВГ и компьютерная графика на С++» (главы 3,4). Майкл Ласло «ВГ и компьютерная графика на С++» (главы 3,4).

17 Спасибо за внимание!!