Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Рис. 7.16. Точка пересечения р обнаружена при х = хи когда отрезки s, и s2 впервые стали смежными. Однако события с абсциссами х2, хг и xt необходимо обработать раньше, чем точку р с абсциссой хъ.
за время, логарифмически связанное с его размером. На практике использование прошитого словаря (с прямым употреблением указателей, если адрес s известен) позволяет реализовать функции НАД(х) и ПОД^) за константное время.
Относительно списка точек событий заметим, что для регистрации всех пересечений нужно уметь поддерживать отношение >х в течение всего процесса заметания плоскости. Как указано ранее, упорядочение >х изменяется только в некоторых абсциссах (см. случаи 1, 2 и 3 выше), которые являются концами отрезков или точками их пересечения. В то время как все концы отрезков заданы заранее, точка пересечения, найденная плоским заметанием, динамически порождает событие, которое, вообще говоря, должно запоминаться и обрабатываться алгоритмом в нужный момент. Заметим, что в действительности, возможно, придется обработать несколько других событий за время, прошедшее с момента обнаружения какой-нибудь
Гл. 7. Пересечения
точки пересечения до момента ее обработки. На рис. 7.16 дан пример подобной ситуации: там точка пересечения р обнаружена в момент х\ (когда отрезки s\ и s2 стали смежными); однако необходимо обработать абсциссы х2, хг и х4 перед обработкой соответствующего р события х5. Следовательно, показано, что для отчета обо всех пересечениях структура данных &, создаваемая для работы со списком точек событий, должна поддерживать следующие операции (в & хранится полное упорядочение точек событий):
a. MIN(lf). Определить наименьший элемент в $ и удалить его.
b. ВСТАВИТЬ (х,&). Вставить абсциссу х в полное упорядочение, хранимое в 8.
В дополнение к этим важнейшим операциям необходимо, чтобы 8 поддерживала также операцию:
c. ЧЛЕН(х, 8). Узнать, является ли абсцисса х членом 8.
Указанная структура данных представляет собой очередь с приоритетом (см. разд. 1.2.3), и, как хорошо известно, она поддерживает все три описанные операции за время, логарифмически связанное с ее размером.
Теперь можно описать алгоритм: при заметании плоскости вертикалью в каждой точке события структура данных & корректируется и все пары отрезков, которые становятся смежными при этой корректировке, проверяются на пересечение. Если какое-нибудь пересечение обнаружено впервые, о нем дается отчет (вывод на печать), и его абсцисса вставляется в список точек событий 8. Более формально приведенные рассуждения выражены в процедуре (здесь очередь si- — рабочий параметр процедуры) [Bentley, Ottmann (1979)]:
procedure ПЕРЕСЕЧЕНИЕ-ОТРЕЗКОВ
1. begin сортируем 2 TV концов отрезков лексикографически
по х и у и помещаем их в приоритетную очередь 8:
2. ^:=0;
3. while (8 ф 0) do
4. begin p:=MIN (8);
5. if (р — левый конец) then
6. begin s'= отрезок, концом которого служит р;
7. ВСТАВИТЬ(5,2');
8. s,:=HAA(s,S');
9. s2:=nOR(s,gy,
Ю- if (si пересекает s) then ^-*=(s,,s);
П. if (s2 пересекает s) then st<=(s,s2) end;
7.2. Плоские приложения
347
12. else if (р — правый конец) then
begin s:=отрезок, концом которого служит р;
13. $,:=НАД(а, S);
14. s2 := ПОД(5,2);
15. if (s, пересекает s-> справа от р) then st<=(sh s>);
16. УДАЛИТЬ^,.24 end
17. else(* р — точка пересечения*)
18. begin(s, ,s2) := отрезки, пересекающиеся в р; (* причем S[ = НАД(«2) слева от р *)
19. s3:=hamsl,&);
20. 54:=ПОД(52,^);
21. if(s3 пересекает s2) then st<=(s3, s2);
22. if (s, пересекает s4) then ^ -<= (s,s4);
23. поменять местами Sj и s2 ъ 2! end
(* теперь найденные пересечения следует обработать *)
24. while (st ф 0) do
25. begin (s,s')<=st;
26. x := общая абсцисса s и s';
27. if (ЧЛЕН(х,#) = ЛОЖЬ) then
28. begin вывод (s,s')\
29. ВСТАВИТЬСЯ) end
end
end
end.
При таком алгоритме не будет пропущено ни одного из пересечений, поскольку могут пересечься только смежные отрезки, причем все смежные пары корректно проверяются по крайней мере однажды. Более того, каждое пересечение регистрируется ровно один раз, поскольку, когда его абсцисса вставляется в &, проверка в строке 27 предупреждает нежелательные повторы ').
С точки зрения оценки заметим: операция строки 1 (начальная сортировка) выполняется за время O(NlogN). Блоки 6—11, 13—16 и 18—23 выполняются каждый за время O(logJV), поскольку каждая операция на ? укладывается в
') Для обработки возможной ситуации, когда разные пересечения обладают одной и той же абсциссой, достаточно так строить &, чтобы точки пересечения перечислялись в лексикографическом порядке пар (х, у).
348
Гл. 7. Пересечения
такую временную оценку в худшем случае, а проверка попарного пересечения требует константного времени. Для каждого события, т. е. для каждого исполнения главного цикла while (строка 3), эти три блока являются взаимоисключающими. Если через К обозначить число пересечений, встреченных алгоритмом, то главный цикл while выполняется ровно (2N + К) раз. Единственное обстоятельство, которое все еще заслуживает пристального внимания, относится к структуре данных 8, а именно сколько раз будет выполняться проверка, помещенная в строке 27? Между прочим, заметим, что какое-нибудь одно пересечение можно повторно обнаруживать очень много раз; однако если соотнести каждую пересекающуюся пару с тем выполнением главного цикла while, на котором она обнаружена, то станет ясно, что общее число обнаруженных пересечений равно 0(N + К). Поэтому строка 27 выполняется 0(N + +/С) раз, а каждое выполнение требует 0(log(N -\- К)) =
