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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
== Модель вычислений ==
 
== Модель вычислений ==
 
=== Арифметика ===
 
=== Арифметика ===
−
# [[Представление чисел с плавающей точкой]]
+
# [[Представление чисел с плавающей точкой]] (''5'')
−
# [[Предикат "левый поворот"]]
+
## Помёрджить с аналогичным конспектом по дискретке
−
# [[Интервальная арифметика]]
+
## Добавить код получения машинного эпсилон в c++
 +
#:* Оформить правильно источники информации
 +
#:* Поправить категории
 +
#:* Дефисы заменить на тире
 +
#:* Заменить знаки неравенств
 +
# [[Интервальная арифметика]] (''10'')
 +
## Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
 +
## И написать, что делать, если в интервальной арифметике посчиталось неточно (добавить просто пример с mpq_class)
 +
## Пару мотивационных слов о том, как надо делать вычисления (про скатывание в рациональную), о скорости и т. д.
 +
#:* Англоязычные термины
 +
#:* В формулы можно добавить пробелы для лучшей читаемости
 +
#:* Оформить правильно Источники информации
 +
#:* Добавить категории
 
# [[Adaptive precision arithmetic]]
 
# [[Adaptive precision arithmetic]]
 
=== Технические подробности ===
 
=== Технические подробности ===
Строка 10: Строка 22:
 
## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
 
## Небольшой туториал, как начать работу с библиотекой визуализации, что поставить и как запустить
 
## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
 
## Неплохо бы ещё скриншоты добавить (чтобы совсем всем всё было понятно)
−
# [[CMake_Tutorial|Туториал по cmake]] (''20'')
+
# [[CMake_Tutorial|Туториал по cmake]] (''15'')
 
## Сделать конспект более формальным
 
## Сделать конспект более формальным
 
## Как установить, что вообще надо (ссылки добавить)
 
## Как установить, что вообще надо (ссылки добавить)
Строка 24: Строка 36:
 
#:* Имя функции в \mathrm
 
#:* Имя функции в \mathrm
 
== Базовые алгоритмы и структуры данных ==
 
== Базовые алгоритмы и структуры данных ==
 +
# [[Квадродеревья | Квадродерево, сжатое квадродерево]]
 +
# [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
 +
# [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) | К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]
 +
# [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
 +
# [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов | Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
 +
# [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
 +
# [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) | Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
 
== Аффинное пространство ==
 
== Аффинное пространство ==
−
* [[Алгоритм Бентли-Оттмана]]
+
=== Простые геометрические операции и алгоритмы ===
−
* [[Трапецоидная карта]]
+
# [[Предикат "левый поворот"]] (''10'')
−
* [[Алгоритм Киркпатрика детализации триангуляции]]
+
## Перенести расчёт погрешности из конспекта про вещественные числа сюда
−
* [[Пересечение окружностей]]
+
## Сказать, почему в расчёте не используется деление, и что обычно с этим делают
−
* [[Упрощение полигональной цепи]]
+
## Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
−
* [[Ортогональный поиск]]
+
## Добавить пример, простое правило для запоминания направления
−
* [[Триангуляция полигонов (ушная + монотонная)]]
+
#:* Неплохо бы векторные картинки сделать вместо таких растровых
−
# [[ Пересечение отрезков и поворот: определение, свойства, вычисление | Пересечение отрезков и поворот: определение, свойства, вычисление ]]
+
#:* Добавить категории
−
# [[ Принадлежность точки выпуклому и невыпуклому многоугольникам | Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
+
#:* Добавить источники информации
−
# [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) | Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
+
# [[Пересечение отрезков и поворот: определение, свойства, вычисление]]
−
# [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull | Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]
+
# [[Пересечение отрезков на сфере]]
−
# [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) ]]
+
# [[Пересечение окружностей]]
−
# [[ Выпуклая оболочка в n-мерном пространстве | Выпуклая оболочка в n-мерном пространстве ]]
+
# [[Принадлежность точки выпуклому и невыпуклому многоугольникам]]
 +
# [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull]]
 +
=== Продвинутые алгоритмы ===
 +
