Выходная точка пересечения - А + с£оц1. (4.62) Луч находится внутри полигона Р для всех £ из интервала [£ , t ].

Френсис Хилл

Рис. 4.41. Луч А + ст., пересекающий выпуклый полигон

4.8. Задачи о пересечениях многоугольников Отметим, что нахождение rjn и гоц( решает не только задачу пересечения, но и задачу отсечения: если нам известны rin и tml, то мы знаем, какая часть прямой А + ct расположена внутри полигона Р. Обычно задача отсечения ставится так: какая часть отрезка прямой А С для заданных точек Aw. С расположена внутри Р? Исследуем эту задачу подробно.

Задача отсечения На рис. 4.42 показаны некоторые аспекты задачи отсечения. На рис. 4.42, а показан случай, когда обе точки Ли С расположены вне Р, но часть отрезка АС находится внутри Р. Если рассматривать отрезок АС как часть луча, задаваемого выражением Л + ct, где вектор с - С - А, тогда точка Л соответствует точке этого луча в момент времени t - 0, а точка С соответствует точке луча при t = 1. Эти «моменты времени луча» («гау times») отмечены на рисунке. Для того чтобы найти отсеченный отрезок, вычислим г.п и rout только что описанным способом. Отрезок, подвергнутый отсечению, имеет концевые точки А + ct.m и Л + сгои1. На рис. 4.42, б точка С расположена внутри Р, следовательно, значение rout больше единицы. Отсеченный отрезок имеет концевые точки Л + crin и С. На рис. 4.42, в и Л, и С расположены внутри Р, поэтому отсеченный отрезок равен АС.

Френсис Хилл

Рис. 4.42. Отрезок, отсеченный полигоном В общем случае мы вычисляем £п и сравниваем его с нулем. Большая из величин 1п и нуль используется в качестве «времени» для первой концевой точки отсеченного отрезка. Меньшая же из двух величин: единицы и гоц( - используется для нахождения второй концевой точки. Таким образом, концевые точки отсеченного отрезка равны: А' = А + с тах(0, *1п) (4.63)

и С' = С+стт(гои(,1).

Но как вычислять £п и £оц1? Мы должны рассмотреть каждую из ограничивающих полигон Р прямых поочередно и найти, в каком месте луч А + с£ пересекает эту прямую. Мы предполагаем, что каждая ограничивающая прямая записана в точечной нормальной форме в виде пары {В, п}, где В - некоторая точка данной прямой, а п - внешняя нормаль для этой же прямой; это означает, что п указывает направление наружу от полигона. Так как это направление от полигона, проверка по уравнению (4.61) приводит к следующим трем условиям:


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