Вычислительная геометрия — различия между версиями
(→Основание вычислительной геометрии) |
|||
| Строка 1: | Строка 1: | ||
| + | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;" | ||
| + | |+ | ||
| + | |-align="center" | ||
| + | |'''НЕТ ВОЙНЕ''' | ||
| + | |-style="font-size: 16px;" | ||
| + | | | ||
| + | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. | ||
| + | |||
| + | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. | ||
| + | |||
| + | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. | ||
| + | |||
| + | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. | ||
| + | |||
| + | ''Антивоенный комитет России'' | ||
| + | |-style="font-size: 16px;" | ||
| + | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. | ||
| + | |-style="font-size: 16px;" | ||
| + | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки]. | ||
| + | |} | ||
| + | |||
== Основание вычислительной геометрии == | == Основание вычислительной геометрии == | ||
* [[ Аффинное пространство ]] | * [[ Аффинное пространство ]] | ||
Версия 08:07, 1 сентября 2022
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Содержание
- 1 Основание вычислительной геометрии
- 2 Вычисление геометрических предикатов
- 3 Пересечение отрезков
- 4 Выпуклые оболочки
- 5 Поиск
- 6 Триангуляция
- 7 ППЛГ и РСДС
- 8 Алгоритмы локализации
- 9 Триангуляция Делоне и диаграмма Вороного
- 10 Планирование движения (Motion planning)
- 11 Задачи
- 12 Программирование
- 13 Организационные вопросы
Основание вычислительной геометрии
- Аффинное пространство
- Объем
- Скалярное произведение и метрика
- Однородные координаты
- Двойственное пространство
Вычисление геометрических предикатов
- Представление чисел с плавающей точкой
- Предикат "левый поворот"
- Пересечение отрезков и поворот: определение, свойства, вычисление
- Adaptive precision arithmetic
- Интервальная арифметика
Пересечение отрезков
- Алгоритм Бентли-Оттмана
- Пересечение множества отрезков
- Алгоритм Балабана
- Snap rounding
- Пересечение отрезков на сфере
Выпуклые оболочки
- Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
- Динамическая выпуклая оболочка
- Выпуклая оболочка в n-мерном пространстве
- Пересечение полуплоскостей, связь с выпуклыми оболочками
Поиск
- К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
- Квадродерево, сжатое квадродерево
- Skip quadtree: определение, время работы, запрос точек в прямоугольнике
- Ортогональный поиск
- Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
- Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)
- Дерево интервалов (interval tree) и пересечение точки с множеством интервалов
- Пересечение прямоугольника с множеством прямоугольников (priority search tree)
- BSP-дерево
Триангуляция
ППЛГ и РСДС
- Конфигурация
- ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых
- Пересечение многоугольников (PSLG overlaying)
Алгоритмы локализации
- Принадлежность точки выпуклому и невыпуклому многоугольникам
- Локализация в ППЛГ методом полос (персистентные деревья)
- Локализация в ППЛГ. Алгоритм Киркпатрика
- Трапецоидная карта
Триангуляция Делоне и диаграмма Вороного
- Триангуляция Делоне
- Триангуляция Делоне на сфере
- Диаграмма Вороного
- Motorcycle graph
- Straight skeleton
Планирование движения (Motion planning)
Задачи
- Диаметр множества точек (вращающиеся калиперы)
- Минимальная охватывающая окружность множества точек
- Пересечение окружностей
- Упрощение полигональной цепи
- Вычисление площади и объема
- Пересечение выпуклых многоугольников
