Отсечение отрезка. Алгоритм Сазерленда-Кохена

Задачу отсечения иногда называют задачей клиппирования (от английского clip - отрезать, отсекать). Она возникает довольно часто. Пример - размещение изображений в окнах, в том числе занимающих весь экран, при различном разрешении (640*480, 800*600 и т.д.). Требуется знать пикселы, лежащие за пределами окна, и не работать с ними. Решение "в лоб" - сравнивать с границами каждый выводимый пиксел. Но это долго, т.к. сравнение должно быть встроено в цикл в алгоритме Брезенхейма. К тому же границы должны или где-то храниться в виде набора адресов пикселов, или вычисляться путем 4-х кратного (для каждой стороны прямоугольника) решения уравнения прямой для каждой точки. Придется также учитывать специальные случаи горизонтальной и вертикальной прямой, а также вырождение прямой в точку.

Алгоритм Сазерленда-Кохена широко известен благодаря простоте и эффективности. Плоскость делится на 9 областей. В каждой из областей точки по отношению к прямоугольнику расположены одинаково. Определив, в какие области попали концы отрезка, легко определить, где нужно отсечение. Для этого каждой области сопоставляется 4-битовый код, имеющий следующий смысл:

N бита	Положение точки при бит=1
	Слева от прямоугольника
1	Выше прямоугольника
	Справа от прямоугольника
	Ниже прямоугольника

Соотношение конечных точек и прямоугольника вычисляется с помощью поразрядных логических операций над кодами. Они выполняются очень быстро, т.к. в процессорах 80x86 есть машинные команды AND и OR. Реализацию алгоритма см. в [ 1,3 ]. Программа из [ 1 ] - в rastr\clip\line3.cpp.

#include <conio.h>

#include <graphics.h>

#include <process.h>

#include <stdio.h>

#include <stdlib.h>

void Swap (int& a, int& b)

{

int c;

c = a;

a = b;

b = c;

}

int OutCode (int x, int y, int X1, int Y1, int X2, int Y2)

{

int code = 0;

// Кодирование точки в соответствии с правилами образования кодов

if (x < X1)

code |= 0x01; // код 0001

if (y < Y1)

code |= 0x02; // код 0010

if (x > X2)

code |= 0x04; // код 0100

if (y > Y2)

code |= 0x08; // код 1000

return code;

}

void ClipLine (int x1, int y1, int x2, int y2,

int X1, int Y1, int X2, int Y2)

{

// кодирование концов отрезка *

int code1 = OutCode (x1, y1, X1, Y1, X2, Y2);

int code2 = OutCode (x2, y2, X1, Y1, X2, Y2);

int inside = (code1 | code2) == 0; // внутри

int outside = (code1 & code2)!= 0; // вне

while (!outside &&!inside)

{

if (code1 == 0)

{

Swap (x1, x2);

Swap (y1, y2);

Swap (code1, code2);

}

if (code1 & 0x01) // clip left

{

y1 += (long)(y2-y1)*(X1-x1)/(x2-x1);

x1 = X1;

}

else

if (code1 & 0x02) // clip above

{

x1 += (long)(x2-x1)*(Y1-y1)/(y2-y1);

y1 = Y1;

}

else

if (code1 & 0x04) // clip right

{

y1 += (long)(y2-y1)*(X2-x1)/(x2-x1);

x1 = X2;

}

else

if (code1 & 0x08) // clip below

{

x1 += (long)(x2-x1)*(Y2-y1)/(y2-y1);

y1 = Y2;

}

code1 = OutCode (x1, y1, X1, Y1, X2, Y2);

code2 = OutCode (x2, y2, X1, Y1, X2, Y2);

inside = (code1 | code2) == 0;

outside = (code1 & code2)!= 0;

}

line (x1, y1, x2, y2);

}

main ()

{

int driver = DETECT;

int mode;

int res;

initgraph (&driver, &mode, "c:\\tcpp\\bgi");

if ((res = graphresult ())!= grOk)

{

printf("\nGraphics error: %s\n", grapherrormsg (res));

exit (1);

}

int ClipX1 = 100,

ClipY1 = 50,

ClipX2 = 540,

ClipY2 = 300;

rectangle (ClipX1, ClipY1, ClipX2, ClipY2);

setcolor(GREEN);

ClipLine (1, 100, 600, 200, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(YELLOW);

ClipLine (1, 100, 600, 500, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(12);

ClipLine (300, 600, 510, 3, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(11);

ClipLine (300, 0, 610, 200, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(9);

ClipLine (300, 0, 300, 500, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(13);

ClipLine (200, 100, 500, 200, ClipX1, ClipY1, ClipX2, ClipY2);

getch ();

closegraph ();

}

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