Алгоритм двумерного отсечения Кируса-Бека

Алгоритм двумерного отсечения Кируса-Бека

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

Параметрическая форма записи уравнения отрезка с концами P1 и P2 имеет следующий вид:

,

где t – параметр, принимающий значения в диапазоне 0 £ t £ 1.

В декартовой системе координат приведенное выше уравнение сводится к двум одномерным параметрическим уравнениям:

; ;

здесь x1 , y1 и x2 , y2 – координаты соответственно начала и конца отрезка.

На координатной плоскости (x, y) точкам начала и конца отрезка можно поставить в соответствие векторы (рис.6):

; ;

и – единичные векторы, направленные вдоль осей x и y соответственно.

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

Для вектора, связанного с произвольной точкой P(t) отрезка, выражение в параметрическом виде запишется так:

.

Точке f (расположенной, например, на границе 1 отсекателя в одной из сопряженных с этой границей вершин, см. рис.6) на плоскости будет соответствовать вектор .

Ориентацию точки P(t) относительно точки f можно характеризовать вектором .

О расположении же произвольной точки P (t), принадлежащей отрезку P1 P2 , по отношению к какой-либо границе (например, опять к границе 1), можно судить по величине скалярного произведения

,

где – вектор внутренней (т. е. направленной внутрь окна) нормали к данной границе (рис.6). Только в том случае, когда это произведение равно нулю, точка P(t) лежит на бесконечной прямой, проходящей через указанную границу, и является возможной точкой пересечения (см. рис.6).

Поэтому в алгоритме Кируса-Бека реальные точки пересечения отрезка с границами отсекающего многоугольника ищутся среди решений уравнений

,

где и` – нормаль к i-ой к границе многоугольника и вектор, соответствующий принадлежащей этой границе точке fi ; i = 1, 2, 3, … .

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

(при ),

где` – вектор, называемый директрисой отрезка, – вектор, связывающий точку fi с началом отрезка P1 .

Если найденное при решении последнего уравнения значение ti лежит за пределами интервала 0 £ t £ 1, то его следует проигнорировать (как значения t1 < 0 и t4 > 1 для отрезка P1 P2 на рис.7). Вместе с тем, количество полученных значений ti, принадлежащих интервалу 0 £ t £ 1, может оказаться больше двух (t2, t3, t5 и t6 для отрезка P1 P2 на рис.7). В этом случае среди группы точек с` (t2 и t3 на рис.7), расположенных ближе к началу отрезка, следует выбрать точку с максимальным значением t, т. к. именно она является реальной точкой пересечения и определяет так называемый нижний предел tН (tН = max (t2 , t3 ) = t2 на рис.7). Среди группы точек с` (t5 и t6 на рис.7), лежащих ближе к концу отрезка, надо выбрать точку с минимальным значением t, т. к. она является реальной точкой пересечения и определяет так называемый верхний предел tВ (tВ = min (t5 , t6 ) = t5 на рис.7).

Для учета отрезков, у которых хотя бы один из концов находится внутри отсекающего многоугольника, необходимо заранее присвоить значения нижнего и верхнего пределов соответственно tН = 0 и tВ = 1. При проведении анализа, суть которого изложена выше, для полностью видимого отрезка эти значения не изменятся (как для отрезка P3 P4 на рис.7), а для частично видимого отрезка изменится лишь одно их значений, в зависимости от того, какой из концов лежит вне отсекателя (как для отрезка P5 P6 на рис.7 значение tВ).

Можно показать, что в случаях, когда в какой-либо возможной точке пересечения при` t > 1 или при` t < 0, а также когда оказывается, что tН > tВ, отрезок является полностью невидимым.

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

Изложенные соображения служат основой алгоритма Кируса-Бека. Данный алгоритм на псевдокоде (см. приложение 1) приведен ниже. Полагается, что заранее установлен факт выпуклости отсекающего многоугольника и определены внутренние нормали к его сторонам. Кроме описанных выше величин в алгоритме используется значение k, равное числу сторон отсекающего многоугольника, а в подпрограмме вычисления скалярного произведения – векторы и , задаваемые двумя компонентами (по осям x и y): Вект1x, Вект1y и Вект2x, Вект2y соответственно.

Инициализация нижнего и верхнего пределов параметра t

tН = 0

tВ = 1

Вычисление директрисы

Главный цикл

for i = 1 to k

call Скал_пр (,;Dск )

call Скал_пр (,;W ск )

Отрезок параллелен границе или вырожден в точку?

if Dск = 0 then 2

t = - Wск / Dск

if Dск > 0 then 1

Анализ верхнего предела

if t < 0 then 4

if tВ > t then tВ = t

go to 3

Анализ нижнего предела

1 if t > 1 then 4

if tН < t then tН = t

go to 3

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

2 if Wск < 0 then 4

3 next i

Проверка видимости отрезка с рассчитанными пределами

if tН > tВ then 4

Начертить отрезок от P( tН ) до P( tВ )

4 finish

Подпрограмма вычисления скалярного произведения

subroutine Скал_пр (, ; Скал)

Скал = Вект1x*Вект2x + Вект1y*Вект2y

return

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

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