Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 235
Текст из файла (страница 235)
Поворот последовательных отрезков Следующий вопрос заключается в том, куда сворачивают два последовательных отрезка, рор( и р1рз, в точке рь — влево или вправо. Можно привести эквивалентную формулировку этого вопроса — определить знак угла дрор(уз. Векторное произведение позволяет ответить на этот вопрос, не вычисляя величину угла. Как видно из рис.
33.2, мы просто проверяем, находится ли направленный отрезок рорз по часовой стрелке или против часовой стрелки относительно направленного отрезка роры Для этого вычисляется векторное произведение (рз — ро) х (рз — ро), Если эта величина отрицательна, то направленный отрезок рорз находится против часовой стрелки по отношению к направленному отрезку роры так что в точке рз мы делаем поворот влево. Положительное значение векторного произведения указывает на ориентацию по часовой стрелке и поворот вправо. Нулевое векторное произведение означает, что точки ро, рз и рз коллинеарны.
Определение, пересекаются ли два отрезка Чтобы определить, пересекаются ли два отрезка, следует проверить, пресекает ли каждый из них прямую, содержащую другой отрезок. Отрезок рзрз лересекаепв (в(гаЫ!ез) прямую, если конечные точки отрезка рз и рз лежат в разных полу- плоскостях, на которые прямая разбивает плоскость. В граничном случае точка рз или точка рз (или обе эти точки) лежит непосредственно на прямой. Два отрезка Чтобы определить, находится лн направленный отрезок роорт по часовой стрелке от направленного отрезка рорз или против относительно их общей точки ро, достаточно использовать ее как начало координат.
Сначала обозначим величину рз — ро как вектор р( — — (хы у)), где х', = хз — хо и у', = ут — уо, а затем введем аналогичные обозначения для величины рз — ро, После этого вычислим векторное произведение Чаеть ГП. Инбранные темы 1Обе пересекаются тогда и только тогда, когда выполняется одно из сформулированных ниже условий (или оба эти условия одновременно). 1. Каждый отрезок пересекает прямую, на которой лежит другой отрезок. 2. Конечная точка одного из отрезков лежит на другом отрезке (граничный случай). Эта идея реализована в приведенных ниже процедурах. Процедура БЕОМЕ14тз-114ТЕКЕЕСТ возвращает значение ТкиЕ, если отрезки рзрг и рзр4 пересекаются, и значение елсзе — в противном случае.
В этой процедуре вызываются вспомогательные процедуры 01кест1оы и 014-Бесме14т. В первой из них с помощью описанного выше векторного произведения определяется относительное расположение отрезков, а во второй — лежит ли на отрезке точка, если известно, что она коллинеарна этому отрезку. Бесмехтз-114текзест (Р1, Рг, Рз~ Р4) 1 411 = 131КЕСТ!ОН(РЗ,Р4,Р1) 2 4(г = 111кест1014(рз,р4,рг) 3 дз = 131кест1014(Р1 Рг Рз) 4 п4 = 131кест101ч(Р1 Рг Р4) 11 ((11 > 0 и 1(г < О) или (е(1 < 0 и дг > О)) " ((е(з > 0 и д4 < О) или (дз < 0 и 414 > 0)) 6 ге1нгп ткпе 7 е!яе11 п1== 0 и 014-Беоме14т(рз,р4,Р1) 8 гетнгп ТКЕТЕ 9 е!аеЫНг == 0 и Ом-БКОме1чт(рз,р4,рг) 10 гетнгп ткпе !1 е!аеас(з == 0 и Ом-Бесмехт(р1,рг,рз) !2 гетнгп ткни 13 е!ае11 Н4 == 0 и 014-Беаме1чт(р1, рг, р4) 14 гегнгп типе 15 е1яе ге1нгп ЕЛСЗЕ Ецкест10н (р„р,, рь) 1 гетпгп (рь — р) х (р — р) 014-$епме14т(Р„Р,, рь) 1 Ы ппп(х;, х,) < хь < ьпах(х;,х,) и ппп(у;, у ) < уь < гпах(у„ у.) 2 ге1нгп тки е 3 е!зе ге1игп глсзе Процедура БеОме14тз-1нтекзест работает следующим образом.
В строках 1-4 вычисляется относительное расположение д, каждой конечной точки р, относительно другого отрезка. Если все величины, характеризующие относительное расположение, отличны от нуля, то легко определить, пересекаются ли отрезки р1рг и рзр4. Это делается следующим образом. Отрезок р1рг пересекает лрямУю, содеРжашУю отРезок РзР4, если напРавленные отРезки РзР1 и Рзрг имеют !Об5 Глава 35. Вычислительная геометрия (РгРз) (Р Р1 (Р1 Рз! х (Р Р~ Рл Рл „-Р,) х (Рз-р, ) < О 4 Рд х (Рз-Р) ) < О х(рл-Р ) <О (Рз Рд> О (Рз Р)) (Рз Р~) Рз (РГР ~ Рз Озг-Рз) «(Рл Рз) хо (е) (з) Р) Рз (г) (в) противоположные направления относительно рззр4. В этом случае знаки величин ((1 и ((з разные.
Аналогично отрезок рзр4 пересекает прямую, содержащую отрезок р)рз, если знаки величин ((з и ((4 разные. Если проверка в строке 5 успешна, то отрезки пересекаются, и процедура Бесмеытз-1)чтекеест возвращает значение ТКОЕ. Этот случай показан на рис. 33.3,(а). В противном случае отрезки не пересекают прямые друг друга, хотя и возможны граничные случаи. Если ни одна из величин, характеризующих взаимную ориентацию отрезков, не равна нулю, то это не граничный случай. При этом не выполняется ни одно из условий равенства нулю в строках 7-13, и процедура БеОме)чтз-1)чтекзест возвращает в строке ! 5 значение рлезе.
Этот случай проиллюстрирован на рис. 33.3, (б). Граничный случай осуществляется, когда любая относительная ориентация г(ь равна нулю. Это говорит о том, что точка рь коллинеарна с другим отрезком. Данная точка принадлежит другому отрезку тогда и только тогда, когда она находится между его конечными точками. Процедура О)ч-БеОме)чт позволяет определить, расположена ли точка рь между конечными точками другого отрезка р;р . Эта процедура вызывается в строках 7 — 13, и в ней предполагается, что точка рь коллинеарна отрезку р,р . В частях (в) и (г) рис.33.3 проиллюстрирован случай, когда один из отрезков коллинеарен конечной точке другого отрезка.
В части (в) точка рз лежит на отрезке р) рз, так что процедура Б еОме)чтз-1ы те кз ест возвращает в строке 12 значение тк()е. В части (г) точка рз коллинеарна отрезку р)рз, Рис. 333. Частные случаи в процедуре авомннтз-(нтнязнсг. (а) Отрезки рзрз н рзрл пересекают прямые друг друга. Поскольку рзрл пересекает прямую, содержащую р)рз, знаки векторных произведений (рз — рз) х (рз — рз) и (рл — рз) х (рз — р)) различны. Поскольку р)рз пересекает прямую, содержащую рзрл, знаки векторных произведений (рз — рз) х (рл — рз) и (рз — рз) х (рл — рз) рюличны. (6) Отрезок рзрл пересекает прямую, содержащую р) рз, но отрезок р)рз не пересекает прямую, содержащую рзрл. Знаки векторных произведений (рз — рз) х (рл — рз) и (рз — рз) х (рл — рз) одинаковы.
(в) Точка рз коллинеарна отрезку р1 рз и находитсв между рз и рз. (г) Точка рз коллинеарна отрезку рзрз, но не находится между р~ и рз. Отрезки не пересекаются. 10бб Часть Р11. Избранные ыемы но не лежит между его конечными точками. Процедура ЗлОмпнтз-1нтпкзлст возвращает в строке 15 значение гльзл (отрезки не пересекаются). Другие применения векторного произведения В последующих разделах этой главы описаны другие приложения векторного произведения.
В разделе 33.3 ставится задача сортировки множества точек по характеризующему их расположение полярным углам относительно заданного начала координат. В упр. 33.1.3 предлагается показать, что с помощью векторного произведения можно осуществить сравнение в соответствующей процедуре сортировки. В разделе 33.2 с помощью красно-черных деревьев поддерживается упорядочение отрезков по вертикали. Вместо того чтобы явным образом поддерживать ключевые значения, в коде, реализующем красно-черное дерево, их сравнение будет заменено векторным произведением. Это позволит определить, какой из двух отрезков, пересекающих заданную прямую, находится выше другого.
Упражнения 33.1.1 Докажите, что если произведение рз х рз положительно, то переход от вектора рз к вектору р1 относительно начала координат (О, 0) осуществляется по часовой стрелке, а если это векторное произведение отрицательно, то переход осуществляется против часовой стрелки. ЗЗ 1.2 Профессор предположил, что в строке 1 процедуры Он-Бдпмлмт достаточно протестировать только измерение х. Покажите, что профессор ошибается. 33.1.3 Полярным углам (ро1аг алй!е) точки рз относительно начала координат рс называется угол между вектором рз — рс в обычной полярной системе координат. Например, полярный угол точки (3, 5) относительно точки (2,4) — это угол вектора (1, 1), составляющий 45' или к/4 радиан.
Полярный угол точки (3, 3) относительно точки (2, 4) — это угол вектора (1, — 1), составляющий угол 315' илн 7к/4 радиан. Напишите псевдокод, сортирующий последовательность и точек (ры рз,..., р„) по их полярному углу относительно заданной точки рс. Процедура должна выполняться за время 0(п 15п), и сравнение упюв в ней следует выполнять с помощью векторного произведения. 33.1.4 Покажите, как за время 0(пз 15 п) определить, содержатся ли в множестве нз п точек трн коллинеарные точки. 33.1. 5 Многоугольник (ро!убоп) представляет собой кусочно-линейную замкнутую кривую на плоскости. Другими словами, это образованная последовательностью отрезков кривая, начало которой совпадает с ее концом.
Эти отрезки называют- глана 33. Вычислительная геометрии !ОВ7 ся сяеораиами (аЫез) многоугольника. Точка, соединяющая две последовательные стороны, называется вереипиой (еепех) многоугольника. Если многоугольник просяеой (зппр!е), в нем нет самопересечений. (В общем случае предполагается, что мы имеем дело с простыми многоугольниками.) Множество точек плоскости, ограниченное простым многоугольником, образует внутреннюю обласяеь (!пГепог) многоугольника, множество точек, принадлежащих самому многоугольнику, образует его границу (Ьоппдагу), а множество точек, окружаюших многоугольник, образует его внешнюю область (ехгепог).
Простой многоугольник называется выпуклым (сопеех), если отрезок, соединяющий любые две его граничные или внутренние точки, лежит на границе или во внутренней части этого многоугольника. Профессор предложил метод, позволяющий определить, являются ли и точек (ро, рп, .., р„1) последовательными вершинами выпуклого многоугольника.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
