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