15. Отсечение. Алгоритм Кируса Бека отсечения отрезка.

Отсечение отрезка произвольным выпуклым отсекателем

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

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

P(t)=P_1+(P_2-P_1 )t, 0≤t≤1

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

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

t<0 – для верхней и левой границ.

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

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

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

В данном случае точкам пересечения отрезков также соответствуют недопустимые значения параметра.

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

Видимость и невидимость отдельно взятой точки

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

Задача состоит в определении видимости точки A относительно каждой из сторон отсекателя.

Рассмотрим ребро C_1 C_2:

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

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

Выбранную произвольную точку на рассматриваемой стороне назовём f_i.

Рассмотрим скалярное произведение двух заданных векторов:

N_i (A-f_i )

Если N_i (A-f_i )>0, то точка видима относительно рассматриваемой стороны, так как косинус угла между данными векторами в этом случае положителен, то есть лежит в диапазоне от -90° до 90°, не включая эти конечные значения.

Если N_i (A-f_i )=0, то точка лежит на границе отсекателя.

Если N_i (A-f_i )<0, то точка расположена по невидимую сторону границы отсекателя.

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

Нахождение точек пересечения произвольного отрезка с границами отсекателя

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

Определим вектор внутренней нормали к стороне отсекателя C_1 C_2 и вектор с началом в произвольной точке стороны к точке отрезка в области отсечения:

Запишем скалярное произведение заданных векторов:

N_внi (P1+(P2-P1)t-f_i )

В соответствии с тем, что мы отметили выше можно записать:

Если N_внi (P_1+(P_2-P_1 )t-f_i )>0, то точка отрезка видима относительно рассматриваемой границы отсекателя.

Если N_внi (P_1+(P_2-P_1 )t-f_i )=0, то точка отрезка расположена на границе отсекателя.

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

Если N_внi (P_1+(P_2-P_1 )t-f_i )<0, то точка расположена по невидимую сторону отсекателя.

Приравняем скалярное произведение нулю:

N_внi (P_1+(P_2-P_1 )t-f_i )=0

Обозначим вектор P_2-P_1 следующим образом:

D=P_2-P_1

Данный вектор является вектором направления отрезка. Его также называют директрисой.

Обозначим вектор P_1-f_i следующим образом:

W_i=P_1-f_i

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

1. D = 0 – отрезок вырожденный.

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

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

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

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

W_ск и D_ск

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

Выбор точек пересечения

Как говорилось выше, в случае видимости отрезка, находится столько точек пересечения, сколько сторон у отсекателя. Таким образом, для примера, для пятиугольного отсекателя будут определены параметры t_1,t_2,t_3,t_4,t_5. От нас требуется определить, какая из найденных точек пересечения будет являться началом видимой части отрезка, а какая концом видимой части отрезка.

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

Занесём на заданный интервал значения найденных параметров:

(в рассмотренном мною случае отсутствуют параметры >=1 и <=0, но в том случае, если такие параметры были бы, то располагались бы они соответственно за пределами интервала (0; 1), либо на его концах)

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

Видно, что все найденные точки пересечения можно разделить на две группы:

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

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

То, в какую группу можно отнести точку, определяется по знаку скалярного произведения D_ск:

Если D_ск>0, то точка расположена ближе к началу отрезка.

Если D_ск<0, то точка расположена ближе к концу отрезка.

Из иллюстрации выше видно, что начало видимой части отрезка будет определяться наибольшим значением параметра из тех значений, которые определяют начало видимой части. В случае, указанном выше, таким параметром будет t_1. Конец же видимой части отрезка будет определяться наименьшим значением параметра из тех значений, которые определяют конец видимой части. В случае, указанном выше, таким параметром будет t_4.

Также стоит отметить следующий частный случай расположения отрезка относительно отсекаемой области:

Выполняя описанную процедуру нахождения точек пересечения заданного отрезка с границами отсекателя, как итог получим две точки, соответствующие параметрам t_н и t_к, определяющие начало и конец видимой части отрезка. То есть формально мы получаем два значения параметра, расположенных в интервале от нуля до единицы. Если не выполнить проверку того, что начало видимой части отрезка располагается до его конца, то будет получен неверный результат. То есть будет внесена следующая проверка:

t_н≤t_к

Следует отметить, следующие факты для дальнейшего описания алгоритма:

1. Изначально весь отрезок считается видимым, то есть t_к=1,t_н=0.

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

Способ определения внутренней нормали к заданной стороне многоугольника

Из курса аналитической геометрии нам известно, что равенство нулю скалярного произведения некоторых двух векторов означает, что эти векторы перпендикулярны. Данный факт мы и будем использовать для того, чтобы определить нормаль к i-ой стороне отсекателя.

