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