Формализованный алгоритм Кируса-Бека

p(t) = p1+(p2-p1)t; 0≤t≤1 (1)

; i=1,2,… (2)

Подставив (1) в (2) найдем пересечение отрезка с областью: (3) либо (4), где пропорционально расстоянию от конца отрезка до выбранной точки, а определяет ориентацию отрезка.

D=- директриса

w_i=- некий весовой множитель

Тогда (4) примет вид: (5)

; D≠0; i=1,2,…

- точка вне области отсечения

- точка на границе окна

- точка внутри окна

Все решения следует разбивать на две группы: нижнюю и верхнюю, в зависимости от того, к какому концу отрезка будет ближе. Правильными решениями будут наибольшие из нижних и наименьшие из верхних. Если Dn_i­>0, то параметр t рассматривается как возможный нижний предел; если Dn_i­<0, то параметр t рассматривается как возможный верхний предел.

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

Дата добавления: 2014-01-07