Изменения

Перейти к: навигация, поиск
м
Нет описания правки
[[Файл:samplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограничено или пусто]]
[[Файл:dualityhalfSpaces.png|400px|thumb|right|Пример отображенияПредикат]]
Задача: есть конечное множество полуплоскотей, найти фигуру их пересечения или сообщить что оно пусто.
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)
 
Пусть у нас прямые заданы уравнениями вида <tex> Ax + By + C = 0 </tex>. Тогда предикат проверки того, что прямая <tex> A''x + B''y + C'' = 0 </tex> лежит над пересечением прямых <tex> Ax + By + C = 0 </tex> и <tex> A'x + B'y + C' = 0 </tex> будет равен <math>\begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix}</math>
 
 
 
 
 
 
 
 
Рассмотрим отображение <tex> D </tex> между точками и прямыми, такое что:
222
правки

Навигация