КГ Лекция 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

Рассмотрим следующий случай:

Если в результате вычислений получаются значения параметра t, выходящие за пределы интервала 0 <= t <= 1, то такие решения отвергаются, так как они соответствуют точкам, лежащим вне рассматриваемого отрезка. Естественной является попытка определения видимости отрезка на основе анализа получаемых значений параметра t.

В данном случае будем иметь:

• t < 0 – для верхней и левой границ.
• t > 1 – для нижней и правой границ.

Таким образом, для полностью видимого отрезка каждой точке пересечения соответствует недопустимое значение параметра.

Рассмотрим иной случай:

Так, для полностью видимого отрезка точки пересечения лежат за пределами отрезка, поэтому значения параметра t будут лежать за пределами допустимого интервал. Данный факт можно было бы рассматривать в качестве критерия определения видимых отрезков. Однако рассмотрение полностью невидимого отрезка показывает, что и для такого отрезка значения параметра t, соответствующие точкам пересечения со сторонами отсекателя, также лежат за пределами допустимого интервала. Таким образом, не удается получить простой критерий, используя который легко было бы идентифицировать полностью видимые и полностью невидимые отрезки. Поэтому требуется специальный метод отсечения параметрически заданных отрезков выпуклым отсекателем.

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

Пусть в качестве окна отсечения используется выпуклая область C, которая может быть любым плоским выпуклым многоугольником. Тогда, внутренняя нормаль nв , в произвольной точке a, лежащей на любой границе C, удовлетворяет следующему условию: nв (b - a) >= 0 , где b - любая другая точка на границе отсекающей области.

Угол alpha между внутренней нормалью nв к точке A и вектором, проведенным из данной точки к любой другой, расположенной на границе отсекающей области, всегда находится внутри интервала: -pi/2 <= alpha <= pi/2. Таким образом, косинус угла alpha всегда положителен, а, следовательно, положительно и скалярное произведение этих векторов. В свою очередь, угол между внешней нормалью nвш и любым из подобных векторов равен (pi - alpha), косинус которого всегда отрицателен.

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

P(t) = P1 + (P2 - P1) * t 

где t - параметр; при наложении ограничений на t: 0 <= t <= 1, получим именно отрезок, а не бесконечную прямую.

nв[P(t) - f] - скалярное произведение вектора.

Далее предположим, что f - граничная точка выпуклой области С, а nв - внутренняя нормаль к одному из ограничивающих эту область ребер. Тогда для любой точки отрезка AB, то есть для любого значения параметра t:

• из условия nв[P(t) - f] < 0 следует, что вектор [P(t) - f] направлен из области C;
• из условия nв[P(t) - f] = 0 следует, что вектор [P(t) - f] принадлежит плоскости, которая проходит через граничную точку k и перпендикулярна нормали nв ;
• из условия nв[P(t) - f] > 0 следует, что вектор [P(t) - f] направлен внутрь C

Рассмотрим ребро C_1 C_2: Построим внутреннюю нормаль N_i к рассматриваемой стороне из произвольной её точки:

В качестве второго вектора построим вектор, начинающийся в произвольной точке рассматриваемого ребра и заканчивающийся в заданной точке:

Из всех этих условий следует, что прямая пересекает замкнутую выпуклую область C ( выпуклый многоугольник в нашем двумерном случае) равно в двух точках.

• Если эти две точки не принадлежат одной граничной плоскости или ребру, тогда уравнение nв[ C(t) - f] = 0 имеет только одно решение.
• Если точка f лежит на той граничной плоскости или на том ребре, для которых nв является внутренней нормалью , то точка на отрезке P(t) , которая удовлетворяет уравнению nв [ P(t) - f] = 0, будет точкой пересечения этого отрезка с ребром окна отсечения.

Таким образом, скалярное произведение внутренней нормали к i-му ребру окна отсечения на вектор, начинающийся в точке, лежащей на i - ом ребре окна отсечения, и заканчивающийся в любой точке исследуемого отрезка, т.е. nвi [P(t) - fi], где i = 1,2,3, ..m; m - число сторон окна отсечения будет положительно, равно нулю или отрицательно, в зависимости от того, будет ли исследуемая точка лежать внутри окна отсечения, на границе окна или вне его.

Подставив параметрическое представление отрезка в соотношение скалярного произведения, получим уравнение для определения точки пересечения отрезка с ребром полигонального выпуклого окна отсечения:

nвi  [ P1 + (P2-P1) t - fi] =0,

которое приведем к виду:

nвi [P1 - fi] + nвi [P2-P1] t  = 0.                                                  

