Редактирование: Вычислительная геометрия

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
== Основание вычислительной геометрии ==
+
* [[Представление чисел с плавающей точкой]]
* [[ Аффинное пространство ]]
+
* [[Предикат "левый поворот"]]
* [[ Объем ]]
+
* [[Интервальная арифметика]]
* [[ Скалярное произведение и метрика ]]
+
* [[Adaptive precision arithmetic]]
* [[ Однородные координаты ]]
+
* [[Алгоритм Бентли-Оттмана]]
* [[ Двойственное пространство ]]
+
* [[Конфигурация]]
 +
* [[Трапецоидная карта]]
 +
* [[Алгоритм Киркпатрика детализации триангуляции]]
 +
* [[Пересечение окружностей]]
 +
* [[Упрощение полигональной цепи]]
 +
* [[Ортогональный поиск]]
 +
* [[Триангуляция полигонов (ушная + монотонная)]]
  
== Вычисление геометрических предикатов ==
+
----
* [[ Представление чисел с плавающей точкой ]]
 
* [[ Предикат "левый поворот" ]]
 
* [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]]
 
* [[ Adaptive precision arithmetic ]]
 
* [[ Интервальная арифметика ]]
 
  
== Пересечение отрезков ==
+
* [[Список тем]]
* [[ Алгоритм Бентли-Оттмана ]]
+
* [[Список тем (year 2012)]]
* [[ Пересечение множества отрезков ]]
+
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]
* [[ Алгоритм Балабана ]]
+
* [[Обсуждение:Вычислительная геометрия#Презентации | Сдача презентаций]]
* [[ Snap rounding ]]
+
* [[Обсуждение:Вычислительная геометрия#Условия и чекеры | Условия и чекеры]]
* [[ Пересечение отрезков на сфере ]]
 
  
== Выпуклые оболочки ==
+
----
* [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]
 
* [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка ]]
 
* [[ Выпуклая оболочка в n-мерном пространстве ]]
 
* [[ Пересечение полуплоскостей, связь с выпуклыми оболочками ]]
 
  
== Поиск ==
+
* [[CMake_Tutorial|Туториал по cmake]]
* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]
+
* [[Тестирование с использованием Google Test]]
* [[ Квадродеревья | Квадродерево, сжатое квадродерево ]]
+
== Базовые алгоритмы и структуры данных ==
 +
* [[Квадродеревья | Квадродерево, сжатое квадродерево]]
 
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
 
* [[ Skip quadtree: определение, время работы | Skip quadtree: определение, время работы, запрос точек в прямоугольнике ]]
* [[ Ортогональный поиск ]]
+
* [[ К-d деревья и перечисление точек в произвольном прямоугольнике (статика) | К-d деревья и перечисление точек в произвольном прямоугольнике (статика) ]]
* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
+
* [[ Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) | Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) ]]
* [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
+
* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов | Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
* [[ Дерево интервалов (interval tree) и пересечение точки с множеством интервалов ]]
 
 
* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
 
* [[ Пересечение прямоугольника с множеством прямоугольников (PST) | Пересечение прямоугольника с множеством прямоугольников (priority search tree) ]]
* [[ BSP-дерево ]]
 
  
== Триангуляция ==
+
== Аффинное пространство ==
 +
* [[ Пересечение отрезков и поворот: определение, свойства, вычисление | Пересечение отрезков и поворот: определение, свойства, вычисление ]]
 +
* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам | Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
 +
* [[ Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) | Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree) ]]
 +
* [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull | Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull ]]
 +
* [[ Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) | Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление) ]]
 +
* [[ Выпуклая оболочка в n-мерном пространстве | Выпуклая оболочка в n-мерном пространстве ]]
 
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
 
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
 
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
 
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]
 
+
* [[ Пересечение полуплоскостей, связь с выпуклыми оболочками | Пересечение полуплоскостей, связь с выпуклыми оболочками ]]
== ППЛГ и РСДС ==
+
* [[ Пересечение множества отрезков | Пересечение множества отрезков ]]
* [[ Конфигурация ]]
+
* [[ Snap rounding | Snap rounding ]]
* [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]]
+
* [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых | ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]]
* [[ Пересечение многоугольников (PSLG overlaying) ]]
+
* [[ Пересечение многоугольников (PSLG overlaying) | Пересечение многоугольников (PSLG overlaying) ]]
 
+
* [[ Локализация в ППЛГ методом полос (персистентные деревья) | Локализация в ППЛГ методом полос (персистентные деревья) ]]
== Алгоритмы локализации ==
 
* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
 
* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]
 
 
* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
 
* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
* [[ Трапецоидная карта ]]
+
* [[ Трапецоидная карта | Трапецоидная карта ]]
 
+
* [[ Пересечение отрезков на сфере | Пересечение отрезков на сфере ]]
== Триангуляция Делоне и диаграмма Вороного ==
+
* [[BSP-дерево]]
* [[ Триангуляция Делоне ]]
 
* [[ Триангуляция Делоне на сфере ]]
 
* [[ Диаграмма Вороного ]]
 
* [[ Motorcycle graph ]]
 
* [[ Straight skeleton ]]
 
 
 
== Планирование движения (Motion planning) ==
 
* [[ Сумма Минковского (определение, вычисление) ]]
 
* [[ Visibility graph и motion planning ]]
 
  
== Задачи ==
+
== Скалярное произведение и мера ==
* [[ Диаметр множества точек (вращающиеся калиперы) ]]
+
* [[ Диаметр множества точек (вращающиеся калиперы) | Диаметр множества точек (вращающиеся калиперы) ]]
* [[ Минимальная охватывающая окружность множества точек ]]
+
* [[ Сумма Минковского (определение, вычисление) | Сумма Минковского (определение, вычисление) ]]
* [[ Пересечение окружностей ]]
+
* [[ Минимальная охватывающая окружность множества точек | Минимальная охватывающая окружность множества точек ]]
* [[ Упрощение полигональной цепи ]]
+
* [[ Visibility graph и motion planning | Visibility graph и motion planning ]]
* [[ Вычисление площади и объема ]]
+
* [[ Триангуляция Делоне | Триангуляция Делоне ]]
* [[ Пересечение выпуклых многоугольников ]]
+
* [[ Диаграмма Вороного | Диаграмма Вороного ]]
 +
* [[Motorcycle graph]]
 +
* [[Straight skeleton]]
  
== Программирование ==
+
== Добавьте в нужное место ==
* [[ CMake_Tutorial|Туториал по cmake ]]
+
* [[Алгоритм Балабана]]
* [[ Тестирование с использованием Google Test ]]
 
 
 
== Организационные вопросы ==
 
* [[Участник:Shersh/Тикеты к вычислительной геометрии (термы 4 и 5) | Правки к конспектам (year 2013)]]
 
* [https://docs.google.com/spreadsheet/ccc?key=0AiudLnRYFaaXdFJZdXBaSHJQT29wd0EwekxSZ0JTZkE&usp=drive_web#gid=4 Список новых тем и дополнений]
 
 
 
----
 
 
 
* [[Список тем | Список тем (year 2010)]]
 
* [[Список тем (year 2012)]]
 
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]
 
* [[Обсуждение:Вычислительная геометрия#Презентации | Сдача презентаций]]
 
* [[Обсуждение:Вычислительная геометрия#Условия и чекеры | Условия и чекеры]]
 
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)