📄Работа №187056
Тема: РАЗРАБОТКА БЫСТРОГО АЛГОРИТМА ПОСТРОЕНИЯ ТРЕХМЕРНОЙ ТРИАНГУЛЯЦИИ ДЕЛОНЕ
Тип работы
Бакалаврская работа
Предмет
информатика
Объем:
47 листов
Год:
2021
Просмотров:
50
4470
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
АННОТАЦИЯ 3
ВВЕДЕНИЕ 7
1 Триангуляция Делоне 8
2 Системы и алгоритмы построения триангуляции Делоне 9
2.1 Обзор программных продуктов 9
2.2 Итеративный алгоритм для двухмерного пространства 10
2.3 Итеративный алгоритм для трехмерного пространства 11
3 Предлагаемый подход 13
3.1 Нормализация координат 13
3.2 Хранение тетраэдров в памяти 14
3.2.1 Уравнение плоскости и нормальный вектор, положение точки
относительно плоскости 15
3.2.2 Вершины и грани тетраэдра 16
3.2.3 Структуры данных для хранения 3 D-триангуляции 16
3.3 Построение начальной триангуляции (6 тетраэдров) 17
3.4 Локализация новой точки в существующей триангуляции 19
3.5 Перестроение тетраэдра, в который попала новая точка 19
3.6 Проверка условия Делоне 21
3.7 Перестроение пары смежных тетраэдров 21
4 Ускорение локализации новой точки 23
4.1 Использование статического кэша 24
4.2 Использование динамического кэша 25
5 Сортировка новых точек на основе кривых Гильберта 27
6 Проверка условия Делоне 30
6.1 Подстановка в уравнение описанной сферы (Матрица 5 х 5) 30
6.2 Подстановка в уравнение описанной сферы (Матрица 4 х 4) 31
6.3 Нахождение центра и радиуса описанной сферы через матрицы 4 х 4.32
6.4 Нахождение центра и радиуса описанной сферы через снижение
размерности и барицентрические координаты через длины сторон 34
6.5 Нахождение центра и радиуса описанной сферы через снижение
размерности и барицентрические координаты взятые через вершины тетраэдра 37
6.6 Нахождение центра и радиуса описанной сферы через равенство
скалярных произведений векторов и барицентрические координаты 38
6.7 Сравнение методов 39
7 Реализация 42
ЗАКЛЮЧЕНИЕ 45
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 46
ВВЕДЕНИЕ 7
1 Триангуляция Делоне 8
2 Системы и алгоритмы построения триангуляции Делоне 9
2.1 Обзор программных продуктов 9
2.2 Итеративный алгоритм для двухмерного пространства 10
2.3 Итеративный алгоритм для трехмерного пространства 11
3 Предлагаемый подход 13
3.1 Нормализация координат 13
3.2 Хранение тетраэдров в памяти 14
3.2.1 Уравнение плоскости и нормальный вектор, положение точки
относительно плоскости 15
3.2.2 Вершины и грани тетраэдра 16
3.2.3 Структуры данных для хранения 3 D-триангуляции 16
3.3 Построение начальной триангуляции (6 тетраэдров) 17
3.4 Локализация новой точки в существующей триангуляции 19
3.5 Перестроение тетраэдра, в который попала новая точка 19
3.6 Проверка условия Делоне 21
3.7 Перестроение пары смежных тетраэдров 21
4 Ускорение локализации новой точки 23
4.1 Использование статического кэша 24
4.2 Использование динамического кэша 25
5 Сортировка новых точек на основе кривых Гильберта 27
6 Проверка условия Делоне 30
6.1 Подстановка в уравнение описанной сферы (Матрица 5 х 5) 30
6.2 Подстановка в уравнение описанной сферы (Матрица 4 х 4) 31
6.3 Нахождение центра и радиуса описанной сферы через матрицы 4 х 4.32
6.4 Нахождение центра и радиуса описанной сферы через снижение
размерности и барицентрические координаты через длины сторон 34
6.5 Нахождение центра и радиуса описанной сферы через снижение
размерности и барицентрические координаты взятые через вершины тетраэдра 37
6.6 Нахождение центра и радиуса описанной сферы через равенство
скалярных произведений векторов и барицентрические координаты 38
6.7 Сравнение методов 39
7 Реализация 42
ЗАКЛЮЧЕНИЕ 45
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 46
📖 Введение
Триангуляция - сетка, составленная из симплексов, т.е. простейших фигур в данном пространстве. Двумерная триангуляция - простейший вид триангуляции, состоящий из множества треугольников. Построение двумерной триангуляции обычно производят по набору точек на плоскости. Таким образом, если задать каждой точке значение какой-то функции, то триангуляция является кусочно-линейной интерполяцией трехмерной функции. Такое применение триангуляции используется при моделировании рельефов местности. Также двумерная триангуляция помогает решить многочисленные задачи пространственного анализа и задач на графах
Трехмерная триангуляции применяется для построения физических моделей различных реальных тел. Обобщение двумерной триангуляции до трехмерной усложняет как представление и отображение результата, так и сами алгоритмы построения.
Триангуляция Делоне вышла за границы области генерации сеток для численных вычислений и вошла в область кристаллографии, металлургии, картографии, геологии, а также в область компьютерной графики. Она используется во многих приложениях, например, для реконструкции объектов по точкам рассеянных данных, моделирования твердых тел, интерполяции и извлечения изоповерхности. Она также используется в виртуальной реальности для виртуальной хирургии и т. д.
Цель данной работы состоит в следующем: найти методы оптимизации времени работы итеративного алгоритма построения триангуляции Делоне, исследовать и реализовать их.
Для достижение цели было выбрано разбить задачу на подзадачи:
1. Изучить материалы по двумерной триангуляции Делоне
2. Адаптировать итеративный алгоритм для трехмерного случая
3. Разработать кэш для локализации точки
4. Разработать алгоритм для выбора оптимального порядка точек
5. Найти и реализовать быстрый способ проверки условия Делоне
Трехмерная триангуляции применяется для построения физических моделей различных реальных тел. Обобщение двумерной триангуляции до трехмерной усложняет как представление и отображение результата, так и сами алгоритмы построения.
Триангуляция Делоне вышла за границы области генерации сеток для численных вычислений и вошла в область кристаллографии, металлургии, картографии, геологии, а также в область компьютерной графики. Она используется во многих приложениях, например, для реконструкции объектов по точкам рассеянных данных, моделирования твердых тел, интерполяции и извлечения изоповерхности. Она также используется в виртуальной реальности для виртуальной хирургии и т. д.
Цель данной работы состоит в следующем: найти методы оптимизации времени работы итеративного алгоритма построения триангуляции Делоне, исследовать и реализовать их.
Для достижение цели было выбрано разбить задачу на подзадачи:
1. Изучить материалы по двумерной триангуляции Делоне
2. Адаптировать итеративный алгоритм для трехмерного случая
3. Разработать кэш для локализации точки
4. Разработать алгоритм для выбора оптимального порядка точек
5. Найти и реализовать быстрый способ проверки условия Делоне
✅ Заключение
В ходе работы была найдена и изучена литература по 3D триангуляции, исследована задача и сложности, которые возникают при ее решении. Были рассмотрены программные продукты, решающие задачу построения трехмерной триангуляции Делоне.
Был выбран, описан итеративный алгоритм построения трехмерной триангуляции, основанный на аналогичном алгоритме для двумерной триангуляции. Были описаны методы ускорения алгоритма и реализованы необходимые для них структуры и классы. Ускорение достигалось при помощи ускорения локализации новой точки, упорядоченного ввода новых точек в триангуляцию и при помощи оптимизации проверки условия Делоне
Был выбран, описан итеративный алгоритм построения трехмерной триангуляции, основанный на аналогичном алгоритме для двумерной триангуляции. Были описаны методы ускорения алгоритма и реализованы необходимые для них структуры и классы. Ускорение достигалось при помощи ускорения локализации новой точки, упорядоченного ввода новых точек в триангуляцию и при помощи оптимизации проверки условия Делоне
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.