Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 236
Текст из файла (страница 236)
Предложенный алгоритм выводит положительный ответ, если в множестве (~р;р;~1рььз . 1 = О, 1,..., п — Ц, где увеличение индексов выполняется по модулю и, не содержатся одновременно н левые, и правые повороты. В противном случае выводится отрицательный ответ. Покажите, что несмотря на то, что время работы этой процедуры выражается линейной функцией, она не всегда дает правильный ответ. Модифицируйте предложенный профессором метод, чтобы он всегда давал правильный ответ за линейное время. 33.1.
б Пусть задана точка ро = (хс, уо). Правым горпзонтеьзьным лучом (пя)п Ьопхоп!а! гау) из точки ро называется множество точек (р; = (х;, у;): х, > хо и у; = уо), т.е. множество точек, расположенных строго справа от точки ро, вместе с самой этой точкой. Покажите, как за время О(1) определить, пересекает ли данный правый горизонтальный луч из точки рс отрезок р1рз. Сведите эту задачу к другой, в которой определяется, пересекаются ли два отрезка. 33.1. 7 Один из способов определения, находится ли заданная точка рс во внутренней области простого, но не обязательного выпуклого многоугольника Р, заключается в следующем. Из точки рс проводится произвольный луч и определяется, сколько раз он пересекает границу многоугольника Р. Если количество пересечений нечетно и сама точка ро не лежит на границе многоугольника Р, то она лежит во внутренней его части. Покажите, как в течение времени 9(п) определить, находится ли точка ро во внутренней части и-угольника Р.
(Указаниес воспользуйтесь результатами упр. 33.1.6. Убедитесь в правильности этого алгоритма в том случае, когда луч пересекает границу многоугольника в его вершине и если луч перекрывается его стороной.) 33.1.8 Покажите, как за время ез(п) найти площадь простого, но не обязательно выпуклого п-угольника. (Определения, которые относятся к многоугольникам, можно найти в упр. 33.1.5.) /Оба Часть Л!. Избранные темы 33.2. Определение наличия пересекающихся отрезков В этом разделе представлен алгоритм для определения, пересекаются ли какие-нибудь два из отрезков некоторого множества. В этом алгоритме используется метод, известный под названием "выметание", который часто встречается в алгоритмах вычислительной геометрии. Кроме того, как показано в упражнениях, приведенных в конце этого раздела, с помощью данного алгоритма или его вариации можно решать и другие задачи вычислительной геометрии.
Время работы этого алгоритма равно О(п 1я и), где и — количество заданных отрезков. В нем лишь определяется, существуют пересечения или нет, но не выводятся данные обо всех этих пересечениях. (Согласно результатам упр. 33.2.1 для поиска всех пересечений в множестве, состоящем нз п отрезков, в наихудшем случае понадобится время ()(пз).) В методе вымелеииия (зееер)пй) по заданному множеству геометрических объектов проводится воображаемая вертикальная вымелеаюецая прямая (зюеер йпе), которая обычно движется слева направо. Измерение, вдоль которого двигается выметающая прямая (в данном случае это измерение я), трактуется как время. Выметание предоставляет способ упорядочения геометрических объектов, обычно путем размещения их параметров в динамической структуре данных, что позволяет воспользоваться взаимоотношениями между этими объектами. В приведенном в этом разделе алгоритме, устанавливаюшем наличие пересечений отрезков, рассматриваются все конечные точки отрезков в порядке их расположения слева направо, н для каждой новой конечной точки проверяется наличие пересечений.
Чтобы описать алгоритм и доказать его способность корректно определить, пересекаются ли какие-либо из и отрезков, сделаем два упрощаюших предположения. Предположим, во-первых, что ни один из входных отрезков не является вертикальным, и во-вторых — что никакие три входных отрезка не пересекаются в одной точке. В упр. 33.2.8 и 33.2.9 предлагается показать, что алгоритм достаточно надежен для того, чтобы после небольших изменений работать даже в тех случаях, когда сделанные предположения не выполняются.
Часто оказывается, что отказ от подобных упрошений и учет граничных условий становится самым сложным этапом программирования алгоритмов вычислительной геометрии и доказательства их корректности. Упорядочение отрезков Поскольку предполагается, что вертикальные отрезки отсутствуют, каждый входной отрезок пересекает данную вертикальную выметающую прямую в одной точке. Таким образом, отрезки, пересекающие вертикальную выметающую прямую, можно упорядочить по координате у точки пересечения. Чтобы быть более точными, рассмотрим два отрезка, а1 и аз.
Говорят, что они сравнимы (согпрагаЫе) в координате х, если вертикальная выметаюшая прямая с координатой х пересекает оба этих отрезка. Говорят также, что отрезок а1 расположен илд (аЬоче) отрезком аз в х (записываегся а1 ~, аз), если отрезки аз ГВ69 Глава 33. Вычислительная геометрия г г и (л) (о) Рис. Ззлй Упорядочение отрезков с помощью рюньпс вертикальных выметающих прямых.
(а) Здесь а «, с, а «ч Ь, Ь Мч с, а Ь«п с н Ь «с. Отрезок д не сравним ни с одним из показанных отрезков. (6) Когда отрезки е и 3 пересекаются, их порядок становится обратным: е «„3, но 3 «е. Для любой выметающей прямой (такой, как л), которая проходит по заштрихованной области, отрезки е и 3 являются последовательными при упорядочении отношением «,. и яз сравнимы в координате х и точка пересечения отрезка а) с выметающей прямой в координате х находится выше, чем точка пересечения отрезка яз с этой выметаюшей прямой, или если л) и яз пересекаются на выметаюшей прямой.
Например, в ситуации, проиллюстрированной на рис. 33.4,(а), выполняются соотношения а )р„с, а «) Ь, Ь «) с, а )р, с и Ь «„с. Отрезок д не сравним ни с каким другим отрезы)м. Для произвольной заданной координаты х отношение '"« " полностью упорядочивает (см. раздел Б.2) отрезки, пересекающие выметающую прямую в координате х. Иначе говоря, это отношение транзитивно, и если каждый из отрезков я) и яз пересекает выметающую прямую в х, то справедливо либо отношение л) «, язл либо отношение яз «я), либо они оба (если а) и яз пересекаются на выметающей прямой). (Отношение «, является также рефлексивным, но ни симметричным, ни антисиммстричным.) Однако общий порядок может отличаться для разных значений х по мере входа отрезков в число сравнимых и выхода из него.
Отрезок попадает в число сравнимых, когда выметающая прямая проходит его левую конечную точку, и выходит из него, когда выметаюшая прямая проходит его правую конечную точку. Что происходит, когда выметающая прямая проходит через точку пересечения двух отрезков? Как видно из рис. 33.4, (б), в общем упорядочении меняется порядок этих отрезков.
В показанной на рисунке ситуации выметаюшие прямые и и )о находятся соответственно слева и справа от точки пересечения отрезков е и 3, и справедливы соотношения е «„( и 3' «м е. В силу предположения о том, что никакие три отрезка не пересекаются в одной и той же точке, должна существовать некоторая вертикальная выметающая прямая х, для которой пересекающиеся отрезки е и ( явлнются последовательными (т.е. между ними нет других отрезков) в полном упорядочении отношением «,. Для любой выметающей прямой, проходящей через затененную область на рис. 33.4,(б), например для прямой л, отрезки е и ( являются последовательными в общем упорядочении. Перемещение выметаюшей прямой В выметающих алгоритмах обычно обрабатываются два набора данных. 1070 Часть Л!.
Избранные теми 1. Состояние относительно аыметаюи1ей нрамой (вччеер-йпе вШШв) описыва- ет соотношения между объектами, пересекаемыми выметающей прямой. 2. Таблица, нли расписание, точек-событий (ечепырошг зспейп)е) — это последовательность координат х, упорядоченных слева направо, в которой определяются точки останова выметающей прямой.
Каждая такая точка останова называется точкой-событием (ечепг роше). По мере перемещения выметающей прямой слева направо, когда она достигает х-координаты точки-события, выметанне приостанавливается„выполняется обработка точки-события, после чего выметание продолжается. Изменение состояния относительно выметающей прямой происходит только в точках-событиях. В некоторых алгоритмах (например, в том, который предлагается разработать в упр.
33.2.7) таблица точек-событий строится динамически, в ходе работы алгоритма. Однако в алгоритме, о котором сейчас пойдет речь, точки-события определяются статически, исходя исключительно из простых свойств входных данных. В частности, в роли точки-события выступает каждая конечная точка отрезка. Конечные точки отрезков сортируются в порядке возрастания координат х (т.е.
слева направо). (Если две или более точек ковертикальны (сочегг(са1), т.е, их координаты х совпадают, этот узел можно "разрубить", поместив все ковертикальные левые конечные точки перед ковертнкальными правыми конечными точками. Если в множестве ковертикальных левых точек есть несколько левых, первыми среди них будут те, которые имеют меньшее значение координаты у, и то же самое выполняется в множестве ковертикальных правых конечных точек.) Отрезок помещается в набор состояний относительно выметающей прямой, когда пересекается его левая конечная точка; этот отрезок удаляется из набора состояний относительно выметающей прямой, когда пересекается его правая конечная точка. Если два отрезка впервые становятся последовательными в полном упорядочении, выполняется проверка, пересекаются ли они.
Состояние относительно выметающей прямой является полностью упорядоченным множеством Т, в котором необходимо реализовать такие операции. 1мзнкт(Т, в): вставка отрезка в в Т. Рц1.ете(Т, в): удаление отрезка в из Т. Авочц(Т, в): возврат отрезка, находящегося непосредственно над отрезком в в Т. Ви.очч(Т, в): возврат отрезка, находящегося непосредственно пол отрезком в в Т. Возможна ситуация, когда отрезки в~ и вз находятся взаимно один над другим в упорядочении Т; такая ситуация может возникнуть, если в~ и вз пересекаются на выметающей прямой, для которой задается упорядочение Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
