Модифицированный алгоритм Брезенхейма с устранением ступенчатости для первого квадранта
Отрезок проводится из (x1,y1) в (x2,y2)
I — число доступных уровней интенсивности все переменные целого типа
p
rocedure
Line(x1, y1, x2, y2, I: Integer);
var dx, dy, d, d1, d2, i: Integer;
begin
// Инициализация переменных
x=x1;
y=y1;
dx = x2 – x1;
dy = y2 – y1;
m = (I*dy)/d x;
w = I – m;
e = I/2;
PutPixel(x, y, m/2) ;
while (x<x2) do
begin
if e<w then
begin inc(x); inc(e, m); end
else
begin inc(x); inc(y); inc(e, – w); end;
PutPixel(x, y, e')
end;
end;
Интенсивность для первого пиксела предполагает, что отрезок начинается с адреса пиксела. Результаты для отрезка с тангенсом угла наклона m = 5/8 и восемью уровнями интенсивности представлены на рисунке первом - с. Распространить работу алгоритма на другие октанты можно тем же способом, что и для основного алгоритма Брезенхейма.
Отсечение отрезка. Алгоритм Сазерленда-Кохена
Необходимость отсечь выводимое изображение по границам некоторой области встречается довольно часто. В простейших ситуациях в качестве такой области, как правило, выступает прямоугольник. В таких случаях имеет смысл предварительно пересчитать координаты отрезка в отдельной процедуре, а в процедуру рисования отрезка подавать координаты лежащие в пределах экрана.
Ниже рассматривается достаточно простой и эффективный алгоритм отсечения отрезков по границе произвольного прямоугольника. Он заключается в разбиении всей плоскости на 9 областей прямыми, образующими прямоугольник. В каждой из этих областей все точки по отношению к прямоугольнику расположены одинаково. Определив, в какие области попали концы рассматриваемого отрезка, легко понять, где именно необходимо отсечение. Для каждой области сообщается 4-битовый код, где установленный:
бит 0 означает, что точка лежит левее прямоугольника,
бит 1 означает, что точка лежит выше прямоугольника,
бит 2 означает, что точка лежит правее прямоугольника,
бит 3 означает, что точка лежит ниже прямоугольника.
Приведенная ниже программа реализует алгоритм Сазерленда-Кохена отсечения отрезка по прямоугольной области, в неё необходимо дополнительно добавить проверку не попадания отрезка в область экрана для полностью корректной работы.
procedure Swap(var a, b: Integer);
var c: Integer;
begin
c := a; a := b; b := c;
end;
function OutCode(x, y, x1, y1, x2, y2: Integer): Integer;
var code: Integer;
begin
code := 0;
if x < x1 then code := code or 1;
if y < y1 then code := code or 2;
if x > x2 then code := code or 4;
if y > y2 then code := code or 8;
end;
procedure ClipLine(x1, y1, x2, y2, dx1, dy1, dx2, dy2: Integer);
var
code1, code2: Integer;
inside: Boolean;
begin
code1 := OutCode(x1, y1, dx1, dy1, dx2, dy2);
code2 := OutCode(x2, y3, dx1, dy1, dx2, dy2);
inside := (code1 or code2) = 0;
while (not inside) do
begin
if code1 = 0 then
begin Swap(x1, x2); Swap(y1, y2); Swap(code1, code2); end;
if (code1 and 1) <> 0 then // clip left
begin inc(y1, LongInt((y2 – y1)*(dx1 – x1)) div (x2 – x1)); x1 := dx1; end;
if (code1 and 2) <> 0 then // clip above
begin inc(x1, LongInt((x2 – x1)*(dy1 – y1)) div (y2 – y1)); y1 := dy1; end;
if (code1 and 4) <> 0 then // clip left
begin inc(y1, LongInt((y2 – y1)*(dx2 – x1)) div (x2 – x1)); x1 := dx2; end;
if (code1 and 8) <> 0 then // clip above
begin inc(x1, LongInt((x2 – x1)*(dy2 – y1)) div (y2 – y1)); y1 := dy2; end;
code1 := OutCode(x1, y1, dx1, dy1, dx2, dy2);
code2 := OutCode(x2, y3, dx1, dy1, dx2, dy2);
inside := (code1 or code2) = 0;
end;
line(x1, y1, x2, y2);
end;
Замечание. Необходимо также учитывать, что весь отрезок может вообще не попадать в видимую область экрана и отрезок в этом случае рисовать не нужно, в приведенной выше процедуре этот момент не учитывается.