222
правки
Изменения
Нет описания правки
[[Файл:samplesHalfspaces.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>
\begin{vmatrix}
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{vmatrix}
}
</tex>. Подставим его это решение в <tex> A''x_0 + B''y_0 + C'' </tex> и домножим на определитель.
<tex> A'' (B'; -B)(-C; -C') + B'' (-A'; A)(-C; -C') + C \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} = 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} = \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>, где <tex> C </tex> {{---}} однородная координата, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} проверка очередной точки в [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обходе Грэхема]] для нахождения выпуклой оболочки.
* Отсортировать все полуплоскости по углу наклона;
* Запустить обход Грэхема для полуплоскостей, смотрящих вниз (с предикатом-определителем);
* То же самое Запустить обход Грэхема для полуплоскостей, смотрящих вверх;
* Пересечь две цепочки.
== Источники ==
* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf
[[Категория: Вычислительная геометрия]]
