Коен-Садерландов алгоритам

Коен-Садерландов алгоритам (енгл. Cohen–Sutherland algorithm) је алгоритам рачунарске графике који се користи за сецкање линија (енгл. Line clipping). Овај алгоритам дели раван на 9 делова (или простор на 27 делова) и затим ефикасно одређује који делови којих линија су видљиви у централном региону - у оквиру за приказ (енгл. viewport).

Алгоритам је развијен током рада на симулатору лета од стране Денија Коена и Ивана Садерланда.

Алгоритам

Алгоритам укључује, искључује или делимично укључује дужи базирано на следећем:

• Ако су оба краја дужи у оквиру за приказ (битовска дисјунција крајњих тачака == 0) : тривијално прихватамо целу дуж.
• Ако су оба краја дужи мања од x_мин, онда се та дуж тривијално одбацује. Аналогно важи за x_маx, y_мин и y_маx. Ово се лако проверава са битовском коњукцијом крајњих тачака дужи ( == 0).
• Ако су крајње тачке дужи у различитим регионима: Алгоритам прво проналази крај дужи који се налази ван оквира за приказ (мора да постоји бар један такав). Затим се израчуна пресек са проширеним оквиром за приказ (оквир за приказ чије су странице продужене тако да буду праве а не дужи) и на тај начин се добија нова тачка. Овај поступак се понавља све док се не додје до једне од претходно наведених тривијалних ситуација.

Кодови који се придружују тачкама су следећи:

1001	1000	1010
0001	0000	0010
0101	0100	0110

Први бит (најмање тежине) означава да је тачка изнад горње границе (већа од y_маx).

Други бит (најмање тежине) означава да је тачка испод доње границе (мања од y_мин).

Трећи бит (најмање тежине) означава да је тачка десно од десне странице (већа од x_маx).

Четврти бит (најмање тежине) означава да је тачка лево од леве странице (мања од x_мин).

Кохен Сатерлендов алгоритам може да се користи само у случају када је клипинг површина правоугаоник. За клипинг у случају конвексног полигона, може се користити Сајрус-Беков алгоритам.

Пример C/C++ имплементације

typedef int OutCode;

const int INSIDE = 0; // 0000
const int LEFT = 1; // 0001
const int RIGHT = 2; // 0010
const int BOTTOM = 4; // 0100
const int TOP = 8; // 1000

// Compute the bit code for a point (x, y) using the clip rectangle
// bounded diagonally by (xmin, ymin), and (xmax, ymax)

// ASSUME THAT xmax, xmin, ymax and ymin are global constants.

OutCode ComputeOutCode(double x, double y)
{
	OutCode code;

	code = INSIDE; // initialised as being inside of clip window

	if (x < xmin) // to the left of clip window
		code |= LEFT;
	else if (x > xmax) // to the right of clip window
		code |= RIGHT;
	if (y < ymin) // below the clip window
		code |= BOTTOM;
	else if (y > ymax) // above the clip window
		code |= TOP;

	return code;
}

// Cohen–Sutherland clipping algorithm clips a line from
// P0 = (x0, y0) to P1 = (x1, y1) against a rectangle with 
// diagonal from (xmin, ymin) to (xmax, ymax).

void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1)
{
	// compute outcodes for P0, P1, and whatever point lies outside the clip rectangle
	OutCode outcode0 = ComputeOutCode(x0, y0);
	OutCode outcode1 = ComputeOutCode(x1, y1);
	bool accept = false;

	while (true) {
		if (!(outcode0 | outcode1)) { // Bitwise OR is 0. Trivially accept and get out of loop
			accept = true;
			break;
		} else if (outcode0 & outcode1) { // Bitwise AND is not 0. Trivially reject and get out of loop
			break;
                } else {
			// failed both tests, so calculate the line segment to clip
			// from an outside point to an intersection with clip edge
			double x, y;

			// At least one endpoint is outside the clip rectangle; pick it.
			OutCode outcodeOut = outcode0 ? outcode0 : outcode1;

			// Now find the intersection point;
			// use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
			if (outcodeOut & TOP) { // point is above the clip rectangle
				x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
				y = ymax;
			} else if (outcodeOut & BOTTOM) { // point is below the clip rectangle
				x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
				y = ymin;
			} else if (outcodeOut & RIGHT) { // point is to the right of clip rectangle
				y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
				x = xmax;
			} else if (outcodeOut & LEFT) { // point is to the left of clip rectangle
				y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
				x = xmin;
			}

			// Now we move outside point to intersection point to clip
			// and get ready for next pass.
			if (outcodeOut == outcode0) {
				x0 = x;
				y0 = y;
				outcode0 = ComputeOutCode(x0, y0);
			} else {
				x1 = x;
				y1 = y;
				outcode1 = ComputeOutCode(x1, y1);
			}
		}
	}
	if (accept) {
               // Following functions are left for implementation by user based on
               // their platform (OpenGL/graphics.h etc.)
               DrawRectangle(xmin, ymin, xmax, ymax);
               LineSegment(x0, y0, x1, y1);
	}
}

Види још

Алгоритми који се користе у исту сврху:

• Лианг-Барски алгоритам
• Сајрус-Беков алгоритам

Литература

• Фолеy, Јамес D. (1996). Цомпутер Грапхицс: Принциплес анд Працтице. Аддисон-Wеслеy Профессионал. ИСБН 978-0-201-84840-3. 
• Предраг Јаничић. [1]. Математички факултет, Београд

Спољашње везе

• ЈаваСцрипт полyлине цлиппинг либрарy усинг Цохен-Сутхерланд алгоритхм
• Аниматед ЈаваСцрипт имплементатион
• Делпхи имплементатион