1632
правки
Изменения
м
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div><includeonly>[[КатегорияФайл: В разработкеsamplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограниченно или пусто]]</includeonly>
[[Файл== Предикат трех прямых ==Задача:dualесть конечное множество полуплоскостей, найти фигуру их пересечения или сообщить что оно пусто.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> и домножим на определитель.
Тут бы и закончить конспект, но стоит уточнить, что у пересечения полуплоскостей есть одна небольшая особенность {{<tex>A'' \left<(B'; -B);(-C; -}} оно может быть пусто, тогда как выпуклая оболочка вполне себе всегда определена, и это надо учитывать. И еще. когда мы рассматриваем верхнююC')\right> + B'' \left<(нижнюю-A'; A) огибающую, мы рассматриваем все прямые кроме вертикальных. Еще прямые близкие к вертикальным, но имеющие разный наклон ;(-C; -C')\right> + C'' \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} =</ и \) are mapped to very different points. Отсюда выходит то, почему конвекс-халл состоит из двух таких разных и одинаковых частей.tex>
Короче есть биекция <tex> D = 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> DАлгоритм:* Отсортировать все полуплоскости по углу наклона;* Запустить обход Грэхема для полуплоскостей, смотрящих вниз (D(P)с предикатом-определителем) = P </tex>;* Запустить обход Грэхема для полуплоскостей, смотрящих вверх;* Пересечь две цепочки.
* 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 15 page 253-254
rollbackEdits.php mass rollback
<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 \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> D(Y = kX Ax + By + b) C = P0 </tex> как точку с однородными координатами <tex> (kA, B, -bC) </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>. Возьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Построим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, самую правую и самую левую вертикальную прямую.# Перейдем в однородное двойственное пространство.
== Источники ==
* 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
[[Категория: Вычислительная геометрия]]