# [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (log^2 на добавление/удаление)]]
 +
# [[Выпуклая оболочка в n-мерном пространстве]]
 +
# [[Алгоритм Бентли-Оттмана]]
 +
# [[Алгоритм Балабана]]
 +
# [[Трапецоидная карта]]
 +
# [[Алгоритм Киркпатрика детализации триангуляции]]
 +
# [[Упрощение полигональной цепи]]
 +
# [[Ортогональный поиск]]
 +
# [[Триангуляция полигонов (ушная + монотонная)]]
 
# [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
 
# [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
 
# [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
 
# [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
Строка 49: Строка 79:
 
# [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
 
# [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
 
# [[ Трапецоидная карта | Трапецоидная карта ]]
 
# [[ Трапецоидная карта | Трапецоидная карта ]]
−
# [[ Пересечение отрезков на сфере | Пересечение отрезков на сфере ]]
+
 
 
# [[BSP-дерево]]
 
# [[BSP-дерево]]
 
== Скалярное произведение и мера (проверяется) ==
 
== Скалярное произведение и мера (проверяется) ==

Версия 18:09, 18 февраля 2015

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

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

Арифметика

  1. Представление чисел с плавающей точкой (5)
    1. Помёрджить с аналогичным конспектом по дискретке
    2. Добавить код получения машинного эпсилон в c++
    • Оформить правильно источники информации
    • Поправить категории
    • Дефисы заменить на тире
    • Заменить знаки неравенств
  2. Интервальная арифметика (10)
    1. Какой-нибудь пример с кодом на c++ (желательно предикат левый поворот) и с объяснением происходящего
    2. И написать, что делать, если в интервальной арифметике посчиталось неточно (добавить просто пример с mpq_class)
    3. Пару мотивационных слов о том, как надо делать вычисления (про скатывание в рациональную), о скорости и т. д.
    • Англоязычные термины
    • В формулы можно добавить пробелы для лучшей читаемости
    • Оформить правильно Источники информации
    • Добавить категории
  3. Adaptive precision arithmetic

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

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

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

  1. Квадродерево, сжатое квадродерево
  2. Skip quadtree: определение, время работы, запрос точек в прямоугольнике
  3. К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
  4. Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
  5. Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
  6. Пересечение прямоугольника с множеством прямоугольников (priority search tree)
  7. Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)

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

Простые геометрические операции и алгоритмы

  1. Предикат "левый поворот" (10)
    1. Перенести расчёт погрешности из конспекта про вещественные числа сюда
    2. Сказать, почему в расчёте не используется деление, и что обычно с этим делают
    3. Статью написать именно про предикат поворота, про его сакральный смысл, а не про пересечение отрезков; можно добавить различных применений
    4. Добавить пример, простое правило для запоминания направления
    • Неплохо бы векторные картинки сделать вместо таких растровых
    • Добавить категории
    • Добавить источники информации
  2. Пересечение отрезков и поворот: определение, свойства, вычисление
  3. Пересечение отрезков на сфере
  4. Пересечение окружностей
  5. Принадлежность точки выпуклому и невыпуклому многоугольникам
  6. Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull

Продвинутые алгоритмы

  1. Динамическая выпуклая оболочка (log^2 на добавление/удаление)
  2. Выпуклая оболочка в n-мерном пространстве
  3. Алгоритм Бентли-Оттмана
  4. Алгоритм Балабана
  5. Трапецоидная карта
  6. Алгоритм Киркпатрика детализации триангуляции
  7. Упрощение полигональной цепи
  8. Ортогональный поиск
  9. Триангуляция полигонов (ушная + монотонная)
  10. Триангуляция многоугольника за n^2
  11. Триангуляция многоугольника заметающей прямой
  12. Пересечение полуплоскостей, связь с выпуклыми оболочками
  13. Пересечение множества отрезков
  14. Snap rounding
  15. Конфигурация
  16. ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
  17. Пересечение многоугольников (PSLG overlaying)
  18. Локализация в ППЛГ методом полос (персистентные деревья)
  19. Локализация в ППЛГ. Алгоритм Киркпатрика
  20. Трапецоидная карта
  1. 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=44890»