Изменения

[[Файл:dualsamplesHalfspaces.png|400px|thumb|right|типа это одно Пересечение существует и то жевыпукло, неограниченно или пусто]]

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

Если рассмотреть что ребро <tex> PQ </tex> принадлежит верхнему конвекс-халлу это означаетДля начала заметим, что все остальные точки лежат снизу. А если ребро <tex> PQ </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> и \) are mapped to very different points. Отсюда выходит то, почему конвекс-халл состоит из двух таких разных и одинаковых частейдомножим на определитель.

Короче есть биекция <tex> D 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> D(P(k, b)) = (Y 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} = kX - b) </tex>

<tex> D(Y = kX + b) 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} = P(k, \begin{vmatrix} A'' & A' & A \\ B'' & B' & B \\ -C'' & -C' & -b) 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> D(D(PA, B, C)) = P </tex>, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} проверка очередной точки в [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обходе Грэхема]] для нахождения выпуклой оболочки.

В общем алгоритм такой. Отдельно строим конвехАлгоритм:* Отсортировать все полуплоскости по углу наклона;* Запустить обход Грэхема для полуплоскостей, смотрящих вниз (с предикатом-халл определителем);* Запустить обход Грэхема для плоскостей полуплоскостей, смотрящих вверх ;* Пересечь две цепочки. От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, а ограниченная {{---}} когда обе цепочки не пусты и пересекаются. == Связь пересечения полуплоскостей с выпуклой оболочкой == {{Лемма |id=1|statement= Пересечение полуплоскостей может быть получено построением выпуклой оболочки в [[двойственное пространство|двойственном прострастве]] для множества точек, являющихся дуальным преобразованием исходных полуплоскостей|proof= [[Файл:DualSpaceCH.png ‎ |400px|thumb|right| Множество точек в двойственном пространстве]][[Файл:DualSpaceCH400.png |400px|thumb|right| Множество прямых в исходном пространстве]] '''Важно:''' Покажем конструктивный алгоритм для смотрящих множестве полуплоскостей, не содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, позволяющие снять данное ограничение. '''Важно:''' В картинке перепутаны <tex>P</tex> и <tex>P^\star</tex>. TODO  Рассмотрим планарный случай и предположим, что вертикальные и параллельные прямые отсутствуют (в конце приведем два способа решения данной проблемы). Пусть у нас есть множество ориентированных прямых, каждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <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>p</tex> лежит "над" <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> лежит "над" <tex>p^\star</tex>  '''Важно 2:''' * <tex>p^\star</tex> - точка в двойственном пространстве, <tex>p</tex> - линия в исходном,* <tex>l^\star</tex> - прямая в двойственном пространстве, <tex>l</tex> - точка в исходном,* Значок <tex>*</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> в базовое пространство {{---}} прямая <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>, лежащая ниже всех остальных прямых из <tex>P</tex>. Посмотрим на планарный граф множества(рис.2) прямых. Из факта выше, мы можем понять, что <tex>p</tex> внесла ребро в самый нижний фейс(именно тот, который задаёт часть пересечения полуплоскостей). Обозначим цепочку данного фейса, как <tex>\mathcal{LE}</tex>. Математически данную цепочку мы можем описать, как минимум из всех линейных функция (заданные прямыми) в <tex>P</tex>. Так же <tex>X</tex> компонента узлов этой цепочки монотонно возрастает. Вернемся к <tex>\mathcal{UH}</tex> и заметим, что при обходе цепи, координата <tex>X</tex> точек растет. Если же мы будет обходить цепочку из <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>q^\star</tex> из <tex>P^\star</tex> образуют какое-то или принадлежат какому-то ребру <tex>\mathcal{UH}</tex> <tex>\Leftrightarrow</tex> все точки из <tex>P^\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>. Возьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Построим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, самую правую и самую левую вертикальную прямую.# Перейдем в однородное двойственное пространство.