3.6.3. Отсечение произвольного отрезка произвольным выпуклым окном (Алгоритм Кируса - Бека)

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

В этом алгоритме для определения местоположения точки относительно окна отсечения используется вектор нормали и параметрическая форма задания отрезка. Параметрическое уравнение отрезка P₁P₂ имеет вид:

P(t)= P_{1 +} (P₂- P₁)t; 0 t 1, где t - параметр.

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

P_x(t)= P_{1.x +} (P_2.x- P_1.x)t; 0 t 1

P_y(t)= P_{1.y +} (P_2.y- P_1.y)t; 0 t 1 ( 3.6.2)

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

t = (P(t)-P₁)/(P₂ - P₁)

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

t = 0 t 1 (для левой границы)

t = 0 t 1 (для правой границы)

t = 0 t 1 (для нижней границы)

t = 0 t 1 (для верхней границы)

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

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

Пусть в качестве окна отсечения используется выпуклая область C, которая может быть любым плоским выпуклым многоугольником. Тогда, внутренняя нормаль n_в , в произвольной точке A, лежащей на любой границе C, удовлетворяет следующему условию: n_в ( B - A ) 0 , где B - любая другая точка на границе отсекающей области. Правильность условия иллюстрируется на рис. 3.6.8. Угол  между внутренней нормалью n_в к точке A и вектором, проведенным из данной точки к любой другой, расположенной на границе отсекающей области, всегда находится внутри интервала: - /2  /2. Таким образом, косинус угла  всегда положителен, а, следовательно, положительно и скалярное произведение этих векторов. В свою очередь, угол между внешней нормалью n_вш и любым из подобных векторов равен (-), косинус которого всегда отрицателен.

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

P(t) = P₁ + (P₂ - P₁) t , ( 3.6.3)

где t - параметр; при наложении ограничений на t: 0 t 1, получим именно отрезок, а не бесконечную прямую. Далее предположим, что 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 (рис.3.6.9).

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

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

n_вi [P(t) - f_i] , (3.6.4)

где i=1,2,3, ..m; m - число сторон окна отсечения

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

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

n_вi [ P₁ + (P₂-P₁) t - f_i] =0, (3.6.5)

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

n_вi [P₁ - f_i] + n_вi [P₂-P₁] t = 0. (3.6.6)

В уравнении (3.6.6) вектор [P₂-P₁] определяет ориентацию отрезка, а вектор [P₁ - f_i] пропорционален расстоянию от начала отрезка до исследуемой граничной точки. Обозначим вектор ориентации как D = P₂-P₁, а для второго вектора введем некоторый коэффициент Wi= P₁- f_i. С учетом последних обозначений уравнение (3.6.6) можно записать в следующем виде:

t ( n_вi D ) + Wi n_вi = 0 (3.6.7)

Решая уравнение (2.6.7) относительно t, получим:

t = - ( Wi n_вi) /( D n_вi) , D 0, i=1,2..m _. (3.6.8)

Анализируя уравнение (3.6.8), замечаем, что знаменатель D n_вi принимает нулевое значение в двух случаях. Во-первых, в случае вырождения отрезка в точку, то есть когда P2=P1_. Эта точка лежит вне окна отсечения, когда числитель Wi n_вi < 0 , на границе, когда он равен нулю и внутри, когда числитель Wi n_вi >0. Однако этот случай не представляет большого интереса, т.к. нас интересуют отрезки, а не точки. Во-вторых, знаменатель равен нулю, когда равно нулю скалярное произведение D n_вi, т.е. когда отрезок параллелен ребру отсекателя.

Используя уравнение (3.6.8), можно определить значения параметра t, при которых происходят пересечения исследуемого отрезка с ребрами окна отсечения. Если значения t не принадлежат интервалу 0 t  1, то их не рассматривают, поскольку они соответствуют точкам, лежащим вне исходного отрезка. Несмотря на то, что отрезок может пересечь замкнутую выпуклую область не более, чем в двух точках, при решении уравнения (3.6.8) можно получить более двух решений в интервале 0 t 1. Полученные решения следует разбить на две группы: верхнюю и нижнюю, в зависимости от близости найденной точки пересечения к началу или концу отрезка. Чтобы отрезок был видимым относительно всего отсекателя, он должен быть видим относительно всех ребер отсекателя одновременно. Концам видимой части отрезка будут соответствовать два значения параметра t, одно из которых является максимальным значением из нижней группы t_maxmin, а второе - минимальным из верхней группы t_minmax (рис. 3.6.10). Найденное значение параметра t для очередной точки пересечения рассматривают в качестве возможного верхнего предела t_в, если знаменатель Dn_вi < 0; в случае же, когда знаменатель положителен, значение параметра t определяет точку, которую относят к нижней границе видимости t_н.

