Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 215
Текст из файла (страница 215)
В современных инженерных и математических расчетах вычислительная геометрия, в числе других областей знаний, применяется в машинной графике, в робототехнике, при разработке СВИС, при автоматизированном проектировании и в статистике. Роль входных данных в задачах вычислительной геометрии обычно играет описание множества таких геометрических объектов, как точки, отрезки нли вершины многоугольника в порядке обхода против часовой стрелки. На выходе часто дается ответ на такие запросы об этих объектах, как наличие пересекающихся линий. Могут также выводиться параметры новых геометрических объектов, например, выпуклой оболочки множества точек (это минимальный выпуклый многоугольник, содержащий данное множество).
В этой главе мы ознакомимся с несколькими алгоритмами вычислительной геометрии в двух измерениях, т.е. на плоскости. Каждый входной объект представлен множеством точек (ры рз,...), где каждая точка р, = (х;, у;) образована парой действительных чисел х;, у; Е Н.. Например, и-угольник Р представлен последовательностью вершин (ро, ры..., р„1) в порядке обхода границы многоугольника. Вычислительная геометрия может работать в трех измерениях, и даже в большем их числе, но визуализация подобных задач и их решений может оказаться очень трудной. Однако даже в двух измерениях можно ознакомиться с хорошими примерами применения методов вычислительной геометрии.
В разделе 33.1 показано, как быстро и точно ответить на такие основные вопросы о расположении отрезков: если два отрезка имеют общую конечную точку, то как следует перемещаться при переходе от одного из ннх к другому — по часовой стрелке или против часовой стрелки, в каком направлении следует сво- Часть ЧП. Избранные темы 1048 рачивать при переходе от одного такого отрезка к другому, а также пересекаются ли два отрезка.
В разделе 33.2 представлен метод, известный под названием "выметание", или "метод движущейся прямой". Он используется при разработке алгоритма со временем работы 0 (и 18 и), определяющего, имеются ли пересечения среди и отрезков. В разделе 33.3 приведены два алгоритма "выметания по кругу", предназначенные для вычисления выпуклой оболочки множества п точек (наименьшего содержащего их выпуклого многоугольника): сканирование по Грэхему (бгаЬаш'з зсап), время работы которого равно 0(п18п), и обход по Джарвису (1агч1з'з шагсЬ), время выполнения которого равно 0 (пп), где Ь вЂ” количество вершин в оболочке.
Наконец, в разделе 33.4 приводится алгоритм декомпозиции со временем работы 0(п18п), предназначенный для поиска пары ближайших точек в заданном на плоскости множестве из и точек. 33.1 Свойства отрезков В некоторых представленных в этой главе алгоритмах требуется ответить на вопросы о свойствах отрезков. Выпуклой комбинацией (сопчех сошЬ(пайоп) двух различных точек рз = (хмуг) и рз = (хз, уз) называется любая точка рз = = (хз, уз), такая что для некоторого значения а, принадлежащего интервалу 0 < < а < 1, выполняются равенства хз = ахз + (1 — а) хз и Уз = ау~ + (1 — с~) Уз.
Также пишут, что рз = арз + (1 — а) рз. Интуитивно понятно, что в роли рз может выступать любая точка, которая принадлежит прямой, соединяющей точки рз и рз, и находится между этими точками. Если заданы две различные точки рз н рз, то отрезкам прямой (йле зейтеп1) р~р~ называется множество выпуклых комбинаций рз и рз. Точки р~ и рз называются конечными точками (епоро(п1з) отрезка рзрз.
Иногда играет роль порядок следования точек рз и рз, и тогда говорят о направленном отрезке (о1гес1еб зейшеш) рзрз. Если точка рз совпадает с началом координат (ог181п), т.е. имеет координаты (0,0), то направленный отрезок рзрг можно рассматривать как вектор (чес1ог) рз. В этом разделе исследуются перечисленные ниже вопросы. 1. Если заданы два направленных отрезка рор~ и рорз, то находится ли отрезок рорз в направлении по часовой стрелке от отрезка рорз относительно их общей точки ро? 2.
Если заданы два направленных отрезка рорз и р~р~, то в какую сторону следует свернуть в точке рз при переходе от отрезка рорз к отрезку р~рз? 3. Пересекаются ли отрезки рррр и рзр4? На рассматриваемые точки не накладывается никаких ограничений. На каждый из этих вопросов можно ответить в течение времени 0(1), что не должно вызывать удивления, поскольку объем входных данных, которыми выражается каждый из этих вопросов, равен 0 (1). Кроме того, в наших методах Глава 33. Вычислительная геометрия 1049 используются только операции сложения, вычитания, умножения и сравнения.
Не понадобится ни деление, ни вычисление тригонометрических функций, а ведь обе эти операции могут оказаться дорогостоящими и приводить к проблемам, связанным с ошибками округления. Например, метод "в лоб" при определении того, пересекаются ли два отрезка, — найти для каждого из них уравнение прямой в виде у = тх+ Ь (где гп — угловой коэффициент, а Ь вЂ” координата пересечения с осью у), вычислить точку пересечения этих прямых и проверить, принвдпежит ли эта точка обоим отрезкам.
В таком методе при вычислении координат точки пересечения используется деление. Если отрезки почти параллельны, этот метод очень чувствителен к точности операции деления на реальных компьютерах. Изложенный в данном разделе метод, в котором удается избежать операции деления, намного точнее. Векторное произведение Вычисление векторного произведения составляет основу методов работы с отрезками. Рассмотрим векторы рг и рз, показанные на рис. 33.1а. Векторное произведение (егозя ргодис1) рг х рз можно интерпретировать как значение (со знаком) площади параллелограмма, образованного точками (О, 0), рг, рз и рг + рз = = (хг+ хз, у1 + уз).
Эквивалентное, но более полезное определение векторного произведения — определитель матрицы: 1. 1 х1 хз 1 р1 х рг = г1е1 = хгуз — хзуг = -рз х р1. ~, Уг Уг ) Если величина р1 х рз положительна, то вектор рг находится по часовой стрелке от вектора рз относительно начала координат (О, 0); если же векторное произведение отрицательно, то вектор р1 находится в направлении против часовой стрелки от вектора рз.
(См. упражнение 33.1-1.) На рис. 33.1б показаны области, расположенные по и против часовой стрелки относительно вектора р. Граничный случай возникает, когда векторное произведение равно нулю. В этом случае векторы коллинеарны (со11шеаг), т.е. они направлены в одном и том же или в противоположных направлениях. Чтобы определить, находится ли направленный отрезок рор1 по часовой стрелке от направленного отрезка рорз относительно их общей точки ро, достаточно использовать ее как начало координат. Сначала обозначим величину р1 — ро как вектор рг — — (х1, уг), где хг — — х1 — хо и у1 — — уг — уо, и введем аналогичные 'Фактически векторное произведение — трекмернал концепция.
Это вектор, перпендикулярный обоим векторам рг и рз, направление которого определяется "правилом правой руки", а величина равна 1хгрз — хзрг (. Однако в этой главе удобнее трактовать векторное произведение как величину Х1Д2 — Х2Р1. Часть П. Избранные темы 1050 Рис. 33.1. Геометрический смысл векторного произведения обозначения для величины рз — р).
Затем вычислим векторное произведение (Р) — Ро) х (Рз — Ро) = (ж) ко) (Уз Уо) (кз зо) (У) — Уо) ° Если это векторное произведение положительно, то переход от направленного отРезка Рор) к отРезкУ Рорз осУществлЯетсЯ пРотив часовой стРелки; в пРотивном случае он осуществляется по часовой стрелке. Поворот последовательных отрезков Рт Против часовой стрелки По часовой стрелке Ро а) Ро б) Рис. 33.2. Использование векторного произведения ллл определе- ния направления поворота последовательных отрезков Следующий вопрос заключается в том, куда сворачивают два последовательных отРезка Рор) и Р)рз в точке Р) — влево или впРаво.
Можно пРивести эквивалентную формулировку этого вопроса — определить знак угла дрор)рз. Векторное произведение позволяет ответить на этот вопрос, не вычисляя величину угла. Как видно из рис. 33.2, производится проверка, находится ли направленный отрезок Рорз по часовой стрелке или против часовой стрелки относительно направленного отрезка Рор).
Для этого вычисляется векторное произведение (Рг — ро) )е (р) — ро) Если эта величина отрицательная, то переход от направленного отрезка роор) к на- пРавленномУ отРезкУ Рорз осУществлаетсЯ пРотив часовой стРелки, и в точке р) образуется левый поворот. Положительное значение векторного произведения указывает на ориентацию по часовой стрелке и на правый поворот. Обе эти ситуа- Глава 33. Вычислительная геометрия 1051 ции проиллюстрированы на рис. 33.2. В части а показан случай, соответствующий левому повороту, а в части б — случай, соответствующий правому повороту. Нулевое векторное произведение означает, что точки ро, р1 и рз коллинеарны.
Определение того, пересекаются ли два отрезка Чтобы определить, пересекаются ли два отрезка, следует проверить, пресекает ли каждый из них прямую, содержащую другой отрезок. Отрезок р1рз лересекаегл (з1гайПез) прямую, если конечные точки отрезка принадлежат разным полуплоскостям, на которые прямая разбивает плоскость. В граничном случае точка р1 или точка рз (или обе эти точки) лежит на прямой. Два отрезка пересекаются тогда и только тогда, когда выполняется одно из сформулированных ниже условий (нли оба эти условия). 1. Каждый отрезок пересекает прямую, на которой лежит другой отрезок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
