Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) — различия между версиями
Shersh (обсуждение | вклад) (Новая страница: «== Модель вычислений == === Арифметика === === Технические подробности === == Базовые алгоритмы и...») |
Shersh (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
+ | Нумерованные замечания {{---}} по содержанию, маркированные {{---}} по оформлению | ||
== Модель вычислений == | == Модель вычислений == | ||
=== Арифметика === | === Арифметика === | ||
+ | # [[Представление чисел с плавающей точкой]] | ||
+ | # [[Предикат "левый поворот"]] | ||
+ | # [[Интервальная арифметика]] | ||
+ | # [[Adaptive precision arithmetic]] | ||
=== Технические подробности === | === Технические подробности === | ||
+ | # [[Запуск проекта визуализации cg]] (''10'') | ||
+ | ## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить | ||
+ | ## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно) | ||
+ | # [[CMake_Tutorial|Туториал по cmake]] (''20'') | ||
+ | ## Сделать конспект более формальным | ||
+ | ## Как установить, что вообще надо (ссылки добавить) | ||
+ | ## Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest | ||
+ | ## Объяснение происходящего в библиотеке визуализации cg | ||
+ | ## Примеры полных скриптов | ||
+ | #:* Добавить категории | ||
+ | # [[Тестирование с использованием Google Test]] (''5'') | ||
+ | ## Ссылка на код битая, добавить пример кода с github | ||
+ | #:* Задачу в Шаблон | ||
+ | #:* Добавить категории | ||
+ | #:* Интервики | ||
+ | #:* Имя функции в \mathrm | ||
== Базовые алгоритмы и структуры данных == | == Базовые алгоритмы и структуры данных == | ||
== Аффинное пространство == | == Аффинное пространство == | ||
− | == Скалярное произведение и мера == | + | * [[Алгоритм Бентли-Оттмана]] |
+ | * [[Трапецоидная карта]] | ||
+ | * [[Алгоритм Киркпатрика детализации триангуляции]] | ||
+ | * [[Пересечение окружностей]] | ||
+ | * [[Упрощение полигональной цепи]] | ||
+ | * [[Ортогональный поиск]] | ||
+ | * [[Триангуляция полигонов (ушная + монотонная)]] | ||
+ | # [[ Пересечение отрезков и поворот: определение, свойства, вычисление | Пересечение отрезков и поворот: определение, свойства, вычисление ]] | ||
+ | # [[ Принадлежность точки выпуклому и невыпуклому многоугольникам | Принадлежность точки выпуклому и невыпуклому многоугольникам ]] | ||
+ | # [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) | Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]] | ||
+ | # [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull | Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]] | ||
+ | # [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) ]] | ||
+ | # [[ Выпуклая оболочка в n-мерном пространстве | Выпуклая оболочка в n-мерном пространстве ]] | ||
+ | # [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]] | ||
+ | # [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]] | ||
+ | # [[ Пересечение полуплоскостей, связь с выпуклыми оболочками | Пересечение полуплоскостей, связь с выпуклыми оболочками ]] | ||
+ | # [[ Пересечение множества отрезков | Пересечение множества отрезков ]] | ||
+ | # [[ Snap rounding | Snap rounding ]] | ||
+ | # [[Конфигурация]] | ||
+ | # [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых | ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]] | ||
+ | # [[ Пересечение многоугольников (PSLG overlaying) | Пересечение многоугольников (PSLG overlaying) ]] | ||
+ | # [[ Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья) ]] | ||
+ | # [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]] | ||
+ | # [[ Трапецоидная карта | Трапецоидная карта ]] | ||
+ | # [[ Пересечение отрезков на сфере | Пересечение отрезков на сфере ]] | ||
+ | # [[BSP-дерево]] | ||
+ | == Скалярное произведение и мера (проверяется) == | ||
+ | # [[ Диаметр множества точек (вращающиеся калиперы) | Диаметр множества точек (вращающиеся калиперы) ]] | ||
+ | # [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]] | ||
+ | # [[ Минимальная охватывающая окружность множества точек | Минимальная охватывающая окружность множества точек ]] | ||
+ | # [[ Visibility graph и motion planning | Visibility graph и motion planning ]] | ||
+ | # [[ Триангуляция Делоне | Триангуляция Делоне ]] | ||
+ | # [[ Диаграмма Вороного | Диаграмма Вороного ]] | ||
+ | # [[Motorcycle graph]] | ||
+ | # [[Straight skeleton]] |
Версия 17:37, 18 февраля 2015
Нумерованные замечания — по содержанию, маркированные — по оформлению
Содержание
Модель вычислений
Арифметика
- Представление чисел с плавающей точкой
- Предикат "левый поворот"
- Интервальная арифметика
- Adaptive precision arithmetic
Технические подробности
- Запуск проекта визуализации cg (10)
- Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
- Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
- Туториал по cmake (20)
- Сделать конспект более формальным
- Как установить, что вообще надо (ссылки добавить)
- Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
- Объяснение происходящего в библиотеке визуализации cg
- Примеры полных скриптов
- Добавить категории
- Тестирование с использованием Google Test (5)
- Ссылка на код битая, добавить пример кода с github
- Задачу в Шаблон
- Добавить категории
- Интервики
- Имя функции в \mathrm
Базовые алгоритмы и структуры данных
Аффинное пространство
- Алгоритм Бентли-Оттмана
- Трапецоидная карта
- Алгоритм Киркпатрика детализации триангуляции
- Пересечение окружностей
- Упрощение полигональной цепи
- Ортогональный поиск
- Триангуляция полигонов (ушная + монотонная)
- Пересечение отрезков и поворот: определение, свойства, вычисление
- Принадлежность точки выпуклому и невыпуклому многоугольникам
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
- Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)
- Выпуклая оболочка в n-мерном пространстве
- Триангуляция многоугольника за n^2
- Триангуляция многоугольника заметающей прямой
- Пересечение полуплоскостей, связь с выпуклыми оболочками
- Пересечение множества отрезков
- Snap rounding
- Конфигурация
- ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
- Пересечение многоугольников (PSLG overlaying)
- Локализация в ППЛГ методом полос (персистентные деревья)
- Локализация в ППЛГ. Алгоритм Киркпатрика
- Трапецоидная карта
- Пересечение отрезков на сфере
- BSP-дерево