Пусть A- некоторый вектор, нормаль к которому мы ищем, а вектор N- искомая нормаль. Запишем формулу для вычисления скалярного произведения двух этих векторов:

A_x N_x+A_y N_y=0

Так как нам требуется найти направление нормали, следовательно можем задать одну из проекций нормали = 1 (в моём случае, это N_x):

A_x+A_y N_y=0

При этом не стоит пренебрегать перед вычислением выражения сверху проверкой на равенство A_y нулю, так как в таком случае требуется задать вектор {0, 1} как вектор нормали заданной стороны. При этом, после выполнения вычислений, стоит проверить также, была определена внутренняя или внешняя нормаль (определяется по знаку скалярного произведения найденной нормали с вектором, заданным по следующей стороне), и во втором случае вернуть вектор, обратный найденному.

Способ определения выпуклости многоугольника

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

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

C_i C_(i+1)*C_(i+1) C_(i+2)≥0

При этом векторы внутренних нормалей в этом случае ориентированы влево относительно направления векторов обхода.

Если все C_i C_(i+1)*C_(i+1) C_(i+2)=0, то многоугольник вырожденный.

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

При этом стоит отметить, что в своей реализации я несколько «упростил» условия выпуклости данного способа, так как мне не требовалось дополнительно опознавать направление внутренних нормалей (определение нормалей было вынесено в другой модуль), поэтому анализируется факт того, что все произведения не изменяют своего знака, либо являются нулевыми значениями (но не все).

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

1. Ввод исходных данных: точки отрезка P_1 (P_(1.x),P_(1.y) )  и P_2 (P_(2.x),P_(2.y) )
2. Ввод числа сторон m выпуклого многоугольника и координат его вершин (массив C)
3. Проверка отсекателя на выпуклость. Если отсекатель невыпуклый, то вывести ошибку
 и перейти к пункту 8.
4. Вычисление директрисы заданного отрезка:
D=P_2-P_1
5. Инициализация пределов значений параметра t при условии, что отрезок полностью видим:
t_н=0,t_к=1
6. Начало цикла по всем сторонам отсекателя.
Для каждой i-ой стороны отсекателя выполнить следующие действия:
6.1. Вычисление вектора внутренней нормали к очередной i-ой стороне отсекателя - N_вi
6.2. Определение граничной точки f_i каждой стороны отсекателя
6.3. Вычисление вектора W_i=P_1-f_i
6.4. Вычисление скалярного произведения векторов:
W_iскал=W_i N_вi
6.5. Вычисление скалярного произведения векторов:
D_скал=DN_вi  
6.6. Проверка на равенство нулю скалярного произведения D_скал (вырождение отрезка в
 точку или его параллельность стороне отсекателя).
Если D_скал=0, тогда переход к пункту 6.9.
6.7. Вычисление параметра t:
t=-W_скi/D_ск 
6.8. Определение верхнего и нижнего пределов параметра t:
6.8.1. Поиск нижней границы параметра t:
если D_ск>0:
Если t>1, то переход к пункту 8 (отрезок невидим, так как нижний предел параметра t,
превышает единицу и пересечение с отсекателем имеет место для самого отрезка,
а для его продолжения за вершину P_2).
Если t≤1, то t_н=max⁡(t,t_н) (выбор максимального значения из текущего значения параметра
t и ранее вычисленного значения нижней границы параметра).
6.8.2. Поиск верхней границы параметра t, если D_скал≤0:
Если t<0, то переход к пункту 8 (отрезок невидим, так как верхний предел параметра 
t отрицателен и пересечение с отсекателем имеет место не для самого отрезка, а для 
его продолжения за вершину P_1).
Если t≥0, то t_в=min⁡(t,t_в) (выбор минимального значения из текущего значения параметра t 
и раннее вычисленного значения верхней границы параметра).
6.9. Проверка видимости точки, в которую выродился отрезок, или проверка видимости произвольной 
точки отрезка в случае его параллельности стороне отсекателя: если W_скi<0, то отрезок (точка)
невидим(-а) и переход к п. 7. Если W_скi>0, то отрезок (точка) видим(-а) относительно текущей 
стороны отсекателя и переход к пункту 6.10.
6.10. Конец цикла по сторонам отсекателя.
7. Проверка фактической видимости отсечённого отрезка. Если t_н≤t_в, то изобразить отрезок в 
интервале от P(t_н ) до P(t_н ).
8. Конец алгоритма.

Куров стр. 29-30

Следующий вопрос: 16. Внутреннее и внешнее отсечение. Определение выпуклости многоугольника; определение нормали; разбиение невыпуклых многоугольников. Триангуляция многоугольников.

Предыдущий вопрос: 14. Отсечение Алгоритм разбиения средней точкой при отсечении отрезка.