Поиск пары пересекающихся отрезков
Постановка задачи
Задано множество S, состоящее из n отрезков на плоскости. Каждый отрезок si=S[i] (i = 1, 2,…, n) задан координатами его концевых точек в декартовой системе координат. Требуется определить, есть ли среди заданных отрезков по крайней мере два пересекающихся (см. [1], [3]).Если пересечение существует, то алгоритм должен выдать значение “истина” (“true”) и номера пересекающихся отрезков s1 и s2, в противном случае - “ложь” (“false”).
Наивный алгоритм поиска пересечения
Перебираются пары отрезков до тех пор, пока не будет обнаружено пересечение, либо же не будут исчерпаны все пары.
function INTERSECTION_NAIVE(S, var s1, s2): boolean;
begin
INTERSECTION_NAIVE:= false;
for i:= 1 to n-1 do for j:=i+1 to n do if (S[i] пересекает S[j]) then begin
b:= true; s1:= S[i]; s2:= S[j]; INTERSECTION_NAIVE:= true; exit;
end;
end;
Временная сложность этого наивного алгоритма есть O(n2).
Эффективный алгоритм поиска пересечения
В этом алгоритме используется так называемый метод вертикальной заметающей прямой, движущейся в сторону возрастания абсциссы. В каждый момент времени заметающая прямая пересекает отрезки, которые образуют динамически меняющееся множество L. Отрезки в множестве L упорядочиваются по неубыванию ординат точек их пересечения с заметающей прямой. Множество L представляется АВЛ-деревом и модифицируется с помощью операций удаления и вставки элементов.
В алгоритме используются две операции ПОД(s, L) и НАД(s, L), позволяющие за время O(log |L|) определить непосредственно предшествующий отрезок и отрезок, непосредственно следующий за отрезком s в последовательности L.
Если не существует отрезка, предшествующего отрезку s или следующего за ним, то процедуры ПОД(s, L) и НАД(s, L) выдают произвольный отрезок, заведомо не пересекающийся с отрезками из множества S. Это требование введено для того, чтобы не усложнять алгоритм лишними деталями.
Операция ВСТАВИТЬ(s, L) осуществляется в момент, когда заметающая прямая достигает левого конца отрезка s, а операция УДАЛИТЬ(s, L), когда она достигает его правого конца. Обе эти операции осуществляются за время O(log |L|).
Полагаем, что точка ui = (ui.1, ui,2) лексикографически меньше точки vi = (vi.1, vi,2), если либо ui.1<vi.1, либо (ui.1=vi.1)&(ui.2<vi.2).
В алгоритме используется массив ТОЧКА[1..2n], элементы которого соответствуют концам отрезков. В каждом элементе представлены координаты точки, номер отрезка и информация о том, каким концом, левым или правым, для соответствующего отрезка является данная точка.
function INTERSECTION_EFFECTIVE(S, var s1, s2): boolean;
begin
Лексикографическая сортировка 2n концов отрезков и помещение результата в массив ТОЧКА[1..2n];
INTERSECTION_EFFECTIVE:= false;
for i:= 1 to 2*n do
begin
p:= ТОЧКА[i]; s:= отрезок, концом которого является p;
if (p - левый конец отрезка s) then begin
ВСТАВИТЬ(s, L);
s1:= НАД(s, L); s2:= ПОД(s, L);
if (s1 пересекает s) or (s2 пересекает s) then begin
INTERSECTION_EFFECTIVE:= true; exit;
end;
end else begin
s1:= НАД(s,L); s2:= ПОД(s, L);
if (s1 пересекает s2) then begin
INTERSECTION_EFFECTIVE:= true; exit;
end;
УДАЛИТЬ(s,L);
end;
end;
end;
Корректность работы алгоритма основана на том, что до момента, когда пересечение будет обнаружено и алгоритм, таким образом, завершит работу, включаемые в последовательность L и удаляемые из нее отрезки не меняют упорядочения остальных.
Временная сложность данного алгоритма с использованием АВЛ-дерева поиска пересечения есть O(n×log n).
Задания для лабораторной работы № 7
1. Написать программу, реализующую наивный алгоритм и алгоритм с использованием АВЛ-дерева для решения поставленной задачи, основываясь на процедурах INTERSECTION_NAIVE иINTERSECTION_EFFECTIVE.
2. Модифицировать написанные программы для проведения экспериментов, в которых можно выбирать:
· число n рассматриваемых отрезков с вещественными координатами концов,
· способ задания отрезков из числа следующих:
· автоматический с псевдослучайными координатами концов из квадрата единичной длины,
· автоматический с задаваемой длиной r всех отрезков и псевдослучайными координатами их центров из квадрата единичной длины и псевдослучайными величинами углов, образуемых прямыми, проходящими через эти отрезки, с осью абсцисс,
· непосредственный ввод координат концов отрезков.
Выходом данной программы должно быть время работы Т1 тривиального алгоритма и время работы Т2 нетривиального алгоритма в секундах.
При этом в автоматических способах задания отрезков должна быть предусмотрена возможность ввести число k<n-1 и сделать так, чтобы первые k отрезков не пересекались ни между собой, ни с оставшимися, а отрезки с номерами k+1 и k+2 пересекались между собой.
3. Провести эксперименты на основе следующих данных:
3.1. первый способ задания отрезков, n = 1, … ,104+1 с шагом 100 (нарисовать графики функций T1(n) и T2(n)),
3.2. первый способ задания отрезков, n = 104+3, k = 1, … ,104+1 с шагом 100 (нарисовать графики функций T1(k) и T2(k)),
3.3. второй способ задания отрезков, r = 0,001, n = 1, …, 104+1 с шагом 100 (нарисовать графики функций T1(n) и T2(n)),
3.4. второй способ задания отрезков, r = 0,0001, …, 0,01 с шагом 0,0001, n = 104 (нарисовать графики функций T1(r) и T2(r)).
4. Сформулировать и обосновать (на основе псевдокодов алгоритмов и практических данных, для получения которых можно провести дополнительные эксперименты) вывод о том, в каких случаях целесообразно применять наивный алгоритм, а в каких - эффективный.
Приложение: генерация графов для экспериментов
Нас будет интересовать генерация графа G = (V, E) с n вершинами (множество вершин V = {1, … , n}) и m ребрами (множество ребер E, m=|E|) из двух классов графов: класса ориентированных графов без петель и класса обыкновенных графов. В любом из этих двух случаев задача решается единообразно: первоначально каким-либо образом на множестве Еmax (заметим, что в практическом построении этого множества нет необходимости) всех возможных ребер графа с множеством вершин V = {1, … , n} устанавливается строгий линейный порядок (тем самым обретают смысл понятия следующего и предшествующего ребра) и далее последовательно строятся требуемые m ≤ |Еmax| ребер, каждое ребро e из которых строится следующим образом:
псевдослучайно генерируется ребро e’,
если e’ не было построено ранее, то ребро e=e’ считается построенным,
если e’ уже было построено ранее, то осуществляется поиск первого ребра из следующих после e’ ребер, которое еще не было построено, если такое ребро e’’ существует, то ребро e=e’’ считается построенным, если же такого ребра не существует, то осуществляется поиск первого ребра e’’’ из предшествующих e’ ребер, которое еще не было построено, и ребро e=e’’’ считается построенным.
Литература
1. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
2. В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. Лекции по теории графов. – М.: Наука, Гл. ред. физ.-мат. лит., 1990.
3. Ф. Препарата, М. Шеймос. Вычислительная геометрия: Введение. – М.: Мир, 1989.
4. А. Шень. Программирование: теоремы и задачи. – М.: МЦНМО, 1995.
5. В.Е.Алексеев, В.А.Таланов. Графы. Модели вычислений. Структуры данных: Учебник. – Нижний Новгород: Изд-во ННГУ, 2005.