1632
правки
Изменения
м
Давайте это покажемСначала рассмотрим все полуплоскости, которые "смотрят", то есть ориентированны, вниз. Нам надо определить знак <tex> Ax_0 + By_0 + C </tex>Аналогично можно рассмотреть все полуплоскости, где <tex> (x_0, y_0) </tex> {{---}} точка пересечения прямых <tex> l' </tex> и <tex> l </tex>которые ориентированны вверх.
Рассмотрим отображение <tex> D </tex> между точками От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, а ограниченная {{---}} когда обе цепочки не пусты и прямыми, такое что:пересекаются.
<tex> D(P(k, b)) = (Y = kX - b) </tex>Связь пересечения полуплоскостей с выпуклой оболочкой ==
<tex> D(Y {{Лемма |id= kX + b) 1|statement= P(kПересечение полуплоскостей может быть получено построением выпуклой оболочки в [[двойственное пространство|двойственном прострастве]] для множества точек, -b) </tex>являющихся дуальным преобразованием исходных полуплоскостей|proof= [[Файл:DualSpaceCH.png |400px|thumb|right| Множество точек в двойственном пространстве]][[Файл:DualSpaceCH400.png |400px|thumb|right| Множество прямых в исходном пространстве]]
Это отображение '''Важно:''' Покажем конструктивный алгоритм для множестве полуплоскостей, не рассматривает вертикальные прямыесодержащих вертикальный полуплоскости. После леммы приведены два рассуждения, поэтому их мы рассмотрим в конце отдельнопозволяющие снять данное ограничение.
[[Файл'''Важно:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]Будем обозначать, что ''' В картинке перепутаны <tex> D(p) = p^* P</tex>, и <tex> D(l) = lP^* \star</tex> . TODO
Факт дуализма:
* Точка <tex> p </tex> лежит под/на/над прямой <tex> l </tex> тогда и только тогда, когда <tex> D(l) </tex> лежит под/на/над прямой <tex> D(p) </tex>;
Тогда точка <tex> p \in P = \cup p_i </tex> принадлежит <tex> UH(P) </tex> тогда и только тогда, когда существует такая не вертикальная прямая <tex> l </tex>, что <tex> \forall i : p_i </tex> лежит под <tex> l </tex>.
Перефразируем для dual-пространства:* Существует точка <tex> l^* </tex> на прямой <tex> p^* \in P^* : l^* </tex> лежит под любой прямой из <tex> P^*</tex>Рассмотрим планарный случай и предположим, что вертикальные и параллельные прямые отсутствуют (в конце приведем два способа решения данной проблемы).
Рассмортим верхний конвекс-халл точек Пусть у нас есть множество ориентированных прямых, каждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <tex> P (p_x, p_y) \Rightarrow P^\star (p_x x - p_y)</tex> . Далее воспользуемся основными свойствами дуальной трансформации (англсм. ''upper convex hull''доказательтсво в конспекте о [[двойственное пространство|двойственном прострастве]]) и нижнюю огибающей прямых :#<tex>p</tex> <tex>\in</tex> <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> <tex>\in</tex> <tex> Pp^* \star</tex> (англ. ''lower envelope''). Точки в , где <tex> P p</tex> появляются - точка в исходном пространстве, <tex> UH(P) l</tex> по увелечению х-координаты. Прямые прямая в исходном пространстве, <tex> Pl^* \star</tex> появляются в , <tex> LE(Pp^*) \star</tex> по уменьшению угла наклона- их дуальное отображение. Так как угол наклона соответствует х-координате, то список точек #<tex>p</tex> лежит "над" <tex>l</tex> <tex>\Leftrightarrow</tex> <tex> UH(P) l^\star</tex> слева-направо соответствует списку справа-налево ребер лежит "над" <tex> LE(Pp^*) \star</tex>. Таким образом верхний конвекс-халл соответствует нижней огибающей прямых. Аналогично для нижнего СН и верхней огибающей.
Более формально: точки <tex> p, q \in P : pq </tex> {{---}} ребро верхнего конвекс-халла тогда и только тогда, когда все остальные точки из <tex> P </tex> лежат ниже прямой, проходящей через это ребро. В dual-пространстве получаем, что <tex> \forall r^*, r \in P \setminus \{p, q\} </tex> лежат над точкой пересечения <tex> p^* </tex> и <tex> q^* </tex>. Это как раз условие, что <tex> p^* \cap q^* </tex> {{---}} вершина <tex> LE(P^*) </tex>.
Таким образом получаем алгоритм'''Важно 2:''' * <tex>p^\star</tex> - точка в двойственном пространстве, <tex>p</tex> - линия в исходном,* <tex>l^\star</tex> - прямая в двойственном пространстве, <tex>l</tex> - точка в исходном,* Считаем Значок <tex> H_+ *</tex>означает, что элемент из двойственного пространства. Рассмотрим множество точек(полуплоскости<tex>P^\star</tex>) в двойственном пространстве и рассмотрим верхнюю часть выпуклой оболочки, смотрящие вверхпостроенной на этих точках. Обозначим её за <tex>\mathcal{UH}</tex>(Upper hull). Далее мы будем работать только с прямыми(в исходном пространстве), у которых вектор нормали направлен вниз, т.е они образовывают верхнюю цепочку.По свойству выпуклой оболочки, любое ребро из цепи <tex>\mathcal{UH}</tex> содержит "ниже" себя все точки множества <tex>P^\star</tex>, а так же эта цепь соединяет самую правую точку с самой левой. Рассмотрим какую-то точку <tex>p^\star \in P^\star</tex> и заметим, что она будет принадлежать цепи <tex>\mathcal{UH}</tex> <tex>\Leftrightarrow</tex> <tex>\exists</tex> прямая <tex>l^\star </tex> : <tex>p^\star \in l^\star</tex> и все точки из <tex>P^\star</tex> лежат ниже <tex>l^\star</tex> (сейчаc мы жили в двойственном пространстве). В обычном пространстве данный факт эквивалентен следующему: * Считаем Дуальное отображение точки <tex>p^\star</tex> H_в базовое пространство {{-- -}} прямая <tex>p</tex>, которая по ''первому свойству'' содержит точку <tex>l</tex>(в базовом пространстве прямая <tex>p^\star</tex> перешла в точку <tex>p</tex>). *Так как прямая <tex>l^\star</tex> лежит выше всех точек, то теперь каждая прямая из <tex>P</tex> лежит выше точки <tex>l</tex> (полуплоскости, смотрящие внизпо свойству 2).* Считаем Итого: у нас есть точка <tex>l</tex> на прямой <tex>p</tex> H_, лежащая ниже всех остальных прямых из <tex> P</tex>. Посмотрим на планарный граф множества(рис.2) прямых. Из факта выше, мы можем понять, что <tex>p</tex> внесла ребро в самый нижний фейс(вертикальные полуплоскостиименно тот, который задаёт часть пересечения полуплоскостей). Обозначим цепочку данного фейса, как <tex>\mathcal{LE}</tex>. Математически данную цепочку мы можем описать, смотрящие направокак минимум из всех линейных функция (заданные прямыми)в <tex>P</tex>. Так же <tex>X</tex> компонента узлов этой цепочки монотонно возрастает. * Считаем Вернемся к <tex>\mathcal{UH}</tex> и заметим, что при обходе цепи, координата <tex>X</tex> H_точек растет. Если же мы будет обходить цепочку из < tex>P</tex>, образующую пересечение полуплоскостей, мы заметим, что наклон прямых уменьшается. Учитывая этот факт, и то что наклон линии из <tex>\mathcal{LE}</tex> совпадет с <tex>X</tex> координатой точки (вертикальные полуплоскостивспоминаем отображение и применяем производную), можно сделать вывод, смотрящие что обход слева направо точек из цепи <tex>\mathcal{UH}</tex>, совпадает с обходом точек из <tex>\mathcal{LE}</tex> справа налево. (Обе линии монотоны, одна возрастает, другая убывает. Количество точек в массиве одинаковое, при это каждая точка из <tex>\mathcal{UH}</tex> внесла вклад в <tex>\mathcal{LE}</tex>)* Пускаем заметающую вертикальную прямую Напоследок, cоседние точки <tex>p^\star</tex> и получаем пересечение <tex> H_+ q^\star</tex> из <tex>P^\cap H_star</tex> образуют какое-то или принадлежат какому- то ребру <tex>\mathcal{UH}</tex> <tex>\cap H_Leftrightarrow</tex> все точки из <tex> P^\cap H_star</tex> лежат "ниже" линии, построенной на точках <tex>p^\star</tex> и <tex>q^\star</tex>. В исходном пространстве это означает: все прямые из пространства <tex>P</tex> за исключением прямых <tex>p</tex> и < tex>q</tex>Стоит уточнитьлежат над пересечением <tex>p</tex> и <tex>q</tex>. Это достаточное условие, что каждое из этих множеств может быть пустопересечение <tex>p</tex> и <tex>q</tex> <tex>\in</tex> <tex>\mathcal{LE}</tex>. Таким образом мы построили верхнее пересечение полуплоскостей. Тогда Аналогичным образом строится нижнее, затем мы не рассматриваем пересекаем полученные две цепочки.}}Что же делать с ним объединениевертикальными линиями?# Найдем все вертикальным прямые за <tex>O(N)</tex>. Однако в результате мы можем получить пустое множествоВозьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Это главное отличние пересечения полуплоскостей Построим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, самую правую и конвекс-халласамую левую вертикальную прямую.# Перейдем в однородное двойственное пространство.
* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf
rollbackEdits.php mass rollback
[[Файл:samplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограничено неограниченно или пусто]][[Файл:halfSpaces.png|400px|thumb|right|Нужна ли нам верхняя полуплоскость?]]
== Предикат трех прямых ==Задача: есть конечное множество полуплоскотейполуплоскостей, найти фигуру их пересечения или сообщить что оно пусто.
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть полуплоскость выпукла)
Пусть у нас прямые полуплоскости заданы уравнениями вида <tex> Ax + By + C = 0 </tex>. Тогда предикат проверки тогопрямых и ориентацией, что прямая <tex> l'' : A''x + B''y + C'' = 0 </tex> с какой стороны от прямой лежит над пересечением прямых <tex> l : Ax + By + C = 0 </tex> и <tex> l' : A'x + B'y + C' = 0 </tex> будет равен <tex>\begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix}</tex>полуплоскость.
{{Лемма
|statement=
[[Файл:halfSpaces.png|400px|thumb|right|Нужна ли полуплоскость <tex> l'' </tex>?]]
Предикат проверки (см. рисунок) того, что прямая <tex> l'' : A''x + B''y + C'' = 0 </tex> лежит над пересечением прямых <tex> l : Ax + By + C = 0 </tex> и <tex> l' : A'x + B'y + C' = 0 </tex> равен знаку определителя <tex>
\begin{vmatrix}
A & B & C \\
A' & B' & C' \\
A'' & B'' & C''
\end{vmatrix}
</tex>.
|proof=
Для проверки предиката нужно определить знак выражения <tex> A''x_0 + B''y_0 + C'' </tex>, где <tex> (x_0, y_0) </tex> {{---}} точка пересечения прямых <tex> l' </tex> и <tex> l </tex>. Эта точка находится из уравнения <tex> \begin{pmatrix}
A & B\\
A' & B'
\end{pmatrix}
\begin{pmatrix}
x_0\\
y_0
\end{pmatrix} =
\begin{pmatrix}
-C\\
-C'
\end{pmatrix}
</tex>. Решением будет <tex>
\begin{pmatrix}
x_0\\
y_0
\end{pmatrix} =
\frac{
\begin{pmatrix}
B' & -B\\
-A' & A
\end{pmatrix}
\begin{pmatrix}
-C\\
-C'
\end{pmatrix}}
{
\begin{vmatrix}
A & B\\
A' & B'
\end{vmatrix}
}
</tex>. Подставим это решение в <tex> A''x_0 + B''y_0 + C'' </tex> и домножим на определитель.
<tex>
A'' \left<(B'; -B);(-C; -C')\right> + B'' \left<(-A'; A);(-C; -C')\right> + C'' \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} =
</tex>
<tex>
= A'' \begin{vmatrix} B' & B \\ -C' & -C \end{vmatrix} - B'' \begin{vmatrix} A' & A \\ -C' & -C \end{vmatrix} + C'' \begin{vmatrix} A & A' \\ B & B' \end{vmatrix} =
</tex>
<tex>
= A'' \begin{vmatrix} B' & B \\ -C' & -C \end{vmatrix} - B'' \begin{vmatrix} A' & A \\ -C' & -C \end{vmatrix} - C'' \begin{vmatrix} A' & A \\ B' & B \end{vmatrix}
= \begin{vmatrix} A'' & A' & A \\ B'' & B' & B \\ -C'' & -C' & -C \end{vmatrix} =
</tex>
<tex>
= \begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix}
</tex>
}}
Таким образом, если представить прямую <tex> Ax + By + C = 0 </tex> как точку с однородными координатами <tex> (A, B, C) </tex>, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} проверка очередной точки в [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обходе Грэхема]] для нахождения выпуклой оболочки.
Алгоритм:
* Отсортировать все полуплоскости по углу наклона;
* Запустить обход Грэхема для полуплоскостей, смотрящих вниз (с предикатом-определителем);
* Запустить обход Грэхема для полуплоскостей, смотрящих вверх;
* Пересечь две цепочки.
== Источники ==
* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf
* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 11 page 253-254
[[Категория: Вычислительная геометрия]]
