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