Пересечение полуплоскостей

Материал из Algocode wiki
Перейти к: навигация, поиск

Заметим, что если у нас есть некоторая прямая, задаваемая уравнением $ax + by + c = 0$, то множества точек, удовлетворяющие неравенствам $ax + by + c \leq 0$ и $ax + by + c \geq 0$ это полуплоскости, на которые эта прямая разделяет плоскость. Будем задавать поплоскости уравнениями $ax + by + c \leq 0$, потому что для полуплоскостей второго вида можно просто рассмотреть прямую с коэфициентами $-a, -b, -c$. Пусть у нас задано много полуплоскостей. Мы хотим найти их пересечение, то есть как-то описать множество точек, удовлетворяющее всем неравенствам.

Для простоты предположим сначала, что нету вертикальных прямых. Рассмотрим множество прямых, полуплоскости которых "смотрит" вних и полуплоскости которых "смотрят" вверх.

Пусть у нас есть множество полуплоскостей, которые "смотрят" в одну сторону. Пусть для простоты они смотрят вверх. Тогда рассмотрим все прямые, которые разделяют плоскость. Мы хотим найти такую верхнюю огибающую всех прямых, то есть выбрать в каждой $x$ координате максимальную точку с такой $x$ координатой, лежащую на одной из прямых. Этот метод также используется в очень известном методе Convex hull trick. Попробуем повторить что-то типо Алгоритма Грэхэма. Отсортируем все прямые по углу с осью $oX$. Будем перебирать прямые в таком порядке и в стеке поддерживать верхнюю огибающую для тех прямых, которые мы перебрали. Для каждой прямой будем поддерживать минимальную $x$ координату, начиная с которой эта прямая максимальная. При добавлении новой прямой мы должны будем выкинуть из стека несколько последних прямых и добавить новую. Пока стек непустой будем вынимать из него последнюю прямую. Рассмотрим точку пересечения этой прямой с нашей. Если $x$ координата этого пересечения будет не больше чем минимальная $x$ координата, начиная с которой последняя прямая из стека была максимальной, то последняя прямая в стеке больше никогда не будет максимальной и мы должны вынуть ее из стека. После этого надо добавить эту прямую в конец стека и минимальная $x$ координата начиная с которой эта прямая будет максимальной будет равна $x$ координате последней точки пересечения (во время того как мы вынимали последнюю прямую из стека).

Далее надо пересечь две цепочки: полуплоскостей смотрящих вниз и смотрящих вверх. Для этого переберем все пары звеньев верхней и нижней цепочки и попробуем их пересечь. Таким образом найдется $\leq 2$ точек пересечения, которые надо будет добавить в фигуру пересечения и удалить все звенья левее и правее добавленных точек.

Для того, чтобы разобраться с вертикальной прямой, можно попробовать пересечь ее с полученной конструкцией (что очень неприятно), а можно просто выбрать любую пару перпендикулярных векторов и сказать, что новые направления осей это эти вектора и в зависимости от этого выбрать какие полуплоскости смотрят вверх, а какие вниз.

Общее время работы составляет $O(n^2)$.




Автор конспекта: Иван Сафонов

По всем вопросам пишите в telegram @isaf27