КГ Лекция 11. Отсечение отрезка. Определение выпуклости. Алгоритм Кируса Бека.

Алгоритм Кируса-Бека

В трех уже рассмотренных алгоритмах отсечения отрезков предполагалось, что отсекатель является прямоугольником со сторонами, параллельными осям координат. Однако, очень часто оно повернуто относительно координатной сетки или не является прямоугольным. Поэтому Кирус и Бек предложили алгоритм отсечения окном произвольной выпуклой формы. В этом алгоритме для определения местоположения точки относительно окна отсечения используется вектор нормали и параметрическая форма задания отрезка. Параметрическое уравнение отрезка P1P2 имеет вид:

P(t) = P1 + (P2 - P1)*t; 0 <= t <= 1, где t - параметр

Если ограничить t, то таким образом получается именно отрезок, а не бесконечная прямая. Фактически это уравнение является векторным, оно сводится к двум одномерным параметрическим уравнениям следующего вида:

P.x(t) = P1.x + (P2.x - P1.x)*t
P.y(t) = P1.y + (P2.y - P1.y)*t

Для прямоугольного окна со сторонами, параллельными осям координат, точки пересечения отрезков с его границами определяются достаточно просто, поскольку одна из координат точки пересечения заранее известна и остается вычислить только вторую координату из:

t = (P(t) - P1) / (P2 - P1)

Значения параметра t для точек пересечения отрезка с границами отсекателя определяются из следующих соотношений:

     Xл - P1.x
t = -----------   (для левой границы)
    P2.x - P1.x

     Xп - P1.x
t = -----------   (для правой границы)
    P2.x - P1.x

     Yн - P1.y
t = -----------   (для нижней границы)
    P2.y - P1.y

     Yв - P1.y
t = -----------   (для верхней границы)
    P2.y - P1.y