Обозначим вектор ориентации как D = P2-P1(вектор является вектором направления отрезка, директриса), а для второго вектора введем некоторый коэффициент Wi= P1- fi.

С учетом последних обозначений уравнение (3.6.6) можно записать в следующем виде:

t(Nвi D) + Wi Nвi = 0 

t = -( Wi  Nвi) / (D Nвi) , D != 0, i=1,2..m . 

В данном выражении знаменатель может равняться нулю. Это происходит в следующих частных случаях:

• D = 0 – отрезок вырожденный, то есть когда P2 = P1
• Векторы перпендикулярны. Это означает, что отрезок расположен параллельно рассматриваемой границе отсекателя. В данном случае нас интересует вопрос, по какую сторону от текущей границы отсекателя он расположен: по видимую или по невидимую. При этом стоит отметить тот факт, что, если отрезок полностью невидим для одной стороны отсекателя, то он является полностью невидимым для всего отсекателя, так как чтобы быть полностью или частично видимым отрезком, он должен быть видим относительно каждой границы отсекателя. В ином случае отрезок точек пересечения с текущей границей не имеет и целесообразно перейти к поиску пересечения со следующей границей отсекателя.

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

Знак скалярного произведения, стоящего в числителе, Wi Nвi позволяет определить положение первой вершины отрезка относительно границы отсекателя и, следовательно, положение всего отрезка.

Обозначим скалярные произведения в числителе и знаменателе следующим образом: W_ск и D_ск

Если W_ск ≥ 0, то отрезок является видимым для текущей рассматриваемой стороны отсекателя. Если же W_ск < 0, отрезок является полностью невидимым.

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

1. Ввод координат концевых точек отрезка P1(P1.x, P1.y) , P2(P2.x, P2.y)
2. Ввод числа сторон m выпуклого многоугольника - окна отсечения и координат его вершин (массив C).
3. Вычисление вектора ориентации отрезка D = S2 - S1.
4. Инициализация пределов значений параметра t при условии, что отрезок полностью видимый, то есть tн = 0, tв = 1.
5. Начало цикла по всем сторонам отсекающего окна (i = 1..m). Выполнение для каждой i-ой стороны окна следующих действий:
   • 5.1. Вычисление вектора внутренней нормали к очередной i-ой стороне окна отсечения - nвi
   • 5.2. Определение граничной точки fi каждой стороны отсекающего окна (точки, лежащей на i-ой стороне окна).
   • 5.3. Вычисление вектора Wi = P1 - fi .
   • 5.4 Вычисление скалярного произведения векторов Wск i= Wi nвi .
   • 5.5 .Вычисление скалярного произведения векторов Dск i= Dnвi .
   • 5.6. Проверка на равенство нулю скалярного произведения Dск (вырождение отрезка в точку или его параллельность стороне отсекателя). Если Dnвi = =0 , тогда переход к пункту 5.9 .
   • 5.7. Вычисление параметра t: t = - ( Wскi / Dскi) (отрезок не вырожден в точку и не параллелен стороне отсекателя).
   • 5.8. Определение верхнего и нижнего пределов параметра t :
   • 5.8.1. Поиск нижней границы параметра t, если Dскi > 0 : если t>1, то переход к п.7 (отрезок невидим, т.к. нижний предел параметра t превышает единицу и пересечение с отсекателем имеет место не для самого отрезка, а для его продолжения за вершину P2.; если t1, то tн = max ( t, tн ) (выбор максимального значения из текущего значения параметра t и ранее вычисленного значения нижней границы параметра).
   • 5.8.2. Поиск верхней границы параметра t, если Dскi < 0 : если t<0, топереход к п.7 (отрезок невидим, т.к. верхний предел параметра t отрицателен и пересечение с отсекателем имеет место не для самого отрезка, а для его продолжения за вершину P1.; если t0, то tв = min ( t, tв ) (выбор минимального значения из текущего значения параметра t и ранее вычисленного значения верхней границы параметра).
   • 5.9. Проверка видимости точки, в которую выродился отрезок, или проверка видимости произвольной точки отрезка в случае его параллельности стороне отсекателя: если Wскi < 0, то отрезок (точка) невидим и переход к п. 7; если Wскi >0, то отрезок (точка) видим относительно текущей стороне отсекателя и переход к п. 5.10.
   • 5.10. Конец цикла по сторонам отсекателя.
6. Проверка фактической видимости отсеченного отрезка. Если tн > tв, то переход к пункту 7 , иначе визуализация отрезка в интервале от P(tн) до P(tв).
7. Конец алгоритма.