Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 216
Текст из файла (страница 216)
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 с помощью красно-черных деревьев поддерживается упорядочение отрезков по вертикали. Вместо того, чтобы явным образом поддерживать ключевые значения, в коде, реализующем красно-черное дерево, их сравнение будет заменено векторным произведением.
Это позволит определить, каюй из двух отрезков, пересекающих заданную прямую, находится над другим. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
