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