222
правки
Изменения
м
Нет описания правки
Если рассмотреть что ребро <tex> PQ </tex> принадлежит верхнему конвекс-халлу это означает, что все остальные точки лежат снизу. А если ребро <tex> PQ </tex> принаджлежит нижней огибающей, то все остальные прямые лежат сверху. Короче да, одно и то же...
Если в конвекс-халле мы идем слева направо по увеличению икса, то тут то же самое будет, если мы пойдем справа налево по увеличению угла наклона.
Полностью считать пересечние можно по отдельности (верхняя + нижняя огибающая), а можно и сразу все, как полный конвекс-халл.
Тут бы и закончить конспект, но стоит уточнить, что у пересечения полуплоскостей есть одна небольшая особенность {{---}} оно может быть пусто, тогда как выпуклая оболочка вполне себе всегда определена, и это надо учитывать. И еще. когда мы рассматриваем верхнюю(нижнюю) огибающую, мы рассматриваем все прямые кроме вертикальных. Еще прямые близкие к вертикальным, но имеющие разный наклон (/ и \) are mapped to very different points. Отсюда выходит то, почему конвекс-халл состоит из двух таких разных и одинаковых частей.
