Вычислительная геометрия — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основание вычислительной геометрии)
 
(не показаны 83 промежуточные версии 28 участников)
Строка 1: Строка 1:
* [[Представление чисел с плавающей точкой]]
+
== Основание вычислительной геометрии ==
* [[Предикат "левый поворот"]]
+
* [[ Аффинное пространство ]]
* [[Интервальная арифметика]]
+
* [[ Объем ]]
* [[Adaptive precision arithmetic]]
+
* [[ Скалярное произведение и метрика ]]
* [[Алгоритм Бентли-Оттмана]]
+
* [[ Однородные координаты ]]
* [[Конфигурация]]
+
* [[ Двойственное пространство ]]
* [[Список тем]]
 
  
== Сдача конспектов ==
+
== Вычисление геометрических предикатов ==
 +
* [[ Представление чисел с плавающей точкой ]]
 +
* [[ Предикат "левый поворот" ]]
 +
* [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]]
 +
* [[ Adaptive precision arithmetic ]]
 +
* [[ Интервальная арифметика ]]
  
* [https://docs.google.com/spreadsheet/pub?hl=en_US&hl=en_US&key=0Ar0nZy99lVSvdDIzR1E5R1MwdDN0MXBiOHRyQ2NVV1E&output=html Распределение тем конспектов]
+
== Пересечение отрезков ==
* Для сдачи конспекта необходимо сообщить об этом одному из редакторов:
+
* [[ Алгоритм Бентли-Оттмана ]]
** Артём Васильев
+
* [[ Пересечение множества отрезков ]]
** Андрей Комаров
+
* [[ Алгоритм Балабана ]]
** Андрей Шулаев
+
* [[ Snap rounding ]]
* Конспекты проверяются редакторами, о недочётах сообщается на странице обсуждения.
+
* [[ Пересечение отрезков на сфере ]]
  
== Презентации ==  
+
== Выпуклые оболочки ==
 +
* [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]
 +
* [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка ]]
 +
* [[ Выпуклая оболочка в n-мерном пространстве ]]
 +
* [[ Пересечение полуплоскостей, связь с выпуклыми оболочками ]]
  
* Презентация должна быть презентацией, а не полотном текста! Хорошие картинки приветствуются. Неинформативные картинки не приветствуются. Копипаст в любом виде не приветствуется.
+
== Поиск ==
 +
* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]
 +
* [[ Квадродеревья | Квадродерево, сжатое квадродерево ]]
 +
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
 +
* [[ Ортогональный поиск ]]
 +
* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
 +
* [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
 +
* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
 +
* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
 +
* [[ BSP-дерево ]]
  
* Презентации надо делать в TeX'е! Презентации в поверпоинте или аналогах будут караться отрубанием головы.
+
== Триангуляция ==
А именно, для этого стоит использовать пакет beamer. Он хороший, презентации в нём красивые, а аналогов вроде как и нет.
+
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
Почитать про него можно (внезапно!) тут: http://ru.wikipedia.org/wiki/Beamer_(LaTeX). В конце есть ссылки на документацию.
+
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
Ну, думаю, википедией все пользоваться умеют.
 
  
* При составление презентации стоит забить на оформление презентации в целом --- так как она делается в TeX'е, можно будет быстро поменять стиль.НО! Весь текст должен выглядеть красиво и правильно. Нерусские кавычки в тексте, дефисы вместо минуса или тире, курсив вместо прямого шрифта и т.д. будут неодобряться.
+
== ППЛГ и РСДС ==
По поводу внешнего вида презентации в целом придирок не будет. И вообще, надо ещё специально постараться, чтобы
+
* [[ Конфигурация ]]
что-то в TeX'е выглядело плохо.
+
* [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]]
 +
* [[ Пересечение многоугольников (PSLG overlaying) ]]
  
* Презентации надо складировать в одном месте в какой-то системе контроля версий. Я предлагаю использовать для этого систему контроля версий git, хостится всё это на [http://github.com гитхабе]. Там стоит зарегистрироваться.
+
== Алгоритмы локализации ==
[https://github.com/andrey-komarov/presentations Репозиторий]. Возможно, оно оттуда переедет.
+
* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
Там отличная регистрация, во время неё вы пройдёте курс "гит за пять минут". Если вы до этого пользовались
+
* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]
SVN-ом(а вы им пользовались, если сдавали C++), то проблем с гитом возникнуть не должно. Особо недовольным я могу сделать шпаргалку с командами гита.
+
* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
 +
* [[ Трапецоидная карта ]]
  
* Конструктивная критика приветствуется.
+
== Триангуляция Делоне и диаграмма Вороного ==
 +
* [[ Триангуляция Делоне ]]
 +
* [[ Триангуляция Делоне на сфере ]]
 +
* [[ Диаграмма Вороного ]]
 +
* [[ Motorcycle graph ]]
 +
* [[ Straight skeleton ]]
  
* Холивары "git vs SVN", "Powerpoint vs Beamer", "github vs что-то" не приветствуются. При этом, предыдущее правило имеет больший приоритет.
+
== Планирование движения (Motion planning) ==
 +
* [[ Сумма Минковского (определение, вычисление) ]]
 +
* [[ Visibility graph и motion planning ]]
  
* И, да, Антон не одобряет неторопливость!
+
== Задачи ==
 +
* [[ Диаметр множества точек (вращающиеся калиперы) ]]
 +
* [[ Минимальная охватывающая окружность множества точек ]]
 +
* [[ Пересечение окружностей ]]
 +
* [[ Упрощение полигональной цепи ]]
 +
* [[ Вычисление площади и объема ]]
 +
* [[ Пересечение выпуклых многоугольников ]]
  
Рекомендуется кому-то уже начать делать презентацию, чтобы отточить процесс её подготовки.
+
== Программирование ==
 +
* [[ CMake_Tutorial|Туториал по cmake ]]
 +
* [[ Тестирование с использованием Google Test ]]
 +
 
 +
== Организационные вопросы ==
 +
* [[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) | Правки к конспектам (year 2013)]]
 +
* [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых тем и дополнений]
 +
 
 +
----
 +
 
 +
* [[Список тем | Список тем (year 2010)]]
 +
* [[Список тем (year 2012)]]
 +
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]
 +
* [[Обсуждение:Вычислительная геометрия#Презентации | Сдача презентаций]]
 +
* [[Обсуждение:Вычислительная геометрия#Условия и чекеры | Условия и чекеры]]
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Текущая версия на 15:27, 12 декабря 2016

Основание вычислительной геометрии[править]

Вычисление геометрических предикатов[править]

Пересечение отрезков[править]

Выпуклые оболочки[править]

Поиск[править]

Триангуляция[править]

ППЛГ и РСДС[править]

Алгоритмы локализации[править]

Триангуляция Делоне и диаграмма Вороного[править]

Планирование движения (Motion planning)[править]

Задачи[править]

Программирование[править]

Организационные вопросы[править]