2014-02-24
489
Отсечение прямоугольником.
II. Отсечение отрезка (clipping).
Лекция 2, часть 2
СПИСОК ЛИТЕРАТУРЫ
[Bresenham, 1965] Bresenham J.E. Algorithm for Computer Control of a Digital Plotter //IBM System Journal.- 1965.- Vol.4.- pp. 25-30.
[Castle-Pitteway, 1987] Castle C.M., Pitteway L.V. An Efficient Structural Technique for Encoding "Best-fit" Straight Lines //The Computer Journal.- 1987.- Vol. 30, No. 2.
Задача отсечения прямоугольником возникает, как правило, из-за физически конечных размеров растра, на который происходит вывод (пример: дисплей компьютера)
Возможные подходы:
1) В функции изменения атрибутов пиксела проверять x и y на попадание в допустимые диапазоны значений.
Неэффективно, так как произойдет слишком расчетов для не отображаемых точек.
Классифицируем все точки в зависимости от их положения по отношению к отсекающим прямым 1, 2, 3, 4: поставим в соответствие каждой области 4-битный код.
Рис. 1. Алгоритм Сазерленда-Кохена.
Установим эти биты следующим образом:
0 бит - если точка лежит левее прямой 1
1 бит - если точка лежит выше прямой 2
|
|
|
2 бит - если точка лежит правее прямой 3
3 бит - если точка лежит ниже прямой 4
Тогда для отрезка AB на Рис. 1 будем иметь:
код A = 1001
код B = 0100
Пусть A - код точки - начала отрезка,
B - код точки - конца отрезка.
Возможные варианты:
· A = B = 0000
Этот случай означает, что обе точки лежат внутри прямоугольника (т. е. отсечение не требуется)
· C= A & B ¹ 0
В этом случае точки лежат по одну сторону от какой-либо отсекающей линии (с внешней ее стороны), следовательно, рисовать вообще ничего не нужно.
· В противном случае необходимо находить точки пересечения с некоторыми из отсекающих прямых (для прямых, которые пересекает AB, соответствующий бит в A^B установлен в 1), разбить наш отрезок найденными точками пересечения и затем применить тот же анализ кодов концов уже для этих подотрезков. Один из возможных вариантов реализации окончательного алгоритма приведен ниже:
Алгоритм:
Пусть A=(x1,y1), B=(x2,y2);
(x_лево, y_верх, x_право, y_низ) - отсекающий прямоугольник
Функция код(<точка>) возвращает код, значение которого описано выше
Отсечь (x1, y1, x2, y2, x_лево, y_верх, x_право, y_низ)
{
пока((код(A) | код(B)) && (!(код(A) & код(B))))
{
если(код(A) == 0) // т.е. A внутри
поменять(A,B); //меняем координаты местами, чтобы A всегда лежала снаружи
если(код(A) & 0x01) // т.е. A лежит слева от отсекающего прямоугольника
{
y1+=(y2-y1)*(x_лево-x1)/(x2-x1);
x1=x_лево;
}
иначе если(код(A) & 0x02) // т.е. A лежит сверху от отсекающего прямоугольника
{
x1+=(x2-x1)*(y_верх-y1)/(y2-y1);
y1=y_верх;
}
иначе если(код(A) & 0x04) // т.е. A лежит справа от отсекающего прямоугольника
{
y1+=(y2-y1)*(x_право-x1)/(x2-x1);
x1=x_право;
}
иначе если(код(A) & 0x08) // т.е. A лежит снизу от отсекающего прямоугольника
|
|
|
{
x1+=(x2-x1)*(y_низ-y1)/(y2-y1);
y1=y_низ;
}
}
}
На выходе AB - отсеченный отрезок.