Алгоритм Кируса - Бека может быть представлен следующим образом:

1. Ввод координат концевых точек отрезка P₁(P_1.x, P_1.y) , P₂(P_2.x, P_2.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. Определение граничной точки f_i каждой стороны отсекающего окна (точки, лежащей на i-ой стороне окна).

5.3. Вычисление вектора Wi = P₁ - f_i .

5.4 Вычисление скалярного произведения векторов W_{ск i}= Wi n_вi .

5.5 .Вычисление скалярного произведения векторов D_{ск i}= Dn_вi .

6. Проверка на равенство нулю скалярного произведения D_ск (вырождение отрезка в точку или его параллельность стороне отсекателя). Если Dn_вi = =0 , тогда переход к пункту 5.9 .

5.7. Вычисление параметра t: t = - ( W_скi / D_скi) (отрезок не вырожден в точку и не параллелен стороне отсекателя).

5.8. Определение верхнего и нижнего пределов параметра t :

1. Поиск нижней границы параметра t, если D_скi > 0 : если t>1, то переход к п.7 (отрезок невидим, т.к. нижний предел параметра t превышает единицу и пересечение с отсекателем имеет место не для самого отрезка, а для его продолжения за вершину P_2.; если t1, то t_н = max ( t, t_н ) (выбор максимального значения из текущего значения параметра t и ранее вычисленного значения нижней границы параметра).

2. Поиск верхней границы параметра t, если D_скi < 0 : если t<0, топереход к п.7 (отрезок невидим, т.к. верхний предел параметра t отрицателен и пересечение с отсекателем имеет место не для самого отрезка, а для его продолжения за вершину P_1.; если 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. Конец алгоритма.

При программной реализации целесообразно скалярные произведения векторов вычислять с помощью отдельной функции.

В заключение, рассмотрим пример отсечения отрезка выпуклым шестиугольником. На рис. 3.6.11 показан шестиугольник P1-P6 , служащий окном отсечения, и отрезок AB, который отсекается данным окном. В таблице 3.1 приведены необходимые вычисления, полученные после работы алгоритма Кируса - Бека. В качестве примера заполнения таблицы, рассмотрим ее строку, соответствующую ребру P5P6. Вектор ориентации D = B - A = [ 3 3 ] - [-1 1 ] = [ 4 2 ]. Внутренняя нормаль n_в к ребру P5P6 равна n_в = [ -1 0 ], тогда D n_в = -4. Для граничной точки k ( 2,3 ) коэффициент W = A - k = [-1 1 ] - [2 3 ] = [ -3 -2 ], a W n_в = 3. Так как D n_в = -4 < 0, то найден верхний предел и tв = -3/ (-4) = 3/4. Из анализа таблицы 1 видно, что максимальное среди нижних значений t - tн =1/4, а минимальное среди верхних t - tв = 3/4 , то есть отрезок AB видим в интервале: 1/4t  3/4 .

Таблица 3.1

Ребро	Нормаль nв	Граничная точка k	Коэффициент W	W nв	D nв	Нижний предел tн	Верхний предел tв
P1P2	[ 1 1 ]	( 1 , 0 )	[ -2 1 ]	-1	6	1/6
P2P3	[ 1 0 ]	( 0 , 2 )	[ -1 -1 ]	-1	4	1/4
P3P4	[ 1 - 1 ]	( 0 , 2 )	[ -1 -1 ]	0	2	0
P4P5	[ 0 -1 ]	( 2 , 3 )	[ -3 -2 ]	2	-2		1
P5P6	[ -1 0 ]	( 2 , 3 )	[ -3 - 2 ]	3	-4		3/4
P6P1	[ 0 1 ]	( 1 , 0 )	[ -2 1 ]	1	2	-1/2

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

3.6.4.ОПРЕДЕЛЕНИЕ ФАКТА ВЫПУКЛОСТИ МНОГОУГОЛЬНИКА.

ВЫЧИСЛЕНИЕ ВНУТРЕННИХ НОРМАЛЕЙ

Алгоритм Кируса - Бека позволяет производить отсечение отрезков произвольным выпуклым окном, поэтому необходимо уметь устанавливать факт выпуклости отсекателя. Существует ряд способов проверки многоугольника на выпуклость. Одним из них является вычисление векторных произведений его смежных сторон (рис.3.6.12). Результирующий вектор, получаемый в результате умножения векторов, перпендикулярен плоскости, в которой лежит рассматриваемый многоугольник. Будем считать, что это произведение имеет положительный знак, если кратчайший поворот для совмещения первого вектора со вторым производится против часовой стрелки. Произведение будет иметь знак минус, если кратчайший поворот первого вектора для совмещения со вторым должен производиться по часовой стрелке.

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

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

Помимо установления факта выпуклости многоугольник алгоритм требует вычисления внутренних нормалей к сторонам отсекателя. Причем достаточно определить направление нормали. Для этого используется свойство скалярного произведения двух перпендикулярных векторов - оно равно нулю. Пусть A_x ,A _y -компоненты вектора A стороны многоугольника (считаются известными), n_x, n_y - искомые компоненты вектора нормали. Тогда можно записать следующее равенство:

nA=( n_xi +n_yj)( A_xi +A_yj )=( n_xA_x + n_yA_y)=0

n_xA_x = - n_yA_y

Положив n_y равным 1, получаем n= -A_y/ A_x i + j (A_x0, т.е. сторона многоугольника не параллельна оси ординат). Если сторона многоугольника параллельна оси ординат, т.е. A_x=0, A_y 0, то вектор нормали параллелен оси абсцисс и следует положить n_x=1, n_y=0.

Найденную нормаль надо проверить, является ли она внутренней или внешней. Для этой проверки можно воспользоваться следующим фактом. Если вектор стороны многоугольника образован как разность векторов пары смежных его вершин A_i-1 и A_i и если скалярное произведение нормали n и вектора от A_i-1 до A_i+1 положительно, то n - внутренняя нормаль. В противном случае n - внешняя нормаль. Для получения внутренней нормали полученное значение n надо умножить на -1.

Можно предложить и третий способ (рис.3.6.14) определения факта выпуклости многоугольника с одновременным определением вектора внутренней нормали и разбиения исследуемого многоугольника на выпуклые многоугольники в случае его невыпуклости. Этот способ основан на использовании переносов и поворотов исследуемого многоугольника. Предполагается, что вершины многоугольника пронумерованы в направлении против часовой стрелки. Рассматриваемый алгоритм может быть представлен в следующем виде:

1. Осуществить перенос многоугольника таким образом, чтобы очередная i-ая вершина совпала с началом координат.

2. Осуществить поворот многоугольника относительно начала координат таким образом, чтобы следующая (i+1)- ая вершина оказалась на положительной полуоси абсцисс x.

3. Определить знак ординаты у всех (i+2)-ых вершин. Если знаки ординат у всех (i+2)-ых вершин неотрицательные, то многоугольник выпуклый относительно очередной стороны, соединяющей i-ую и (i+1)-ую вершины.

В повернутой системе координат внутренняя нормаль к ребру, соединяющему i-ую и (i+1)-ую вершины, имеет нулевую абсциссу и ординату, знак которой совпадает со знаком ординаты (i+2)-ой вершины. Для определения ориентации внутренней нормали исходного многоугольника следует выполнить обратные повороты.

Если ордината (i+2)-ой вершины равна нулю, то i-ая, (i+1)-ая и (i+2)-ая вершины лежат на одной прямой, т.е. ребра, соединяющие i-ую и (i+1)-ую вершины, а также (i+1)-ую и (i+2)-ую вершины коллинеарны. Если ординаты всех (i+2)-ых вершин равны нулю, то многоугольник вырожден, т.е. является отрезком.

Если знак ординаты (i+2)-ой вершины отрицателен, то многоугольник невыпуклый, его следует разбить на части. Многоугольник разрезается вдоль положительной полуоси x. Для этого ищутся стороны многоугольника, пересекающие ось абсцисс, и для них находится ближайшая к началу координат точка пересечения с этой осью, абсцисса которой больше значения x_i+1 (x> x_i+1). Далее формируются два многоугольника: первый многоугольник образован вершинами, начиная с (i+1)-ой и кончая найденной точкой пересечения (многоугольник лежит целиком ниже оси абсцисс), второй многоугольник образован всеми вершинами исходного многоугольника, не вошедшими в первый многоугольник, и точкой пересечения. Полученные многоугольники могут быть невыпуклым, поэтому описанная процедура применяется к ним до тех пор, пока все многоугольники, получаемые в процессе разбиения, не станут выпуклыми.