Использование сканирующей прямой для поиска пары пересекающихся отрезков.
Данный алгоритм выполняется за \(O(n \log n)\).
Задача
Даны n отрезков на плоскости. Требуется проверить, пересекаются ли друг с другом хотя бы два из них. (Если ответ положителен — то вывести номера этих пересекающихся отрезков; среди нескольких ответов достаточно выбрать любой из них.)
Алгоритм
Назовем началом отрезка один из концов отрезка, который лежит правее другого конца, в случае с вертикальными — который выше (на рисунке обозначены голубым). А другой конец назовем к-конец (розовый).
Создадим структуру Point, которая будет хранить два вещественных значения x и y (x-координата и y-координата соответственно). Пусть в структуре seg будет два члена структуры, Point beg и Point fin (точка начала и к-конца отрезка). Будем хранить в списке segList элементы структуры seg. Причем i-ый элемент будет содержать параметры i-го отрезка. Заметим, что мы можем всегда узнать координаты отрезка по его номеру.
В список ListA поместим каждый конец отрезков, хранящий информацию о его x-координате, о том, каким концом он является (пусть -1 — начало, а +1 — к-конец) и о номере его отрезка.
Отсортируем ListA и проведём мысленно вертикальную прямую через самый левый конец — первый элемент списка ListA (пунктирная прямая на рисунке). Начнём двигать эту прямую вправо. Заметим, что прямая будет пересекать точки именно в том порядке, в котором они расположены в списке ListA. По ходу своего движения эта прямая будет встречаться с отрезками, причём в любой момент времени каждый отрезок будет пересекаться с нашей прямой по одной точке или лежать на ней. Таким образом, для каждого отрезка в какой-то момент времени его точка появится на сканирующей прямой, затем с движением прямой будет двигаться и эта точка, и, наконец, в какой-то момент отрезок исчезнет с прямой.
Нас интересует относительный порядок отрезков по вертикали. А именно, мы будем хранить множество отрезков (назовем ListB), пересекающих сканирующую прямую в данный момент времени. Когда прямая перестанет пересекать какой-то отрезок, мы просто удалим его из множества.
Мы проходимся циклом по списку ListA и каждый раз проверяем тип отрезка. Если рассматриваемый конец является началом, находим место отрезка в ListB: по y-координате начала. Дальше проверяем на пересечение новый отрезок с его соседями в множестве ListB, а затем вставляем отрезок на его место. Если рассматриваемый конец является к-концом, удаляем его и проверяем на пересечение его соседние отрезки.
Если отрезки пересекаются мы их выводим и останавливаем программу. Если нет продолжаем поиск пока не пройдем весь цикл.
Нам достаточно проверять на пересечение соседние отрезки, так как если отрезок L пересекает несоседний отезок K, то
• или соседний он тоже пересекает (требуется вывести хотя бы два пересекающихся отрезка, если есть);
• или у всех отрезков, находящихся между ними, к-концы левее обоих к-концов этих отрезков. Тогда при удалении последнего отрезка между L и K, они станут соседними;
• или у всех отрезков, находящихся между ними, начала правее обоих начал этих отрезков. Значит, при добавлении одного из отрезков L и K, они были соседними.
Заметим, что данный алгоритм будет работать также и для вертикальных отрезков, так как после сортировки начало этого отрезка будет раньше, чем конец в списке ListB (x-координаты у этих точек равны, а -1 < +1). Мы также добавляем эти отрезки, проверяем условия и убираем их из списка.