Изменения

[[Файл:samplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограничено неограниченно или пусто]][[Файл:halfSpaces.png|400px|thumb|right|Нужна ли нам верхняя полуплоскость?]]

== Предикат трех прямых ==Задача: есть конечное множество полуплоскотейполуплоскостей, найти фигуру их пересечения или сообщить что оно пусто.

Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть полуплоскость выпукла)

Пусть у нас прямые полуплоскости заданы уравнениями вида прямых и ориентацией, с какой стороны от прямой лежит полуплоскость. Сначала рассмотрим все полуплоскости, которые "смотрят", то есть ориентированны, вниз. Аналогично можно рассмотреть все полуплоскости, которые ориентированны вверх. {{Лемма|statement=[[Файл:halfSpaces.png|400px|thumb|right|Нужна ли полуплоскость <tex> Ax + By + C = 0 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>

|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}

</tex>.  Решением будет <tex>

</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 & B 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#Алгоритм Грэхема|обходе Грэхема]] для нахождения выпуклой оболочки. Алгоритм:* Отсортировать все полуплоскости по углу наклона;* Запустить обход Грэхема для полуплоскостей, смотрящих вниз (с предикатом-определителем);* Запустить обход Грэхема для полуплоскостей, смотрящих вверх;* Пересечь две цепочки. От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, а ограниченная {{---}} когда обе цепочки не пусты и пересекаются. == Связь пересечения полуплоскостей с выпуклой оболочкой == {{Лемма |id=1|statement= Пересечение полуплоскостей может быть получено построением выпуклой оболочки в [[двойственное пространство|двойственном прострастве]] для множества точек, являющихся дуальным преобразованием исходных полуплоскостей|proof= [[Файл:DualSpaceCH.png ‎ |400px|thumb|right| Множество точек в двойственном пространстве]][[Файл:DualSpaceCH400.png |400px|thumb|right| Множество прямых в исходном пространстве]]

Таким образом если представить прямую <tex> Ax + By + C = 0 </tex> как точку с координатами <tex> (A'''Важно:''' Покажем конструктивный алгоритм для множестве полуплоскостей, Bне содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, C) </tex>, где <tex> C </tex> {{---}} однородная координата, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} обход Грэхемапозволяющие снять данное ограничение.

Рассмотрим Пусть у нас есть множество ориентированных прямых, каждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <tex> P(p_x, p_y) \Rightarrow P^\star (p_x x - p_y)</tex>. Далее воспользуемся основными свойствами дуальной трансформации (см. доказательтсво в конспекте о [[двойственное пространство|двойственном прострастве]]):#<tex>p</tex> <tex>\in</tex> <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> <tex>\in</tex> <tex>p^\star</tex>, где <tex>p</tex> - точка в исходном пространстве, <tex>l</tex> - прямая в исходном пространстве, <tex>l^\star</tex>, <tex>p^\star</tex> - их дуальное отображение .#<tex> D p</tex> лежит "над" <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> лежит "над" <tex>p^\star</tex> между точками и прямыми, такое что:

'''Важно 2:''' * <tex> Dp^\star</tex> - точка в двойственном пространстве, <tex>p</tex> - линия в исходном,* <tex>l^\star</tex> - прямая в двойственном пространстве, <tex>l</tex> - точка в исходном,* Значок <tex>*</tex> означает, что элемент из двойственного пространства.Рассмотрим множество точек(<tex>P^\star</tex>) в двойственном пространстве и рассмотрим верхнюю часть выпуклой оболочки, построенной на этих точках. Обозначим её за <tex>\mathcal{UH}</tex>(Y = kX + bUpper hull) = P. Далее мы будем работать только с прямыми(kв исходном пространстве), у которых вектор нормали направлен вниз, т.е они образовывают верхнюю цепочку.По свойству выпуклой оболочки, -b) любое ребро из цепи <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> в базовое пространство {{---}} прямая <tex>p</tex>, поэтому их мы рассмотрим которая по ''первому свойству'' содержит точку <tex>l</tex>(в базовом пространстве прямая <tex>p^\star</tex> перешла в конце отдельноточку <tex>p</tex>).*Так как прямая <tex>l^\star</tex> лежит выше всех точек, то теперь каждая прямая из <tex>P</tex> лежит выше точки <tex>l</tex> (по свойству 2).

[[ФайлИтого:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]Будем обозначать, что у нас есть точка <tex>l</tex> на прямой <tex> D(p) = p^* </tex>, лежащая ниже всех остальных прямых из <tex> D(l) = l^* P</tex> .

Факт дуализма:* Точка <tex> p </tex> лежит под/Посмотрим на/над прямой <tex> l </tex> тогда и только тогда, когда <tex> Dпланарный граф множества(lрис.2) прямых. Из факта выше, мы можем понять, что </tex> лежит под/на/над прямой <tex> D(p) </tex>;Тогда точка <tex> p \in P = \cup p_i </tex> принадлежит <tex> UHвнесла ребро в самый нижний фейс(Pименно тот, который задаёт часть пересечения полуплоскостей) </tex> тогда и только тогда. Обозначим цепочку данного фейса, когда существует такая не вертикальная прямая как <tex> l \mathcal{LE}</tex>. Математически данную цепочку мы можем описать, что как минимум из всех линейных функция (заданные прямыми) в <tex> \forall i : p_i P</tex> лежит под . Так же <tex> l X</tex>компонента узлов этой цепочки монотонно возрастает.

Перефразируем для dual-пространства:* Существует точка Вернемся к <tex> l^* \mathcal{UH}</tex> и заметим, что при обходе цепи, координата <tex>X</tex> на прямой точек растет. Если же мы будет обходить цепочку из <tex>P</tex>, образующую пересечение полуплоскостей, мы заметим, что наклон прямых уменьшается. Учитывая этот факт, и то что наклон линии из <tex> p^* \in P^* : l^* mathcal{LE}</tex> совпадет с <tex>X</tex> координатой точки (вспоминаем отображение и применяем производную), можно сделать вывод, что обход слева направо точек из цепи <tex>\mathcal{UH}</tex> лежит под любой прямой , совпадает с обходом точек из <tex> P^*\mathcal{LE}</tex>справа налево.

Рассмортим верхний конвекс-халл точек <tex> P </tex> (англОбе линии монотоны, одна возрастает, другая убывает. ''upper convex hull'') и нижнюю огибающей прямых <tex> P^* </tex> (англ. ''lower envelope''). Точки в <tex> P </tex> появляются Количество точек в массиве одинаковое, при это каждая точка из <tex> \mathcal{UH(P) </tex> по увелечению х-координаты. Прямые в <tex> P^* }</tex> появляются внесла вклад в <tex> \mathcal{LE(P^*) }</tex> по уменьшению угла наклона. Так как угол наклона соответствует х-координате, то список точек <tex> UH(P) </tex> слева-направо соответствует списку справа-налево ребер <tex> LE(P^*) </tex>. Таким образом верхний конвекс-халл соответствует нижней огибающей прямых. Аналогично для нижнего СН и верхней огибающей.

Более формально: Напоследок, cоседние точки <tex> p, ^\star</tex> и <tex>q ^\in star</tex> из <tex>P : pq ^\star</tex> {{-образуют какое-то или принадлежат какому-то ребру <tex>\mathcal{UH}} ребро верхнего конвекс-халла тогда и только тогда, когда </tex> <tex>\Leftrightarrow</tex> все остальные точки из <tex> P ^\star</tex> лежат "ниже прямой" линии, проходящей через это ребропостроенной на точках <tex>p^\star</tex> и <tex>q^\star</tex>. В dual-исходном пространстве получаем, что это означает: все прямые из пространства <tex> \forall r^*, r \in P \setminus \{</tex> за исключением прямых <tex>p, </tex> и <tex>q\} </tex> лежат над точкой пересечения пересечением <tex> p^* </tex> и <tex> q^* </tex>. Это как раз достаточное условие, что пересечение <tex> p^* </tex> и <tex>q</tex> <tex>\cap q^* in</tex> {{---}} вершина <tex> \mathcal{LE(P^*) }</tex>.

Таким образом получаем алгоритм:* Считаем <tex> H_+ </tex>мы построили верхнее пересечение полуплоскостей. (полуплоскостиАналогичным образом строится нижнее, смотрящие вверх)затем мы пересекаем полученные две цепочки.}}Что же делать с вертикальными линиями?* Считаем # Найдем все вертикальным прямые за <tex> H_- </tex>. O(полуплоскости, смотрящие внизN)* Считаем <tex> H_> </tex>. (вертикальные полуплоскостиВозьмем самую правую, у которой нормаль смотрит вправо, и самую левую, смотрящие направо)* Считаем <tex> H_< </tex>у которых нормаль смотрит влево. (вертикальные полуплоскостиПостроим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, смотрящие налево)* Пускаем заметающую самую правую и самую левую вертикальную прямую и получаем пересечение <tex> H_+ \cap H_- \cap H_> \cap H_< </tex>.Стоит уточнить, что каждое из этих множеств может быть пусто. Тогда мы не рассматриваем с ним объединение. Однако # Перейдем в результате мы можем получить пустое множество. Это главное отличние пересечения полуплоскостей и конвекс-халлаоднородное двойственное пространство.