Поиск пары пересекающихся отрезков

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

Задано множество S, состоящее из n отрезков на плоскости. Каждый отрезок s_i=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(n²).

 

Эффективный алгоритм поиска пересечения

В этом алгоритме используется так называемый метод вертикальной заметающей прямой, движущейся в сторону возрастания абсциссы. В каждый момент времени заметающая прямая пересекает отрезки, которые образуют динамически меняющееся множество 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|).

Полагаем, что точка u_i = (u_i.1, u_i,2) лексикографически меньше точки v_i = (v_i.1, v_i,2), если либо u_i.1<v_i.1, либо (u_i.1=v_i.1)&(u_i.2<v_i.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 всех отрезков и псевдослучайными координатами их центров из квадрата единичной длины и псевдослучайными величинами углов, образуемых прямыми, проходящими через эти отрезки, с осью абсцисс,

· непосредственный ввод координат концов отрезков.

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

При этом в автоматических способах задания отрезков должна быть предусмотрена возможность ввести число k<n-1 и сделать так, чтобы первые k отрезков не пересекались ни между собой, ни с оставшимися, а отрезки с номерами k+1 и k+2 пересекались между собой.

3. Провести эксперименты на основе следующих данных:

3.1. первый способ задания отрезков, n = 1, …,10⁴+1 с шагом 100 (нарисовать графики функций T₁(n) и T₂(n)),

3.2. первый способ задания отрезков, n = 10⁴+3, k = 1, …,10⁴+1 с шагом 100 (нарисовать графики функций T₁(k) и T₂(k)),

3.3. второй способ задания отрезков, r = 0,001, n = 1, …, 10⁴+1 с шагом 100 (нарисовать графики функций T₁(n) и T₂(n)),

3.4. второй способ задания отрезков, r = 0,0001, …, 0,01 с шагом 0,0001, n = 10⁴ (нарисовать графики функций T₁(r) и T₂(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.