Алгоритмы - построение и анализ (1021735), страница 218
Текст из файла (страница 218)
Каждая такая точка останова называется точкой-событием (ечелг рошг). Состояние относительно выметающей прямой определяется только в точках-событиях. В некоторых алгоритмах (например, в том, который предлагается разработать в упражнении 33.2-7) таблица точек-событий строится динамически, в ходе работы алгоритма. Однаю в алгоритме„о ютором сейчас пойдет речь, точки-события определяются статически, исходя исключительно из простых свойств входных данных. В частности, в роли точки-события выступает каждая конечная точка отрезка.
Конечные точки отрезков сортируются в порядке возрастания координат х (т.е. слева направо). (Если две или более точек ковергникальны (сочегг1са1), т.е. их координаты х совпадают, этот узел можно "разрубить", поместив все ковертикальные левые конечные точки перед ковертикальными правыми конечными точками. Если в множестве ковертикальных левых точек есть несколько левых, первыми среди них будут те, которые имеют меньшее значение координаты у, и то же самое выполняется в множестве ковертикальных правых конечных точек.) Отрезок помещается в набор состояний относительно выметающей прямой, 1058 Часть Ч11. Избранные темы когда пересекается его левая конечная точка; этот отрезок удаляется из набора состояний относительно выметающей прямой, когда пересекается его правая конечная точка.
Если два отрезка впервые становятся последовательными в полном упорядочении, выполняется проверка, пересекаются ли онн. Состояние относительно выметающей прямой является полностью упорядоченным множеством Т, в котором необходимо реализовать такие операции: ° 1нзект(Т, з): вставка отрезка з в множество Т; ° ПН.ЕТЕ(Т, з): удаление отрезка з из множества Т; ° Авоче(Т, з): возвращает отрезок, расположенный непосредственно над отрезком з множества Т; ° Вн.св(Т, з): возвращает отрезок, расположенный непосредственно под отрезком з множества Т.
Если всего имеется п входных отрезков, каждую из перечисленных выше операций с помощью красно-черных деревьев можно выполнить в течение времени 0(18п). Напомним, что операции над красно-черными деревьями, описанные в главе 13, включают в себя сравнение ключей. Однако в нашем случае сравнение ключей можно заменить векторным произведением, позволяющем определить относительный порядок двух отрезков (см. упражнение 33.2-2). Псевдокод, выявляющий пересечение отрезков В приведенном ниже алгоритме в качестве входных данных выступает множество Я, состоящее из и отрезков. На выходе возвращается булево значение ТЛЕ, если любая пара отрезков из множЕства Я пересекается, и значение ЕИ.ЗЕ в противном случае.
Полное упорядочение Т реализуется с помощью красно-черного дерева. АХЪ' ЯЕСМЕХТБ 1ХТЕКБЕСТ(Я) 1 Т+-О 2 Сортировка конечных точек отрезков из множества Я слева направо, разрешение совпадений путем помещения левых конечных точек перед правыми и путем помещения точек с меньшими координатами у перед теми, у которых координата у больше 3 1ог каждой точки р из отсортированного списка конечных точек 4 йе!Г р — левая конечная точка отрезка з 5 т1зеп 1нзект(Т, з) б Ы (Авочв(Т, з) существует и пересекает отрезок з) или (ВН.С®(Т, з) существует и пересекает отрезок з) 7 тьеп гетпгп ткце Глава 33. Вычислительная геометрия 1059 8 11 р — правая конечная точка отрезка а 9 11ьеп Ы существуют АВВЕ(Т, а) и ВЕЕОцс(Т, а), и Авоче(Т, а) пересекает Вн.очг(Т, а) 10 Феп геснгп тине 11 13ЕЕЕТЕ(Т,а) 12 гегнгн ВА1ле Работа этого алгоритма проиллюстрирована на рис.
33.5. Каждая пунктирная линия является выметающей прямой, проходящей через одну из точек-событий. Под каждой из них приведено полностью упорядоченное множество Т в момент окончания итерации цикла Гог, соответствующей данному событию. В момент удаления отрезка с обнаружено пересечение отрезков с1 и б. В строке 1 инициализируется пустое множество полностью упорядоченных отрезков. В строке 2 путем сортировки 2п конечных точек отрезков слева направо создается таблица точек-событий, а ковертикальные точки обрабатываются так, как описано выше.
Заметим, что строку 2 можно выполнить путем лексикографической сортировки конечных точек (х, е, у), где т и р — обычные координаты, а значение переменной е принимает значение 0 для левых конечных точек и значение 1 — для правых конечных точек. При каждой итерации цикла 1ог в строках 3-11 обрабатывается одно событие р. Если р — левая конечная точка отрезка в, то этот отрезок добавляется в строке 5 в полностью упорядоченное множество.
В строках 6-7 возвращается значение ткое, если отрезок а пересекает какой-нибудь из соседних отрезков полностью упорядоченного множества, определенного выметающей прямой, которая проходит через точку р. (Если точка р находится на другом отрезке а', то имеет место граничный случай. При этом лишь требуется, чтобы отрезки а и г' были после- а а а Н я е е Ь с а с Я Ь с Ь с Ь' ь Ь Весна Рис. 33.5.
Выполнение процедуры Ант Беоментз 1нтеааест Часть Ч11. Избранные темы 1060 довательными в множестве Т ) Если р — правая конечная точка отрезка л, то этот отрезок подлежит удалению из полностью упорядоченного множества. В строках 9-10 возвращается значение тепе, если пересекаются ближайшие к отрезку д отрезки из полностью упорядоченного множества, определенного с помощью выметающей прямой, которая проходит через точку р. После удаления из полностью упорядоченного множества отрезка и ближайшие к нему отрезки становятся последовательными в этом множестве. Если эти отрезки не пересекаются, отрезок л в строке ! 1 удаляется из полностью упорядоченного множества. Наконец, если во всех 2п точках-событиях не обнаружено никаких пересечений, в строке 12 возвращается значение ЕАьзе. Корректность Чтобы показать, что процедура Ам' Яюмеитз 1мтеязест работает корректно, докажем, что при вызове Аыу Бесмемтз 11чтекзест(Я) значение тнг3е возвращается тогда и только тогда, когда какие-либо отрезки из Я пересекаются.
Очевидно, что процедура Аиу Бесмемтз !мтензест возвращает значение тле (в строках 7 и 10) толью в том случае, когда в ней будет обнаружено пересечение между двумя входными отрезками. Таким образом, если возвращается значение тиж, то пересечение существует. Следует также показать обратное: если пересечение существует, то процедура Аму Беамемтз 1мтекзест возвращает значение тле. Предположим, что существует по крайней мере одно пересечение.
Пусть р — самая левая точка пересечения (если таких точек несколько, то вьгбирается та из них, у которой наименьшая координата у), а а и Ь вЂ” отрезки, пересекающиеся в этой точке. Поскольку слева от точки р нет никаких пересечений, порядок, заданный в множестве Т, остается правильным во всех точках, которые находятся слева от точки р. Так как никакие три отрезка не пересекаются в одной и той же точке, существует выметающая прямая и, относительно которой отрезки а и Ь расположены последовательно в полностью упорядоченном множествез. Более того, прямая и проходит через точку р или слева от нее.
На выметающей прямой л находится конечная точка д какого-нибудь отрезка, которая выступает в роли события, при котором отрезки а и Ь становятся последовательными в полностью упорядоченном множестве. Если на этой выметаюшей прямой лежит точка р, то 9 = р. Если же точка р не принадлежит выметающей прямой л, то точка 9 находится слева от точки р. В любом случае порядок, установленный в множестве Т, является Если позволить трем отрезхам пересекаться в одной точке, появится возможность существования промежуточного отрезка с, пересекающего отрезки а и Ь в точке р.
Те. для всех выме- тающих прямых ю, расположенных слева от точки р, для которых а < Ь, могут выполняться соотношения а < с и с < Ь. В упражнении 33.2-8 предлагается показать, что пропедура Ант Звпмдитв Пчтяизвет работает корректно, даже если три отрезка пересекаются в одной и той же точке. Глава 33.
Вычислительная геометрия 1061 правильным непосредственно перед точкой д. (Вот где используется лексикографический порядок, в котором алгоритм обрабатывает конечные точки. Поскольку р — нижайшая из самых левых точек пересечения, то даже если она лежит на выметающей прямой я и на этой прямой есть еще одна точка пересечения р', точка-событие д = р обрабатывается перед тем, как эта другая точка пересечения сможет повлиять на порядок отрезков в упорядоченном множестве Т. Кроме того, если р — левая конечная точка одного отрезка (скажем, отрезка а) и правая конечная точка другого отрезка (скажем, отрезка Ь), то в силу того, что левые точки- события расположены перед правыми, отрезок Ь уже будет находиться в множестве Т, когда в это множество попадет отрезок а.) Каждая точка-событие д либо обрабатывается процедурой АХУ ЗЕОМЕМТ$1ХТЕКЗЕСТ, либо нет.
Если точка д обрабатывается процедурой Ану Бксмемтз 1нтнкзнст, возможны всего два варианта выполняемых действий. 1. Отрезок а либо отрезок Ь помещается в множество Т, и в этом множестве один из них расположен над или под другим. То, какой из этих случаев имеет место, определяется в строках 4-7. 2. Отрезки а и Ь уже содержатся в множестве Т, а расположенный между ними отрезок удаляется из этого множества, в результате чего отрезки а и Ь становятся последовательными. Этот случай выявляется в строках 8-11. При реализации любой из перечисленных выше возможностей выявляется точка пересечения р, и процедура Аму Ядпментз 1нтекзест возвращает значение типе. Если точка д не обрабатывается процедурой Ам' Бепментз 1нтекздст, это означает, что произошел выход из процедуры до обработки всех точек-событий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
