Изменения
→Связь пересечения полуплоскостей с выпуклой оболочкой
<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>
'''Важно:''' Покажем конструктивный алгоритм для множестве полуплоскостей, не содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, позволяющие снять данное ограничение.
'''Важно2Важно:''' В картинке перепутаны <tex>P</tex> и <tex>P^\star</tex>. TODO
Рассмотрим планарный случай и предположим, что вертикальные и параллельные прямые отсутствуют (в конце приведем два способа решения данной проблемы).
#<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>lp^\star</tex> в базовое пространство {{---}} прямая <tex>lp</tex>, которая по ''первому свойству'' содержит точку <tex>pl</tex>(в базовом пространстве прямая <tex>p^\star</tex> перешла в точку <tex>p</tex>).
*Так как прямая <tex>l^\star</tex> лежит выше всех точек, то теперь каждая прямая из <tex>P</tex> лежит выше точки <tex>l</tex> (по свойству 2).
}}
Что же делать с вертикальными линиями?
# Очевидный факт: в конечной выпуклой оболочке будет не более двух вертикальных прямых (левая и правая). Мы можем найти их за <tex>NlogN</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
[[Категория: Вычислительная геометрия]]
