Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 218
Текст из файла (страница 218)
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нтекздст, это означает, что произошел выход из процедуры до обработки всех точек-событий. Это может произойти только в том случае, когда в этой процедуре уже была обнаружена точка пересечения и процедурой возвращено значение тле. Таким образом, если отрезки пересекаются, то процедура Ам' Яваиннтз 1нтккзкст возвращает значение тле.
Как мы уже убедились, если процедура Ану Беамннтз 1нтникст возвращает значение тадж, отрезки пересекаются. Поэтому рассматриваемая процедура всегда выдает правильный ответ. Время работы Если в множестве Я содержится и отрезков, то процедура Аму БеОментз 1нтепзпст выполняется в течение времени 0 (и 1я и). Выполнение строки 1 занимает время О (1).
Строка 2 с помощью сортировки слиянием или пирамидальной сортировки выполняется в течение времени 0 (п1яп). Поскольку всего имеется 2п точек-событий, цикл 1ог в строках 3-11 повторяется не более 2п раз. На каждую итерацию требуется время 0 (18 п), поскольку выполнение каждой операции в красно-черном дереве занимает время О (1к и), и с помощью метода, описанного Часть Ч1!. Избранные темы 1062 Упражнения 33.2-1. Покажите, что в множестве, состоящем из п отрезков, может быть О (пз) пересечений.
33.2-2. Пусть отрезки а и Ь сравнимы в координате х. Покажите, как за время 0 (1) определить, какое из соотношений выполняется — а > Ь или Ь > а. Предполагается, что вертикальные отрезки отсутствуют. (Указание: если отрезки а и Ь не пересекаются, достаточно просто воспользоваться векторным произведением. Если же эти отрезки пересекаются, что выявляется путем вычисления векторных произведений, то и в этом случае можно ограничиться только операциями сложения, вычитания и умножения, и избежать деления. Если отрезки а и Ь пересекаются, достаточно просто вывести сообщение, что обнаружено пересечение.) 33.2-3.
Профессор предложил модифицировать процедуру Ан~' Бнпмечтз 1нтннзнСт таким образом, чтобы она не прекращала работу после того, как будет обнаружено пересечение, а выводила пересекающиеся отрезки и переходила к выполнению следующей итерации цикла 1ог. Профессор назвал получившуюся в результате процедуру Рнп й' 1нтнкзнстпчс Бнамннтз и заявил, что она выводит все пересечения, следующие слева направо в том порядке, в котором они располагаются в множестве от- резков. Покажите, что профессор ошибается в двух аспектах.
Для этого приведите пример множества отрезков, для которых первая точка пере- сечения, обнаруженная процедурой Рипа 1нтнкзнстпчо Бнпмннтз, не является самой левой, а также пример множества отрезков, для которых эта процедура выявляет не все пересечения. Разработайте алгоритм, позволяющий в течение времени 0 (и 1я п) опре- 33.2-4. делить, является ли и-угольник простым. Разработайте алгоритм, позволяющий в течение времени 0 (и 1к и) опре- 33.2-5. делить, пересекаются ли два простых многоугольника, суммарное коли- чество вершин в которых равно п.
Круг (<Ыс) состоит из окружности и ее внутренней области, и его можно представить при помощи центра и радиуса. Два круга пересекаются, если у них есть хоть одна общая точка. Приведите алгоритм, позволяющий в течение времени О (п1кп) определить, пересекаются ли какие-либо два круга из множества, состоящего из п кругов.
33.2-6. в разделе 33.1, каждый тест на пересечение удается выполнить за время 0 (1). Таким образом, полное время равно О (п 1к и). Глава 33. Вычислительная геометрия 1063 33.2-7. Пусть задано множество, состоящее из п отрезков, между которыми имеется й пересечений. Покажите, как вывести данные по всем пересечениям в течение времени О Ип + lс) 18 п). 33.2-8.
Покажите, что процедура Аыу Бепмехтз 1хтеизест работает корректно даже в том случае, если в одной и той же точке пересекается три или больше отрезков. 33.2-9. Покажите, что процедура Ам" БЕамннтз 1итнинст работает корректно даже в том случае, если в числе ее входных отрезков есть вертикальные. При этом нижние конечные точки вертикальных отрезков обрабатываются как левые конечные точки, а верхние — как правые конечные точки. Как изменится ответ в упражнении 33.2-2, если допускается наличие вертикальных отрезков? 33.3 Построение выпуклой оболочки Выпуклой оболочкой (сопкех 1ш1!) множества точек Я называется наименьший выпуклый многоугольник Р, такой что каждая точка из Я находится либо на границе многоугольника Р, либо в его внутренней области.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
