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

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

Внутренней нормалью к ребру многоугольника называется единичный вектор перпендикулярный к этому ребру и направленный внутрь многоугольника. Обозначим внутреннюю нормаль ребра A_iA_i+1 через n_i (I = 1,2,...,n). Если f - некоторая точка, лежащая на ребре многоугольника, n - внутренняя нормаль к этому ребру, а P - некоторая точка, полуплоскости, то знак скалярного произведения нормали и вектора из точки f в точку P определяет положение точки относительно грани, содержащей данное ребро (рис. 14).

V = n * (P - f).

Если взять точку f, совпадающую с вершиной многоугольника, то можно рассмотреть следующие три характерных случая расположения точки P, принадлежащей отрезку P₁P₂ (рис. 15).

Первый случай - угол между векторами n и (P-f) больше 90⁰:

V = n * (P - f) < 0, > /2.

Второй случай - угол между векторами n и (P-f) равен 90⁰:

V = n * (P - f) = 0, = /2.

Третий случай - угол между векторами n и (P-f) меньше 90⁰:

V = n * (P - f) > 0, < /2.

Для построения алгоритма здесь используется параметрическая запись прямой, продолжающей отрезок P₁P₂.

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

где t - параметр, определяющий положение точки на прямой.

При значениях

0 t 1

точка принадлежит отрезку P₁P₂. Если t < 0, то точка лежит левее точки P₁, а при t > 1 - правее P₂.

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

n_i *(P₁ + (P₂ - P₁) *t - A_i) = 0.

Из этого выражения после преобразований получаем значение параметра.

t = .

Выполним анализ полученного выражения. Для этого рассмотрим случай равенства нулю знаменателя. Это возможно, когда P₂ = P₁ или же в случае расположения отрезка P₁P₂ параллельно ребру многоугольника (угол между векторами n и P₁P₂ равен /2). Совпадение точек концов отрезка дает вырожденный случай, который не входит в рассмотрение задачи отсечения отрезка. При параллельном расположении отрезка возможны три варианта его видимости, определяемые из анализа числителя:

1. n_i *(P₁ - A_i) < 0. В этом случае точка P₁ находится вне отсекающего многоугольника ( > /2), а следовательно, и точка P₂; поэтому отрезок будет полностью невидимым;
2. n_i *(P₁ - A_i) = 0. Точка P₁ находится на границе отсекающего окна; значит отрезок лежит на грани данного ребра многоугольника, и для выделения видимой части отрезка следует найти общую часть отрезка и ребра;
3. n_i * (P₁ - A_i) > 0. Точка P₁ находится внутри отсекающего окна; в данном случае рассматриваемое ребро не влияет на видимость отрезка.

В случае неравенства нулю знаменателя, значение t дает точку пересечения прямой, продолжающей отрезок, и грани ребра. При значениях t < 0 или t > 1 точка пересечения находится за пределами отрезка P₁P₂. Тогда при t < 0 данное ребро не влияет на видимость отрезка (рис. 16).

При t > 1 отрезок полностью невидим, так как точка пересечения находится правее отрезка (рис. 17).

Если ориентацию отрезка поменять на противоположную (поменять местами точки P₁ и P₂), то рассмотренные последние два случая также поменяются местами.

Рассмотрим теперь случай 0 t 1. Здесь также возможны два варианта (рис.18).

a) n_i *(P₂ - P₁) > 0 b) n_i *(P₂ - P₁) < 0

В первом случае (рис. 18a) видимым является отрезок PP₂, во втором (рис. 18b) - отрезок PP₁. По этому поводу говорят, что отрезок укорачивается снизу или сверху соответственно.

Прямая, продолжающая отрезок P₁P₂, может пересечь многоугольник только в двух местах. Однако решение уравнения для t относительно всех ребер даст множество решений в интервале 0 t 1, из которых следует выбрать необходимые. Для этого все решения разбиваются на две группы, которые называются нижней и верхней, в зависимости от того, к какой точке отрезка ближе расположено рассматриваемое решение - к началу или концу отрезка соответственно. После разбиения решений выделяют наибольшее значение из нижней группы t_н, наименьшее - из верхней t_в, которые рассматриваются, как возможные ограничения снизу и сверху. Если окажется, что t_н > t_в, то отрезок является полностью невидимым.