Материал из Викиконспекты
Пересечение существует и выпукло, неограниченно или пусто
Задача: есть конечное множество полуплоскостей, найти фигуру их пересечения или сообщить что оно пусто.
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство — Пересечение выпуклых фигур выпукло, а полуплоскость выпукла)
Пусть полуплоскости заданы уравнениями прямых и ориентацией, с какой стороны от прямой лежит полуплоскость.
Сначала рассмотрим все полуплоскости, которые "смотрят", то есть ориентированны, вниз. Аналогично можно рассмотреть все полуплоскости, которые ориентированны вверх.
Лемма: |
Нужна ли полуплоскость [math] l'' [/math]?
Предикат проверки (см. рисунок) того, что прямая [math] l'' : A''x + B''y + C'' = 0 [/math] лежит над пересечением прямых [math] l : Ax + By + C = 0 [/math] и [math] l' : A'x + B'y + C' = 0 [/math] равен знаку определителя [math]
\begin{vmatrix}
A & B & C \\
A' & B' & C' \\
A'' & B'' & C''
\end{vmatrix}
[/math]. |
Доказательство: |
[math]\triangleright[/math] |
Для проверки предиката нужно определить знак выражения [math] A''x_0 + B''y_0 + C'' [/math], где [math] (x_0, y_0) [/math] — точка пересечения прямых [math] l' [/math] и [math] l [/math]. Эта точка находится из уравнения [math] \begin{pmatrix}
A & B\\
A' & B'
\end{pmatrix}
\begin{pmatrix}
x_0\\
y_0
\end{pmatrix} =
\begin{pmatrix}
-C\\
-C'
\end{pmatrix}
[/math]. Решением будет [math]
\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}
}
[/math]. Подставим это решение в [math] A''x_0 + B''y_0 + C'' [/math] и домножим на определитель.
[math]
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}
[/math] |
[math]\triangleleft[/math] |
Таким образом, если представить прямую [math] Ax + By + C = 0 [/math] как точку с однородными координатами [math] (A, B, C) [/math], то этот предикат — всего лишь поворот, а проверка предиката — проверка очередной точки в обходе Грэхема для нахождения выпуклой оболочки.
Алгоритм:
- Отсортировать все полуплоскости по углу наклона;
- Запустить обход Грэхема для полуплоскостей, смотрящих вниз (с предикатом-определителем);
- Запустить обход Грэхема для полуплоскостей, смотрящих вверх;
- Пересечь две цепочки.
От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, а ограниченная — когда обе цепочки не пусты и пересекаются.
Связь с двойственным пространством
Источники