Отсечение невыпуклым многоугольником без самопересечений.
Рис. 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 |
Условием выхода из алгоритма является:
(т.е. достижение края прямоугольника или конца отрезка)