Алгоритмы - построение и анализ (1021735), страница 216
Текст из файла (страница 216)
Сначала обозначим величину р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. Каждый отрезок пересекает прямую, на которой лежит другой отрезок. 2. Конечная точка одного из отрезков лежит на другом отрезке (граничный случай). Идея метода реализована в приведенных ниже процедурах. Процедура Бе0- ме1чтз 1нтекзест возвращает значение тк0е, если отрезки р1рз и рзр4 пересекаются, и значение КА1.зе в противном случае. В этой процедуре вызываются вспомогательные процедуры Р1кест101ч и Ом Беомемт. В первой из них с помощью описанного выше векторного произведения определяется относительное расположение отрезков, а во второй — лежит ли на отрезке точка, если известно, что она коллинеарна этому отрезку.
БебмЕХтв 1хтекяест1ры Рз, Рз, Р4) 1 д1 Р1КЕСТ10Х(рЗ,Р4,Рз) 2 Нз +- 431кест10х(рз~ р4, рз) 3 оз +- Р1кест10х(р1 рз рз) 4 Н4 +- Р1КЕСТ!ОХ(рм Рз, Р4) 5 Ы((4 >ОисЬз <0) или(41з <Оиг1з>0)) и Коз > 0 и г14 < 0) или (дз < 0 и Н4 > 0)) б Феп гегпгп ТЛЕ 7 е1веИ' Н1 = 0 и 01Ч Бе0ме1ЧТ(рз, р4,Рт) 8 реп ге1пгп ТЛЕ 9 е!веы оз = 0 и Ог4 Беоме1чт(рз,р4,рз) 1О Феп ге1пгп ТЛЕ 11 е1веп дз = 0 и Он Беоме14т(рырз,рз) 12 Феп гегпгп ТЛЕ 13 еьеи п4 = 0 и Ом Беаме1чт(ры рз, р4) 14 Феп ге1пгп ТКОе 15 еие гегпгп ЕА1.ЗЕ Часть ЧП. Избранные темы 1052 Ечкеспох(р„р,, рь) 1 ге4цгп (рь — р;) х (р — р;) Ох Бегмехт(Р' Ргч Рь) 1г щ,п(х,, х ) < хь < щах(х;, ху) и ппп(Ь В) < Уь — "' 2 4Ьеп гегпгп ТЮЕ 3 е1зе гегпгп елгаве Процедура Бесмехтз 1хтекзест работает следующим образом.
В строках 1-4 вычисляется относительное расположение 4 каждой конечной точки р, относительно другого отрезка. Если все величины, характеризующие относительное расположение, отличны от нуля, то легко определить, пересекаются ли отрезки р~р~ и рзр4. Это выполняется следующим образом. Отрезок р1рз пересекает прямую, содержащую отрезок рзр4, если направленные отрезки рзрз и рзрг имеют противоположные направления относительно рзр4. В этом случае знаки величин 411 и Н~ разные.
Аналогично, отрезок рзр4 пересекает прямую, содержащую отрезок р1рз, если знаки величин Нз и Н4 разные. Если проверка в строке 5 подтверждается, то отрезки пересекаются, и процедура БЕбМЕХТ$1ХТЕКЗЕСТ возвращает значение тле. Этот случай показан на рис. 33.3а. В противном случае отрезки не пересекают прямые друг друга, хотя и возможны граничные случаи. Если ни одна из величин, характеризующих взаимную ориентацию отрезков, не равна нулю, то это не граничный случай. При этом не выполняется ни одно из условий иа равенство нулю в строках 7-13, и процедура Бесмехтз 1хтекзест возвращает в строке 15 значение еА1.зе. Этот случай проиллюстрирован на рис. 33.36.
Здесь отрезок рзр4 пересекает прямую, содержащую отрезок р1рз, но отрезок р4рз не пересекает прямую, содержащую отрезок рзр4. При этом знаки векторных произведений (р1 — рз) х (р4 — рз) и (рз — рз) х (р4 — рз) совпадают. Граничный случай возникает, если какая-либо относительная ориентация Нь равна О. Это говорит о том, что точка рь коллинеарна с другим отрезком. Данная точка принадлежит другому отрезку тогда и только тогда, когда она находится между его конечными точками.
Процедура Ох Бесмехт позволяет определить, расположена ли точка рь между конечными точками другого отрезка р;р . Эта процедура вызывается в строках 7-13, и в ней предполагается, что точка рь коллинеарна отрезку р4р . В частях в и г рисунка 33.3 проиллюстрирован случай„ когда один из отрезков коллинеарен с конечной точкой другого отрезка. В части в точка рз коллинеарна с отрезком р1 1рз и находится между его конечными точками.
В этом случае процедура Бесмехтз 1хтекзест возвращает в строке 12 значение ткце. В части г точка рз коллинеарна с отрезком р1рз, но не лежит между его конечными точками. Процедура Бебмехтз 1хтекзест возвращает в строке 15 значение газе (отрезки не пересекаются).
Глава 33. Вычислительная геометрия 1053 (Рз Рз) "(Р Рз (Рз Рз) х(Р4 Р4 Р4 з-р, ) х (Р -р,) < а 4-Р,) х (Рз-Рз) <О х (р4 рз) <а (Рз-Рз) >О Рз (Рз Рз) х (Р4 Рз) > С (Рз-Рз) х (Рз-Рз) > Рз (Рз-Р з Рз 6) а) Р4 Рз Рз в) Рис. 33.3. Частные случаи в процедуре Бвамвнтз 1нтькзвст Другие применения векторного произведения Упражнения 33.1-1. Докажите, что если произведение рз х рз положительно, то переход от вектора рз к вектору рз относительно начала координат (О, 0) осуществляется по часовой стрелке, а если это векторное произведение отрицательно, то переход осуществляется против часовой стрелки. 33.1-2.
Профессор предположил, что в строке 1 процедуры 0)ч Зиамнчт достаточно протестировать только измерение т. Покажите, что профессор ошибается. 33.1-3. Полярным углом (ро!аг апя1е) точки рз относительно начала юординат ро называется угол между вектором рз — рс и полярной осью. Например, В последующих разделах этой главы описаны другие приложения векторного произведения. В разделе 33.3 ставится задача сортировки множества точек по характеризующему их расположение полярным углам относительно заданного начала координат. В упражнении 33.1-3 предлагается показать, что с помощью векторного произведения можно осуществить сравнение в процедуре сортировки. В разделе 33.2 с помощью красно-черных деревьев поддерживается упорядочение отрезков по вертикали.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
