4.8.3. Нахождение отсеченной прямой Определите, какая часть отрезка прямой с концевыми точками (2,4) и (20,8) расположена внутри четырехугольного окна с углами (0,7), (9,9), (14,4) и (2,2).

4.8.4. Отсечение границами произвольных полигонов В предыдущем разделе мы видели, как осуществляется отсечение отрезка прямой границами выпуклого полигона. Расширим эту процедуру до метода отсечения отрезка границами любого полигона.

Френсис Хилл

Рис. 4.45. Когда луч находится внутри произвольного полигона Р?

Основная задача состоит в том, чтобы найти, когда луч A+ct расположен внутри полигона Р, заданного списком вершин Р0, Р,,..., PN_V Пример приведен на рис. 4.45.

Ясно, что в общем случае луч может входить в полигон Р и выходить из него много раз и что результат отсечения отрезка границами Р может привести не к одному отрезку, а к целому списку отрезков. Кроме того, полигон Р более не описывается набором бесконечных ограничивающих прямых в точечной нормальной форме; мы вынуждены работать с ЛГ-конечными отрезками типа Р3Р4, из которых формируются его ребра.

Данная задача близка к той, с которой мы уже имели дело в разделе «Пересечения прямых с плоскостями; отсечение»: нахождение пересечения двух отрезков прямой. Теперь мы пересекаем один отрезок прямой последовательностью отрезков прямой, связанных с полигоном Р.

Мы будем представлять каждое ребро Р параметрически (а не в точечной нормальной форме). Например, ребро Р3Р4 представляется в виде: Р3+ е3ы, где е3 = Р4 - Р3 - вектор ребра (edge vector), связанный с вершиной Р3. В общем случае г'-е ребро задается в виде Р.+ ей, где и изменяется в интервале [0,1]; i - 0,1 1; а вектор е, - Р.+, - Р(, причем, как всегда, PN отождествляется с Р0.

Напомним из раздела «Пересечения прямых с плоскостями; отсечение», что луч A + ct пересекает i-e ребро, когда t и и имеют значения, удовлетворяющие равенству А + сг = Р( + ем. Вводя вектор Ь. -Р.-А, ищем решение следующего уравнения относительно (им: сг = Ь; + е(м.

4.8. Задачи о пересечениях многоугольников


⇐ Предыдущая| |Следующая ⇒