Викиконспекты - Вклад участника [ru]

Двойственное пространство

2016-12-11T13:58:45Z

188.162.65.11: Жолус

== Введение ==
Введем понятия двойственного, к пространству <tex>\mathbb{R}^2</tex>, пространства. Для того чтобы избежать рассмотрения отдельных случаев, работаем в однородных координатах.
Пока в конспекте есть недочеты.
=== Определение ===
{{Определение|definition=
<b>Двойственным пространством</b> называется пространство линейных функционалов на линейном пространстве <tex>\mathbb{R}^2</tex>.
}}
Любой линейный функционал <tex>f</tex> можно представить как <tex>f((x, y)) = ax - b + cy</tex>. Это значит, каждому такому функционалу будет соответствовать точка в двойственном пространстве с однородными координатами <tex>(-a, b, c)</tex>. Таким образом, мы можем определить <i>дуальное преобразование</i> (<tex>p \mapsto p^\star</tex>)
для прямой, как точку в двойственном пространстве.

{{Утверждение|statement=
Дуальное преобразование от точки <tex>p = (p_x, p_y)</tex> в исходном пространстве дает прямую <tex>p^\star := (y = p_x x - p_y)</tex> в двойственном.
|proof=
Расмотрим все прямые <tex>l</tex>, такие что <tex>p \in l</tex>. Более формально, пусть <tex>L = \{l : l = (-a, b, c), \: cp_y = ap_x - b\}</tex>.
Для каждой можно выразить <tex>b</tex>: <tex>b = ap_x - cp_y</tex>, сделаем замену <tex>\left[a := x, b := y\right]</tex> и получим, что все точки <tex>l^\star</tex>
из <tex>L</tex> удовлетворяют уравнению прямой.
}}

{{Теорема|statement=
пусть <tex>l</tex> - прямая, а <tex>p</tex> - точка, тогда:
# <tex>p \in l \Leftrightarrow l^\star \in p^\star</tex>
# <tex>p</tex> лежит над <tex>l</tex>, тогда и только тогда когда <tex>l^\star</tex> лежит над <tex>p^\star</tex>
|proof=
TODO
}}
{{Утверждение|statement=
отрезок <tex>pq</tex> переходит вот в такое множество: <tex>P = \left\{t^\star = (x, y): \left<p^\star, t^\star \right> \geqslant 0 \wedge \left<q^\star, t^\star \right> \geqslant 0 \wedge \left<l^\star, t^\star \right> \geqslant 0 \vee
\left<p^\star, t^\star \right> \leqslant 0 \wedge \left<q^\star, t^\star \right> \leqslant 0 \wedge \left<l^\star, t^\star \right> \leqslant 0\right\}</tex>,
где <tex>l</tex> - прямая на которой лежат <tex>p</tex> и <tex>q</tex>.
|proof=
TODO
}}

Двойственное пространство

2016-12-11T12:08:12Z

188.162.65.11: Новая страница: «test»

test

Вычислительная геометрия

2016-12-11T12:07:48Z

188.162.65.11: /* Основание вычислительной геометрии */

== Основание вычислительной геометрии ==
* [[ Аффинное пространство ]]
* [[ Двойственное пространство ]]
* [[ Ориентация и объем ]]
* [[ Скалярное произведение и метрика ]]
* [[ Однородные координаты ]]

== Вычисление геометрических предикатов ==
* [[ Представление чисел с плавающей точкой ]]
* [[ Предикат "левый поворот" ]]
* [[ Пересечение отрезков и поворот: определение, свойства, вычисление ]]
* [[ Adaptive precision arithmetic ]]
* [[ Интервальная арифметика ]]

== Пересечение отрезков ==
* [[ Алгоритм Бентли-Оттмана ]]
* [[ Пересечение множества отрезков ]]
* [[ Алгоритм Балабана ]]
* [[ Snap rounding ]]
* [[ Пересечение отрезков на сфере ]]

== Выпуклые оболочки ==
* [[ Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, 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-дерево ]]

== Триангуляция ==
* [[ Триангуляция полигонов (ушная + монотонная)#Ушной метод | Триангуляция многоугольника за n^2]]
* [[ Триангуляция полигонов (ушная + монотонная) | Триангуляция многоугольника заметающей прямой ]]

== ППЛГ и РСДС ==
* [[ Конфигурация ]]
* [[ ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых ]]
* [[ Пересечение многоугольников (PSLG overlaying) ]]

== Алгоритмы локализации ==
* [[ Принадлежность точки выпуклому и невыпуклому многоугольникам ]]
* [[ Локализация в ППЛГ методом полос (персистентные деревья) ]]
* [[ Алгоритм Киркпатрика детализации триангуляции | Локализация в ППЛГ. Алгоритм Киркпатрика ]]
* [[ Трапецоидная карта ]]

== Триангуляция Делоне и диаграмма Вороного ==
* [[ Триангуляция Делоне ]]
* [[ Триангуляция Делоне на сфере ]]
* [[ Диаграмма Вороного ]]
* [[ Motorcycle graph ]]
* [[ Straight skeleton ]]

== Планирование движения (Motion planning) ==
* [[ Сумма Минковского (определение, вычисление) ]]
* [[ 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 Список новых тем и дополнений]

----

* [[Список тем | Список тем (year 2010)]]
* [[Список тем (year 2012)]]
* [[Обсуждение:Вычислительная геометрия#Сдача конспектов | Сдача конспектов]]
* [[Обсуждение:Вычислительная геометрия#Презентации | Сдача презентаций]]
* [[Обсуждение:Вычислительная геометрия#Условия и чекеры | Условия и чекеры]]

[[Категория: Вычислительная геометрия]]