Участник:Komarov/Гайд по вычгеому

Дисклаймер

Всё написанное ниже является моим личным мнением и на правильность не претендует. Но, вроде бы, всё именно так и есть.

Q&A

Я не ходил[а] на пары весь семестр. Что вообще нам надо делать???

Нужно сделать три задания. Первое — проверка двух отрезков на пересечение. Второе — алгоритм Бентли-Оттмана для нахождения всех точек пересечения набора отрезков. Третье — нахождение пересечения многоугольников. Ах да, конечно же, всё это абсолютно точно.

Эээээ, но ведь все говорят, что надо сделать только два задания. Почему тут три?

Второе задание можно явно не делать. Проблема в том, что очерёдность выполнения заданий строго определена. Для того, чтобы сделать второе, необходимо сделать сначала первое. Для третьего же необходимо второе. Да-да, алгоритм Бентли-Оттмана — всего лишь подзадача. Те, кто считают, что заданий два, называют первым пересечение отрезков, а вторым — пересечение многоугольников.

Аааа, всё плохо, что делать?

Увы, да, всё плохо. Писать

Пересечение многоугольников

Краткий план того, как пересекать многоугольники. На код не надейтесь, у самого ещё далеко до этого.

Постановка задачи

Данo 2[[math]k[/math]] многоугольников. Нужно найти множество многоугольников, являющееся их пересечением.

Многоугольники могут быть невыпуклые и дырявые.

Q: А чо такое дырявый многоугольик ваще? A: Это многоугольник, у которого внутри вырезан многоугольник. Например, рамочка — прямоугольник, из которого вырезали прямоугольник. Также, в многоугольнике может быть много дырок. К счастью (ага, счастье-то какое), входные данные корректны, и никаких дырок, пересекающих многоугольник нет. Дырок, пересекающих друг друга тоже нет. Похоже что, касаний тоже нет.

План решения

Многие будут удивлены, но если решать рассказанным нам методом, то ни невыпуклость, ни дырявость многоугольников задачи нам не усложняет. Жопа была — жопа и осталась.

STOP! Если ты, читатель, ещё не знаешь, что такое алгоритм Бентли-Оттмана и не понимаешь, как он работает, самое время исправить это недоразумение (недоразумение, ога).

STOP! Но это ещё не всё! Если ты не знаешь, что такое конфигурация, то тоже настоятельно рекомендуется ознакомиться.

Для простоты посмотрим сначала на случаи попроще.

Два выпуклых многоугольника

Что такое многоугольник? Это набор точек и соединяющих их отрезков. Хмммм... И что мы умеем делать с этим? Алгоритм Бентли-Оттмана! Запустим немного модифицированный алгоритм Бентли-Оттмана на наборе сторон обоих многоугольников.

Вспомним, как работал алгоритм Бентли-Оттмана. Сканирующая прямая бежала слева направо и обрабатывала события начала отрезка, конца отрезка и пересечения двух отрезков. Также хранился так называемый статус — множество пересекаемых в данный момент сканирующей прямой отрезков. Вот его-то модификацией мы сейчас и займёмся.

Так как в данный момент решается задача для двух выпуклых многоугольников, то в статусе может быть максимум четыре отрезка. Посмотрим на какую-нибудь точку из пересечения многоугольников. Посмотрим, какой был бы статус, если бы сканирующая прямая остановилась в этой точке. Луч из этой точки вверх должен пересечь границы обоих многоугольников (любой луч из любой точки внутри многоуголька пересекает его границу). Аналогично, луч вниз пересекает обе границы. Значит, в статусе четыре отрезка (не может быть больше, так как два выпуклых многоугольника, не может быть меньше, так как [math]2+2\geq 4[/math]). При этом, верхние два принадлежали разным многоугольникам и нижние два принадлежали разным многоугольникам.

Отлично, мы научились ловить момент, когда пересечение многоугольников есть. Для этого смотрим на статус и, если в нём четыре отрезка, и верхние два из разных многоугольников, то вот оно пересечение, по середине.

Теперь осталось его явно построить. Посмотрим на два соседних отрезка в статусе. Им соответствует какая-то область между ними. Если с этими отрезками не происходдит никаких событий, то и с областью ничего не происходит.

Посмотрим на момент, когда сканирующая прямая подошла к началу пересечения многоугольников. В этот момент произошло событие — пересеклись два отрезка и образовали новую область. Посмотрев на соседние с пересёкшимися отрезками области, можно сказать, какая из них — искомое пересечение и начать его выводить (ну или что там с ним надо делать?). Далее с этой областью будут происходить всякие разные события — отрезок закончился, начался новый отрезок... Это не должно нас останавливать, область всё равно остаётся пересечением. Заканчивается же всё когда два отрезка, ограничивающие эту область, заканчиваются. После этого события область уничтожается и пересечение заканчивается.

В итоге мы получили набор отрезков — границу пересечения многоугольников. Из них составим многоугольник, который и будет ответом.

Заметим, что алгоритм работает за линейное (офигеть, да?) время. Основная идея — в том, чтобы следить за областью и понимать, является ли она пересечением или нет.

Два многоугольника

Будем делать практически то же самое. Возникает проблема. В статусе может быть больше, чем четыре отрезка. Но это не такая и проблема, ведь суть алгоритма уже ясна (хочется в это верить) и понятно, что ограничение на количество отрезков в статусе было нужно только для определения того, является ли область искомым пересечением.

Будем для каждой области хранить, лежит ли она внутри первого и лежит ли она внутри второго многоугольников. Тогда нас интересуют области, которые лежат внутри обоих.

Пересчёт этих значений можно осуществить, храня для каждого отрезка, слева от него внутрь или наружа многоугольника. Тогда если слева от него наружа, то то область под ним в статусе будет внутри, а над ним — снаружи. Таким образом, пересчитывая эти флаги, приходим к требуемому результату.

Два дырявых многоугольника

Единственная модификация прошлого случая, которую тут необходимо сделать, заключается в том, чтобы правильно посчитать ориентацию отрезков сторон дырки. После этого всё абсолютно так же, как в прошлом случае.

Много дырявых многоугольников

Единственная модификация по сравнению с прошлым алгоритмом — для каждой области нужно хранить не два флага принадлежности, а столько, сколько всего требуется пересечь многоугольников и объявлять область пересечением только если она лежит внутри всех многоугольников.

Деталь реализации

Перед запуском алгоритма удобно сначала запустить первый проход алгоритма Бентли-Оттмана и разбить стороны так, чтобы они пересекались только по вершинам. Просто, если два отрезка пересекаются, создаём в этой точке новую вершину и разбиваем ребро на два (или больше, чем на два, как повезёт).

Сложность алгоритма

сложный

Сложность совпадает со сложностью алгоритма Бентли-Оттмана — [math]\mathcal{O}((n + K) \log n)[/math]