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

Для создания надежного алгоритма отсечения необходим хороший метод определения местоположения относительно окна (внутри, на границе, вне его) точки, принадлежащей отрезку. Для этой цели в алгоритме Кирусаг-Бека используется вектор нормали (рис.13).

Возьмем выпуклую отсекающую область R. Доказано, что внутренняя нормаль п в произвольной точке а, лежащей на границе ft, удовлетворяет условию:

n(b-a)> =0, (3)

где b — любая точка на границе R, т.к. cos 0 всегда положителен.

Возвращаясь к определению пересечения отрезка Со стороной окна, вновь возьмем параметрическое представление отрезка Р1Р2 уравнением (1). Если f - граничная точка выпуклой области R, а n - внутренняя нормаль к одной из ограничивающих эту область плоскостей, то для любой конкретной величины t, т.е. для любой точки отрезка Р1Р2, из условия n(P(t)-f)< 0 следует, что вектор P(t)-f направлен вовне области R. Из условия n(P(t)-f)< 0 следует, что вектор P{t)-f принадлежит плоскости, которая проходит через f и перпендикулярна нормали. Из условия n(Р(t)-f)> 0 следует, что вектор направлен внутрь R. Из всех этих условий, взятых вместе, следует, что бесконечная прямая пересекает замкнутую выпуклую область в двух точках. Далее, пусть эти две точки не принадлежат одной граничной плоскости или ребру. Тогда уравнениеn(P(t)-f)=0 имеет только одно решение. Если точка f лежит на той граничной плоскости или ребре, для которых п является внутренней нормалью, то точка на отрезке P(t) будет точка пересечения этого отрезка с указанной граничной плоскостью.

Таким образом запишем формализованный алгоритм Кируса-Бека:

Решение уравнения будет положительно, равно нулю или отрицательно - в зависимости от того, будет ли избранная точка отрезка лежать с внутренней стороны границы, на самой границе или с ее внешней стороны. Подстановка (4) в (5) дает условие пересечения отрезка с границей области:

Вектор (Р2-Р1) определяет ориентацию отрезка, а вектор (P1-f1) пропорционален расстоянию от первого конца отрезка до избранной граничной точки. Обозначим через D=P2-P1 директрису или ориентацию отрезка, а через W1=P2-P1 - некий весовой множитель. Тогда получаем уравнение:

Если W, *n, < 0, то эта точка вне окна. Если W, *n, =0, то эта точка на границе. Если W, *n, > 0, то эта точка внутри окна. Последнее уравнение используется для получения значений t соответствующих пересечениям отрезка с каждой стороной окна. Если значение t лежит за пределом интервала 0 < =t< = 1, то оно игнорируется.