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) ]]
== Алгоритмы локализации ==*[https://bitbucket[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ.org/andreyrybak/computational-geometry-presentations РепозиторийАлгоритм Киркпатрика ]]* [[ Трапецоидная карта ]]. Возможно, оно оттуда переедет.
== Триангуляция Делоне и диаграмма Вороного ==* Конструктивная критика приветствуется.[[ Триангуляция Делоне ]]* [[ Триангуляция Делоне на сфере ]]* [[ Диаграмма Вороного ]]* [[ Motorcycle graph ]]* [[ Straight skeleton ]]
== Планирование движения (Motion planning) ==* Холивары "git vs Mercurial vs SVN"[[ Сумма Минковского (определение, "PowerPoint vs Beamer", "bitbucket vs github vs что-то" не приветствуются. При этом, предыдущее правило имеет больший приоритет.вычисление) ]]* [[ 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 Список новых тем и дополнений]
[[Категория: Вычислительная геометрия]]