Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 237
Текст из файла (страница 237)
В этом случае эти два отрезка могут находиться в Т в любом порядке. Если всего имеется и входных отрезков, каждую из перечисленных выше операций с помощью красно-черных деревьев можно выполнить за время 0(1кп). Напомним, что операции над красно-черными деревьями, описанные в главе 13, включают в себя сравнение ключей.
Однако в нашем случае сравнение ключей Глава ЗЗ. Вычислительная геометрия !077 можно заменить векторным произведением, позволяющим определить относи- тельный порядок двух отрезков (см. упр. 33.2.2), Псевдокод, выявляющий пересечение отрезков В приведенном далее алгоритме в качестве входных данных выступает множество Я, состоящее из и отрезков. На выходе возвращается булево значение тКОЕ, если некоторая пара отрезюв из множества Я пересекается, и значение еАезе— в противном случае.
Полное упорядочение Т реализуется с помощью красно- черного дерева. Аху-Беомехтз-1хтекзест(Я) 1 Т= И 2 Сортировка юнечных точек отрезков э слева направо с разрешением совпадений путем помещения левых конечных точек перед правыми и путем помещения точек с меньшими координатами у перед теми, координата у которых больше 3 Гог каждой точки р в отсортированном списке конечных точек 4 1Гр является левой конечной точюй отрезка я 5 1хзект(Т,а) 6 1Г (Авоч7е(Т, л) существует и пересекает л) или (Вн.озг(Т, я) существует и пересекает з) 7 гетигп ткое 8 1Г р является правой конечной точкой отрезка л 9 1Г (и Авоуе(Т, я), и Вн.ощ(Т, я) существуют) и (Авоч7е(Т, я) пересекает Вн.о!у(Т, л)) !О гетпгп ТКУЕ 11 ьгЕСЕТЕ(Т,л) 12 гетпгп еАйзе Работа этого алгоритма проиллюстрирована на рис.33.5.
В строке 1 инициализируется пустое множество полностью упорядоченных отрезков. В строке 2 путем сортировки 2п конечных точек отрезюв слева направо создается таблица точек-событий с разрешением совпадений, как сказано выше. Одним из способов выполнения строки 2 является лексиюграфическая сортировка конечных точек (х, е, у), где х и у — обычные координаты, а переменная е принимает значение О для левых конечных точек и значение 1 — для правых конечных точек.
Каждая итерация цикла Гог в строках 3 — 11 обрабатывает одну точку-событие р. Если р является левой точкой отрезка е, то в строке 5 этот отрезок е добавляется в полностью упорядоченное множество, а в строках 6 и 7 возвращается значение тКОЕ, если отрезок л пересекает любой из отрезков, соседних с данным в полностью упорядоченном множестве, определяемом выметающей прямой, проходящей через р.
(Если точка р находится на другом отрезке з', имеет место граничный случай. При этом требуется лишь, чтобы отрезки л и е' были последовательными в множестве Т.) Если р представляет собой правую конечную точку отрезка я, то этот отрезок подлежит удалению из полностью упорядочен- гогг Часть 171 Избранные тены а а а И а' е Ь г а г и Ь г Ь г Ь Ь Время Рне.
33.5. Выполнение процедуры Амт-зяомнмтз-1мтндзнст. Каждая пункгнрная линия явллетея выметающей прямой, проводящей через одну нз точек-еобьпнй. За исключением крайней справа вымегающей линии упорядочение имен отрезков внизу под юпкдой выметающей линией соответствует полному упорядочению Т в конце цикла Гог, обрабатывающего соответствующую точку-еобытне. Крайняя справа выметающая прямая соответствует обработке правой конечной точки отрезка е; поеколъку отрезкн Ы н Ь окружают с н пересекают один другой, процедура возвращает тнщц ного множества. Но сначала, если пересекаются окружающие а отрезки из полностью упорядоченного множества, определенного выметающей прямой, которая проходит через точку р, в строках 9 и 10 возвращается значение ткие. Если зти отрезки не пересекаются, в строке 11 отрезок л удаляется из полностью упорядоченного множества.
Приведенное ниже доказательство корректности пояснит, почему достаточно проверки отрезков, окружающих л. Наконец, если во всех 2п точках-событиях не обнаружено никаких пересечений, в строке 12 возвращается значение РАезе. Корректность алгоритма Чтобы показать, что процедура А1чу-Бебментз-1хтеизест работает корректно, докажем, что при вызове Аму-Беоме1чтз-11чтекзест(Я) значение тк11е возвращается тогда и только тогда, когда какие-либо отрезки из Я пересекаются. Легко видеть, что процедура А1чу-Бепме1чтб-11чтейзест возвращает значение Тк11Е (в строках 7 и 10) толью в том случае, когда в ней обнаружено пересечение между двумя входными отрезками.
Таким образом, если возвращается значение ткие, то пересечение существует. Следует также показать обратное: если пересечение существует, то процедура А1чу-Беоме1чтз-1мтекзест возвращает значение тп11е. Предположим, что существует по крайней мере одно пересечение. Пусть р — крайняя слева точка пересечения (если таких точек несколько, то выбирается точка с наименьшей координатой у), а а и Ь вЂ” отрезки, пересекающиеся в этой точке. Поскольку слева от точки р нет никаких пересечений, порядок, заданный в множестве Т, остается правильным во всех точках, которые находятся слева от точки р.
Так как никакие три отрезка не пересекаются в одной и той же точке, существует выметающая 1073 Глава 33. Вычислпюптьюгн геомеюрия прямая г, относительно которой отрезки а и 6 расположены последовательно в полностью упорядоченном множестве . Более того, прямая г проходит через точку р или слева от нее. На выметаюшей прямой д находится конечная точка г) какого-нибудь отрезка, которая выступает в роли события, при котором отрезки а и 6 становятся последовательными в полностью упорядоченном множестве. Если на этой выметающей прямой лежит точка р, то г3 = р.
Если же точка р не принадлежит выметающей прямой г, то точка д находится слева от точки р. В любом случае порядок, установленный в множестве Т, является правильным непосредственно перед точкой д. (Вот где используется лексикографический порядок, в котором алторитм обрабатывает конечные точки. Поскольку р — самая низкая из крайних слева левых точек пересечения, то даже если она лежит на вымегающей прямой з и на этой прямой есть еше одна точка пересечения р', точка-событие г) = р обрабатывается перед тем, как эта другая точка пересечения сможет повлиять на порядок отрезков в упорядоченном множестве Т. Более того, даже если р — левая конечная точка одного отрезка (скажем, отрезка а) и правая конечная точка другого отрезка (скажем, отрезка Ь), то в силу того, что левые точки-события расположены перед правыми, отрезок 6 уже будет находиться в множестве Т, когда в это множество попадет отрезок а.) Каждая точка-событие г) ЛИбО ОбрабатЫВаЕтСя ПрОцЕдурОй АИУ-БЕПМЕХТЗ-1ЫТЕКЕЕСТ, ЛИбО Нст.
ЕСЛИ тОЧКа г) ОбрабатЫВаЕтСя ПрОцЕдурОй А!йу-БЕаМЕНТЗ-1НТЕКЗЕСТ, ВОЗ- можны всего два варианта выполняемых действий. !. Отрезок а либо отрезок Ь помещается в множество Т, и в этом множестве один из них расположен над нли под другим. То, какой из этих случаев имеет место, определяется в строках 4-7. 2. Отрезки а и 6 уже содержатся в множестве Т, а расположенный между ними отрезок удаляется из этого множества, в результате чего отрезки а и 6 становятся последовательными. Этот случай выявляется в строках 8-! !.
В любом случае мы находим пересечение р, и процедура А!чу-Бепментз1МТЕКЗЕСТ возвращает ТК!3Е. Если точка-событие г! не обрабатывается процедурой Аыу-Беоментз- 1!чтекзест, это означает, что произошел выход из процедуры до обработки всех точек-событий. Это может произойти только в том случае, если в этой процедуре уже была обнаружена точка пересечения и процедурой возвращено значение ТК!3Е. Таким образом, если отрезки пересекаются, то процедура Ану-Бегяьйемтз1нтекзест возвращает значение ткг3е. Как мы уже убедились, если процедура Аму-Бесменте-1нтекзест возвращает значение ткие, отрезки пересекаются. Поэтому рассматриваемая процедура всегда выдает правильный ответ. зЕсли позвоюпь трем отрезкам пересекаться в гжной точке, появитсв возможность сугпеспювания промежуточного стрелю с, пересекающею отрезки а и Ь в точке р.
Иначе говоря, для всех выметаюших прямых ю, расположенных слева от точки р, для «огорых а р Ь, могут выполняться иютношения а Ь с н с Ь Ь В упр. Зэд.й предлагается показать, что пропедура хит-Зпп мента-гмтипякСт работает корректно, даже если три отРезка пересекаются в олной и той же точке.
Часть р// //збраиные тЕны /014 Время работы Если множество Я содержит и отрезков, то процедура А/чт-Якомк/чтз- 1/чтпкзпст выполняется за время 0(п 1я п). Выполнение строки 1 занимает время 0(1). Строка 2 с помощью сортировки слиянием или пирамидальной сортировки выполняется за время 0(п !яп). Поскольку всего имеется 2п точек-событий, а цикл Гог в строках 3 — 1! выполняет не более одной итерации на точку, он выполняется не более 2п раз.
На каждую итерацию требуется время 0(1я п), поскольку выполнение каждой операции в красно-черном дереве занимает время 0(!йп), и с помощью метода, описанного в разделе 33.1, каждая проверка пересечения выполняется за время 0(1). Таким образом, полное время работы равно 0(п 1я и). Упражнения зз.гл Покажите, что в множестве, состоящем из п отрезков, может быть 9(пз) пересечений. ЗЗ.2.2 Пусть отрезки а и 6 сравнимы в координате а.
Покажите, как за время 0(1) определить, какое из соотношений выполняется — а >р 6 или 6 1ре а. Предполагается, что вертикальные отрезки отсутствуют. (Указание: если отрезки а и Ь не пересекаются, достаточно просто воспользоваться векторным произведением. Если же зти отрезки пересекаются, что выявляется путем вычисления векторных произведений, то и в этом случае можно ограничиться только операциями сложения, вычитания и умножения и избежать деления. Если отрезки а и 6 пересекаются, достаточно просто вывести сообщение о том, что обнаружено пересечение.) 33.2.3 Профессор предложил модифицировать процедуру А/чт-Бксмп/чтя-1//тккзпст таким образом, чтобы она не прекращала работу после того, как будет обнаружено пересечение, а выводила пересекающиеся отрезки и переходила к выполнению следующей итерации цикла Гог. Профессор назвал полученную в результате процедуру Рк//гт-1нтпкзпст//чс-Бкомк/чтя и заявил, что она выводит все пересечения, следующие слева направо в том порядке, в котором они располагаются в множестве отрезков.
Аспирант утверждает, что профессор ошибается. Кто из них прав? Всегда ли процедура Рк//чт-1мтпкзпст//ча-Бпсмп/чтз будет находить первым крайнее слева пересечение? Будет ли она находить все пересечения? 33.2.4 Разработайте алгоритм, позволяющий за время 0(п 1я п) определить, является лн и-угольник простым. 33.2.5 Разработайте алгоритм, позволяющий за время О(п1яп) определить, пересекаются ли два простых многоугольника, суммарное количество вершин в которых равно и.. 1075 Глаеа ЗЗ. Вычиееитееьиаи геометрии ЗЗ.г.б Круг состоит из окружности и ее внутренней области, и его можно представить с помощью центра и радиуса.
Два круга пересекаются, если у них есть хотя бы одна общяя точка. Приведите алгоритм, позволяющий в течение времени 0(п 1я и) определить, пересекаются ли какие-либо два круга из множества, состоящего из и кругов. 33.2. 7 Пусть задано множество, состоящее из и отрезков, между которыми имеется и пересечений. Покажите, как вывести данные по всем пересечениям за время ОЯп+ (е) 1яп). 33.2.8 Докажите, что процедура Аму-Бесмемтз-1мтедеест работает корректно даже в том случае, если в одной и той же точке пересекается три или более отрезков. 33.2.9 Покажите, что процедура А~г~-Бебмехтя-1хтедзест работает корректно даже в том случае, если в числе ее входных отрезков есть вертикальные (при этом нижние конечные точки вертикальных отрезков обрабатываются как левые конечные точки, а верхние — как правые юнечные точки).