113
правок
Изменения
→Основание вычислительной геометрии
== Сдача конспектов Вычисление геометрических предикатов ==* [[ Представление чисел с плавающей точкой ]]* [[ Предикат "левый поворот" ]]* [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]]* [[ Adaptive precision arithmetic ]]* [[ Интервальная арифметика ]]
== Презентации Выпуклые оболочки == * [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, 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. Он хороший, презентации в нём красивые, а аналогов вроде как и нет.Почитать про него можно [[ Триангуляция полигонов (внезапно!ушная + монотонная) тут: http://ru.wikipedia.org/wiki/Beamer_#Ушной метод | Триангуляция многоугольника за n^2]]* [[ Триангуляция полигонов (LaTeXушная + монотонная). В конце есть ссылки на документацию. Ну, думаю, википедией все пользоваться умеют.| Триангуляция многоугольника заметающей прямой ]]
== ППЛГ и РСДС ==* При составление презентации стоит забить на оформление презентации в целом --- так как она делается в TeX'е, можно будет быстро поменять стиль.НО! Весь текст должен выглядеть красиво [[ Конфигурация ]]* [[ ППЛГ и правильно. Нерусские кавычки в тексте, дефисы вместо минуса или тире, курсив вместо прямого шрифта РСДС (PSLG и т.д. будут неодобряться. По поводу внешнего вида презентации в целом придирок не будет. И вообщеDCEL): определение, надо ещё специально постараться, чтобыпостроение РСДС множества прямых ]]что-то в TeX'е выглядело плохо.* [[ Пересечение многоугольников (PSLG overlaying) ]]
== Алгоритмы локализации ==* Презентации надо складировать в одном месте в какой-то системе контроля версий. Я предлагаю использовать для этого систему контроля версий git, хостится всё это на [http://github.com гитхабе[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]. Там стоит зарегистрироваться.* [[https://github.com/andrey-komarov/presentations РепозиторийЛокализация в ППЛГ методом полос (персистентные деревья) ]]. Возможно, оно оттуда переедет. Там отличная регистрация, во время неё вы пройдёте курс "гит за пять минут"* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Если вы до этого пользовались Алгоритм Киркпатрика ]]SVN-ом(а вы им пользовались, если сдавали C++), то проблем с гитом возникнуть не должно. Особо недовольным я могу сделать шпаргалку с командами гита.* [[ Трапецоидная карта ]]
== Триангуляция Делоне и диаграмма Вороного ==* Конструктивная критика приветствуется.[[ Триангуляция Делоне ]]* [[ Триангуляция Делоне на сфере ]]* [[ Диаграмма Вороного ]]* [[ Motorcycle graph ]]* [[ Straight skeleton ]]
== Планирование движения (Motion planning) ==* Холивары "git vs SVN"[[ Сумма Минковского (определение, "Powerpoint vs Beamer", "github vs что-то" не приветствуются. При этом, предыдущее правило имеет больший приоритет.вычисление) ]]* [[ Visibility graph и motion planning ]]
== Задачи ==* И, да, Антон не одобряет неторопливость![[ Диаметр множества точек (вращающиеся калиперы) ]]* [[ Минимальная охватывающая окружность множества точек ]]* [[ Пересечение окружностей ]]* [[ Упрощение полигональной цепи ]]* [[ Вычисление площади и объема ]]* [[ Пересечение выпуклых многоугольников ]]
