Cohen-Sutherlands algoritme

Cohen–Sutherlands algoritme er en datagrafikk-algoritme som brukes for linjeklipping. Algoritmen deler et todimensjonalt område inn i ni regioner (eller et tredimensjonalt område inn i 27 regioner), og avgjør så på en effektiv måte hvilke linjer og linjesegmenter som er synlige i den midterste regionen (skjermporten).
Algoritmen ble utviklet i 1967, under arbeid med en flysimulator, av Danny Cohen og Ivan Sutherland.

Eksempel på C/C++ implementasjon

typedef int OutCode;const int INSIDE = 0; // 0000const int LEFT = 1;   // 0001const int RIGHT = 2;  // 0010const int BOTTOM = 4; // 0100const int TOP = 8;    // 1000// Regn ut bitkode for et punkt (x, y) ved bruk av klipperektangelet// avgrenset diagonalt av (xmin, ymin), og (xmax, ymax)// REGN MED AT xmax, xmin, ymax og ymin er globale konstanter.OutCode ComputeOutCode(double x, double y){
OutCode code;

code = INSIDE;          // settes som utgangspunkt inni klippevinduet

if (x < xmin)           // til venstre for klippevinduet
code |= LEFT;
else if (x > xmax)      // til høyre for klippevinduet
code |= RIGHT;
if (y < ymin)           // under klippevinduet
code |= BOTTOM;
else if (y > ymax)      // over klippevinduet
code |= TOP;

return code;}// Cohen–Sutherland linjeklippingsalgoritme klipper linjer fra// P0 = (x0, y0) til P1 = (x1, y1) mot et rektangel med // diagonal fra (xmin, ymin) til (xmax, ymax).void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1){
// regn ut utkoder for P0, P1, og evt. punkter som ligger utenfor klipperektangelet
OutCode outcode0 = ComputeOutCode(x0, y0);
OutCode outcode1 = ComputeOutCode(x1, y1);
bool accept = false;

while (true) {
if (!(outcode0 | outcode1)) { // Bitvis OR er 0. Trivielt akseptert, gå ut av løkken
accept = true;
break;
} else if (outcode0 & outcode1) { // Bitvis AND er ulik 0. Trivielt forkastet, gå ut av løkken
break;
} else {
// feilet begge tester, så regn ut nytt linjesegment
// fra utsiden til krysningspunkt med kanten til klipprektangelet
double x, y;

// Minst ett endepunkt ligger utenfor klipperektangelet; velg det.
OutCode outcodeOut = outcode0 ? outcode0 : outcode1;

// Finn så krysningspunktet;
// bruk formel y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
if (outcodeOut & TOP) {           // punktet er over klipperektangelet
x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
y = ymax;
} else if (outcodeOut & BOTTOM) { // punktet er under klipperektangelet
x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
y = ymin;
} else if (outcodeOut & RIGHT) {  // punktet er til høyre for klipperektangelet
y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
x = xmax;
} else if (outcodeOut & LEFT) {   // punktet er til venstre for klipperektangelet
y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
x = xmin;
}

// Nå flyttes punktet på utsiden inn til krysningspunktet for å klippe
// og klargjøre for neste utregning.
if (outcodeOut == outcode0) {
x0 = x;
y0 = y;
outcode0 = ComputeOutCode(x0, y0);
} else {
x1 = x;
y1 = y;
outcode1 = ComputeOutCode(x1, y1);
}
}
}
if (accept) {
               // Følgende funksjoner er utelatt, og må implementeres basert
               // på brukerens plattform (OpenGL/graphics.h osv.)
               DrawRectangle(xmin, ymin, xmax, ymax);
               LineSegment(x0, y0, x1, y1);
}}