222
правки
Изменения
м
Нет описания правки
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)
Пусть у нас прямые заданы уравнениями вида <tex> Ax + By + C = 0 </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 \\
</tex>.
Докажем это. Для проверки предиката нам надо определить знак выражения <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'
-C'
\end{pmatrix}
</tex>. Решением будет <tex>
\begin{pmatrix}
x_0\\
\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'' \end{vmatrix} </tex>
Таким образом если представить прямую <tex> Ax + By + C = 0 </tex> как точку с координатами <tex> (A, B, C) </tex>, где <tex> C </tex> {{---}} однородная координата, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обход Грэхема]] для нахождения выпуклой оболочки.
