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

 


Рис. 5. Отсечение невыпуклым многоугольником.

На Рис. 5 результатом отсечения отрезка AB являются отрезки C1D1 и C2D2

Алгоритм в этом случае по сути аналогичен приведенному выше алгоритму для отсечения выпуклым многоугольником.


 

Создадим список точек пересечения Ax c многоугольником:

 

Для каждого ребра возможны 4 случая:

а) обе его вершины лежат выше или ниже Ax(например, на Рис. 5 3-4): ничего не заносим в наш список  
б) его вершины лежат по разные стороны от Ax (например, на Рис. 5 1-2): заносим в список точку пересечения  
в) ребро лежит на Ax ничего не заносим в наш список  
г) вершина лежит на Ax г 1) если другие вершины смежных ребер лежат по одну сторону от Ax: ничего не заносим в список  
г 2) если другие вершины смежных ребер лежат по разные стороны от Ax: заносим эту вершину в список,

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

x1 < x2 < x3 < x4 и т.д., тогда искомый отрезок - это :

[0,l] Ç ([x1,x2] È [x3,x4] È [x5,x6] …)(т.к. нечетная точка - всегда точка "входа", а четная - точка "выхода")

 

2.3. Комбинированный алгоритм Кузьмина. [Kuzmin, 1995]

 

Алгоритм Кузьмина является модификацией алгоритма Брезенхема, позволяющей сразу решать задачу и отсечения по прямоугольнику, и рисования отрезка. Ниже приводятся основные идеи алгоритма. Точное описание можно найти в [Kuzmin, 1995]

 


Рис. 6. Определение точки входа.

Первым делом проверим, нужно ли рисовать что-либо вообще (например, с помощью идеи алгоритма Сазерленда-Кохена).

Если нужно рисовать, то перейдем к канонической системе координат Axy, тогда наш отсекающий прямоугольник можно задать координатами своих левого нижнего C(x1,y1) и правого верхнего D(x2,y2)углов. Тогда в зависимости от знака векторного произведения [AB ´ AC] (т.е.a*y1-b*x1)отрезок ABпересекает:

1) горизонтальную границу (случай на Рис. 6)

[AB ´ AC] >0

2) вертикальную границу

[AB ´ AC] <0

 


Найдем для двух случаев начальные значения x, y и e0 , далее будем действовать по алгоритму Брезенхема. Ради целочисленности алгоритма все переменные, связанные с e, по-прежнему домножены на 2a.

1) Горизонтальный случай (Рис. 7).

Рис. 7. Горизонтальный случай.   В этом случае y=y1; а вот x надо найти. Для этого будем следовать алгоритму Брезенхема, как если бы мы рисовали без отсечения, тогда первая точка с координатой y1 будет нарисована тогда, когда для некоего x=xв будет выполнено следующее: xR Î (xв , xв+1] , где R - точка пересечения нашего отрезка с прямой y=y1- 0.5 xв=*(y1 -)+1= (a*(2*y1-1))/(2*b) +1 (Деление целочисленное (т.е. возвращает целую часть частного) !!) De=(yP0- yP1)*2a= (y1 -*xв)*2a= =2*(a*y1- b*xв)   e0=2b - a - De=2b - a- 2*a*y1+ 2*b*xв= = 2b*(xв+1) - a*(2*y1+1)

2) Вертикальный случай (Рис. 8).

Рис. 8. Вертикальный случай.   В этом случае x=x1; а вот yнадо найти исходя из значения e0 Пусть yв=x1*(b/a)=(x1*b)/a(Деление целочисленное (т.е. возвращает целую часть частного) !!) e0=(*x1-yв-)*2a = 2b*x1-a*(2*yв+1)   Тогда возможны 2 варианта: 1) e0 < 0 тогда первая точка - P1 (x=x1 , y=yв) и e0=e0 + 2*b 2) e0 ³0 тогда первая точка - P2 (x=x1 , y=yв+1) и e0=e0 + 2*b-2*a

 

Условием выхода из алгоритма является:

(т.е. достижение края прямоугольника или конца отрезка)