222
правки
Изменения
м
Нет описания правки
[[Файл:samplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограничено или пусто]]
[[Файл:halfSpaces.png|400px|thumb|right|ПредикатНужна ли нам верхняя полуплоскость?]]
Задача: есть конечное множество полуплоскотей, найти фигуру их пересечения или сообщить что оно пусто.
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)
Пусть у нас прямые заданы уравнениями вида <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> будет равен <mathtex>\begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix}</mathtex>.
Давайте это покажем. Нам надо определить знак <tex> Ax_0 + By_0 + C </tex>, где <tex> (x_0, y_0) </tex> {{---}} точка пересечения прямых <tex> l' </tex> и <tex> l </tex>
