Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Модель вычислений == === Арифметика === === Технические подробности === == Базовые алгоритмы и...»)
 
Строка 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

Нумерованные замечания — по содержанию, маркированные — по оформлению

Модель вычислений

Арифметика

  1. Представление чисел с плавающей точкой
  2. Предикат "левый поворот"
  3. Интервальная арифметика
  4. Adaptive precision arithmetic

Технические подробности

  1. Запуск проекта визуализации cg (10)
    1. Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
    2. Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
  2. Туториал по cmake (20)
    1. Сделать конспект более формальным
    2. Как установить, что вообще надо (ссылки добавить)
    3. Простые и последовательные примеры: сборка простого файла, нескольких файлов, как подключить буст, gmp, gtest
    4. Объяснение происходящего в библиотеке визуализации cg
    5. Примеры полных скриптов
    • Добавить категории
  3. Тестирование с использованием Google Test (5)
    1. Ссылка на код битая, добавить пример кода с github
    • Задачу в Шаблон
    • Добавить категории
    • Интервики
    • Имя функции в \mathrm

Базовые алгоритмы и структуры данных

Аффинное пространство

  1. Пересечение отрезков и поворот: определение, свойства, вычисление
  2. Принадлежность точки выпуклому и невыпуклому многоугольникам
  3. Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
  4. Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
  5. Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)
  6. Выпуклая оболочка в n-мерном пространстве
  7. Триангуляция многоугольника за n^2
  8. Триангуляция многоугольника заметающей прямой
  9. Пересечение полуплоскостей, связь с выпуклыми оболочками
  10. Пересечение множества отрезков
  11. Snap rounding
  12. Конфигурация
  13. ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
  14. Пересечение многоугольников (PSLG overlaying)
  15. Локализация в ППЛГ методом полос (персистентные деревья)
  16. Локализация в ППЛГ. Алгоритм Киркпатрика
  17. Трапецоидная карта
  18. Пересечение отрезков на сфере
  19. BSP-дерево

Скалярное произведение и мера (проверяется)

  1. Диаметр множества точек (вращающиеся калиперы)
  2. Сумма Минковского (определение, вычисление)
  3. Минимальная охватывающая окружность множества точек
  4. Visibility graph и motion planning
  5. Триангуляция Делоне
  6. Диаграмма Вороного
  7. Motorcycle graph
  8. Straight skeleton
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_вычислительной_геометрии_(термы_4_и_5)&oldid=44889»