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