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

Задачу отсечения иногда называют задачей клиппирования (от английского 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 ();

}