Descripción : – En este algoritmo, se nos dan 9 regiones en la pantalla. De las cuales una región es de la ventana y las 8 regiones restantes están a su alrededor dadas por un binario de 4 dígitos. La división de las regiones se basa en (x_max, y_max) y (x_min, y_min).
La parte central es la región o ventana de visualización, todas las líneas que se encuentran dentro de esta región son completamente visibles. Siempre se asigna un código de región a los extremos de la línea dada.
C++
// C++ program to implement Cohen Sutherland algorithm
// for line clipping.
#include <iostream>
using namespace std;
// Defining region codes
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
// Defining x_max, y_max and x_min, y_min for
// clipping rectangle. Since diagonal points are
// enough to define a rectangle
const int x_max = 10;
const int y_max = 8;
const int x_min = 4;
const int y_min = 4;
// Function to compute region code for a point(x, y)
int computeCode(double x, double y)
{
// initialized as being inside
int code = INSIDE;
if (x < x_min) // to the left of rectangle
code |= LEFT;
else if (x > x_max) // to the right of rectangle
code |= RIGHT;
if (y < y_min) // below the rectangle
code |= BOTTOM;
else if (y > y_max) // above the rectangle
code |= TOP;
return code;
}
// Implementing Cohen-Sutherland algorithm
// Clipping a line from P1 = (x2, y2) to P2 = (x2, y2)
void cohenSutherlandClip(double x1, double y1,
double x2, double y2)
{
// Compute region codes for P1, P2
int code1 = computeCode(x1, y1);
int code2 = computeCode(x2, y2);
// Initialize line as outside the rectangular window
bool accept = false;
while (true) {
if ((code1 == 0) && (code2 == 0)) {
// If both endpoints lie within rectangle
accept = true;
break;
}
else if (code1 & code2) {
// If both endpoints are outside rectangle,
// in same region
break;
}
else {
// Some segment of line lies within the
// rectangle
int code_out;
double x, y;
// At least one endpoint is outside the
// rectangle, pick it.
if (code1 != 0)
code_out = code1;
else
code_out = code2;
// Find intersection point;
// using formulas y = y1 + slope * (x - x1),
// x = x1 + (1 / slope) * (y - y1)
if (code_out & TOP) {
// point is above the clip rectangle
x = x1 + (x2 - x1) * (y_max - y1) / (y2 - y1);
y = y_max;
}
else if (code_out & BOTTOM) {
// point is below the rectangle
x = x1 + (x2 - x1) * (y_min - y1) / (y2 - y1);
y = y_min;
}
else if (code_out & RIGHT) {
// point is to the right of rectangle
y = y1 + (y2 - y1) * (x_max - x1) / (x2 - x1);
x = x_max;
}
else if (code_out & LEFT) {
// point is to the left of rectangle
y = y1 + (y2 - y1) * (x_min - x1) / (x2 - x1);
x = x_min;
}
// Now intersection point x, y is found
// We replace point outside rectangle
// by intersection point
if (code_out == code1) {
x1 = x;
y1 = y;
code1 = computeCode(x1, y1);
}
else {
x2 = x;
y2 = y;
code2 = computeCode(x2, y2);
}
}
}
if (accept) {
cout << "Line accepted from " << x1 << ", "
<< y1 << " to " << x2 << ", " << y2 << endl;
// Here the user can add code to display the rectangle
// along with the accepted (portion of) lines
}
else
cout << "Line rejected" << endl;
}
// Driver code
int main()
{
// First Line segment
// P11 = (5, 5), P12 = (7, 7)
cohenSutherlandClip(5, 5, 7, 7);
// Second Line segment
// P21 = (7, 9), P22 = (11, 4)
cohenSutherlandClip(7, 9, 11, 4);
// Third Line segment
// P31 = (1, 5), P32 = (4, 1)
cohenSutherlandClip(1, 5, 4, 1);
return 0;
}
Python3
# Python program to implement Cohen Sutherland algorithm
# for line clipping.
# Defining region codes
INSIDE = 0 # 0000
LEFT = 1 # 0001
RIGHT = 2 # 0010
BOTTOM = 4 # 0100
TOP = 8 # 1000
# Defining x_max, y_max and x_min, y_min for rectangle
# Since diagonal points are enough to define a rectangle
x_max = 10.0
y_max = 8.0
x_min = 4.0
y_min = 4.0
# Function to compute region code for a point(x, y)
def computeCode(x, y):
code = INSIDE
if x < x_min: # to the left of rectangle
code |= LEFT
else if x > x_max: # to the right of rectangle
code |= RIGHT
if y < y_min: # below the rectangle
code |= BOTTOM
else if y > y_max: # above the rectangle
code |= TOP
return code
# Implementing Cohen-Sutherland algorithm
# Clipping a line from P1 = (x1, y1) to P2 = (x2, y2)
def cohenSutherlandClip(x1, y1, x2, y2):
# Compute region codes for P1, P2
code1 = computeCode(x1, y1)
code2 = computeCode(x2, y2)
accept = False
while True:
# If both endpoints lie within rectangle
if code1 == 0 and code2 == 0:
accept = True
break
# If both endpoints are outside rectangle
else if (code1 & code2) != 0:
break
# Some segment lies within the rectangle
else:
# Line Needs clipping
# At least one of the points is outside,
# select it
x = 1.0
y = 1.0
if code1 != 0:
code_out = code1
else:
code_out = code2
# Find intersection point
# using formulas y = y1 + slope * (x - x1),
# x = x1 + (1 / slope) * (y - y1)
if code_out & TOP:
# point is above the clip rectangle
x = x1 + (x2 - x1) * \
(y_max - y1) / (y2 - y1)
y = y_max
else if code_out & BOTTOM:
# point is below the clip rectangle
x = x1 + (x2 - x1) * \
(y_min - y1) / (y2 - y1)
y = y_min
else if code_out & RIGHT:
# point is to the right of the clip rectangle
y = y1 + (y2 - y1) * \
(x_max - x1) / (x2 - x1)
x = x_max
else if code_out & LEFT:
# point is to the left of the clip rectangle
y = y1 + (y2 - y1) * \
(x_min - x1) / (x2 - x1)
x = x_min
# Now intersection point x, y is found
# We replace point outside clipping rectangle
# by intersection point
if code_out == code1:
x1 = x
y1 = y
code1 = computeCode(x1, y1)
else:
x2 = x
y2 = y
code2 = computeCode(x2, y2)
if accept:
print ("Line accepted from %.2f, %.2f to %.2f, %.2f" % (x1, y1, x2, y2))
# Here the user can add code to display the rectangle
# along with the accepted (portion of) lines
else:
print("Line rejected")
# Driver Script
# First Line segment
# P11 = (5, 5), P12 = (7, 7)
cohenSutherlandClip(5, 5, 7, 7)
# Second Line segment
# P21 = (7, 9), P22 = (11, 4)
cohenSutherlandClip(7, 9, 11, 4)
# Third Line segment
# P31 = (1, 5), P32 = (4, 1)
cohenSutherlandClip(1, 5, 4, 1)
Javascript
// JavaScript program to implement Cohen Sutherland algorithm
// for line clipping.
// Defining region codes
const INSIDE = 0; // 0000
const LEFT = 1; // 0001
const RIGHT = 2; // 0010
const BOTTOM = 4; // 0100
const TOP = 8; // 1000
// Defining x_max, y_max and x_min, y_min for
// clipping rectangle. Since diagonal points are
// enough to define a rectangle
const x_max = 10;
const y_max = 8;
const x_min = 4;
const y_min = 4;
// Function to compute region code for a point(x, y)
function computeCode(x, y)
{
// initialized as being inside
let code = INSIDE;
if (x < x_min) // to the left of rectangle
code |= LEFT;
else if (x > x_max) // to the right of rectangle
code |= RIGHT;
if (y < y_min) // below the rectangle
code |= BOTTOM;
else if (y > y_max) // above the rectangle
code |= TOP;
return code;
}
// Implementing Cohen-Sutherland algorithm
// Clipping a line from P1 = (x2, y2) to P2 = (x2, y2)
function cohenSutherlandClip(x1, y1, x2, y2)
{
// Compute region codes for P1, P2
let code1 = computeCode(x1, y1);
let code2 = computeCode(x2, y2);
// Initialize line as outside the rectangular window
let accept = false;
while (true) {
if ((code1 == 0) && (code2 == 0)) {
// If both endpoints lie within rectangle
accept = true;
break;
}
else if (code1 & code2) {
// If both endpoints are outside rectangle,
// in same region
break;
}
else {
// Some segment of line lies within the
// rectangle
let code_out;
let x, y;
// At least one endpoint is outside the
// rectangle, pick it.
if (code1 != 0)
code_out = code1;
else
code_out = code2;
// Find intersection point;
// using formulas y = y1 + slope * (x - x1),
// x = x1 + (1 / slope) * (y - y1)
if (code_out & TOP) {
// point is above the clip rectangle
x = x1 + (x2 - x1) * (y_max - y1) / (y2 - y1);
y = y_max;
}
else if (code_out & BOTTOM) {
// point is below the rectangle
x = x1 + (x2 - x1) * (y_min - y1) / (y2 - y1);
y = y_min;
}
else if (code_out & RIGHT) {
// point is to the right of rectangle
y = y1 + (y2 - y1) * (x_max - x1) / (x2 - x1);
x = x_max;
}
else if (code_out & LEFT) {
// point is to the left of rectangle
y = y1 + (y2 - y1) * (x_min - x1) / (x2 - x1);
x = x_min;
}
// Now intersection point x, y is found
// We replace point outside rectangle
// by intersection point
if (code_out == code1) {
x1 = x;
y1 = y;
code1 = computeCode(x1, y1);
}
else {
x2 = x;
y2 = y;
code2 = computeCode(x2, y2);
}
}
}
if (accept) {
console.log("Line accepted from", x1, ",", y1, "to", x2, ",", y2);
// Here the user can add code to display the rectangle
// along with the accepted (portion of) lines
}
else
console.log("Line rejected");
}
// Driver code
// First Line segment
// P11 = (5, 5), P12 = (7, 7)
cohenSutherlandClip(5, 5, 7, 7);
// Second Line segment
// P21 = (7, 9), P22 = (11, 4)
cohenSutherlandClip(7, 9, 11, 4);
// Third Line segment
// P31 = (1, 5), P32 = (4, 1)
cohenSutherlandClip(1, 5, 4, 1);
// The code is contributed by Nidhi goel
C++
// C++ program to implement Cohen Sutherland algorithm
// for line clipping.
// including libraries
#include <bits/stdc++.h>
#include <graphics.h>
using namespace std;
// Global Variables
int xmin, xmax, ymin, ymax;
// Lines where co-ordinates are (x1, y1) and (x2, y2)
struct lines {
int x1, y1, x2, y2;
};
// This will return the sign required.
int sign(int x)
{
if (x > 0)
return 1;
else
return 0;
}
// CohenSutherLand LineClipping Algorithm As Described in theory.
// This will clip the lines as per window boundaries.
void clip(struct lines mylines)
{
// arrays will store bits
// Here bits implies initial Point whereas bite implies end points
int bits[4], bite[4], i, var;
// setting color of graphics to be RED
setcolor(RED);
// Finding Bits
bits[0] = sign(xmin - mylines.x1);
bite[0] = sign(xmin - mylines.x2);
bits[1] = sign(mylines.x1 - xmax);
bite[1] = sign(mylines.x2 - xmax);
bits[2] = sign(ymin - mylines.y1);
bite[2] = sign(ymin - mylines.y2);
bits[3] = sign(mylines.y1 - ymax);
bite[3] = sign(mylines.y2 - ymax);
// initial will used for initial coordinates and end for final
string initial = "", end = "", temp = "";
// convert bits to string
for (i = 0; i < 4; i++) {
if (bits[i] == 0)
initial += '0';
else
initial += '1';
}
for (i = 0; i < 4; i++) {
if (bite[i] == 0)
end += '0';
else
end += '1';
}
// finding slope of line y=mx+c as (y-y1)=m(x-x1)+c
// where m is slope m=dy/dx;
float m = (mylines.y2 - mylines.y1) / (float)(mylines.x2 - mylines.x1);
float c = mylines.y1 - m * mylines.x1;
// if both points are inside the Accept the line and draw
if (initial == end && end == "0000") {
// inbuild function to draw the line from(x1, y1) to (x2, y2)
line(mylines.x1, mylines.y1, mylines.x2, mylines.y2);
return;
}
// this will contain cases where line maybe totally outside for partially inside
else {
// taking bitwise end of every value
for (i = 0; i < 4; i++) {
int val = (bits[i] & bite[i]);
if (val == 0)
temp += '0';
else
temp += '1';
}
// as per algo if AND is not 0000 means line is completely outside hence draw nothing and return
if (temp != "0000")
return;
// Here contain cases of partial inside or outside
// So check for every boundary one by one
for (i = 0; i < 4; i++) {
// if boths bit are same hence we cannot find any intersection with boundary so continue
if (bits[i] == bite[i])
continue;
// Otherwise there exist a intersection
// Case when initial point is in left xmin
if (i == 0 && bits[i] == 1) {
var = round(m * xmin + c);
mylines.y1 = var;
mylines.x1 = xmin;
}
// Case when final point is in left xmin
if (i == 0 && bite[i] == 1) {
var = round(m * xmin + c);
mylines.y2 = var;
mylines.x2 = xmin;
}
// Case when initial point is in right of xmax
if (i == 1 && bits[i] == 1) {
var = round(m * xmax + c);
mylines.y1 = var;
mylines.x1 = xmax;
}
// Case when final point is in right of xmax
if (i == 1 && bite[i] == 1) {
var = round(m * xmax + c);
mylines.y2 = var;
mylines.x2 = xmax;
}
// Case when initial point is in top of ymin
if (i == 2 && bits[i] == 1) {
var = round((float)(ymin - c) / m);
mylines.y1 = ymin;
mylines.x1 = var;
}
// Case when final point is in top of ymin
if (i == 2 && bite[i] == 1) {
var = round((float)(ymin - c) / m);
mylines.y2 = ymin;
mylines.x2 = var;
}
// Case when initial point is in bottom of ymax
if (i == 3 && bits[i] == 1) {
var = round((float)(ymax - c) / m);
mylines.y1 = ymax;
mylines.x1 = var;
}
// Case when final point is in bottom of ymax
if (i == 3 && bite[i] == 1) {
var = round((float)(ymax - c) / m);
mylines.y2 = ymax;
mylines.x2 = var;
}
// Updating Bits at every point
bits[0] = sign(xmin - mylines.x1);
bite[0] = sign(xmin - mylines.x2);
bits[1] = sign(mylines.x1 - xmax);
bite[1] = sign(mylines.x2 - xmax);
bits[2] = sign(ymin - mylines.y1);
bite[2] = sign(ymin - mylines.y2);
bits[3] = sign(mylines.y1 - ymax);
bite[3] = sign(mylines.y2 - ymax);
} // end of for loop
// Initialize initial and end to NULL
initial = "", end = "";
// Updating strings again by bit
for (i = 0; i < 4; i++) {
if (bits[i] == 0)
initial += '0';
else
initial += '1';
}
for (i = 0; i < 4; i++) {
if (bite[i] == 0)
end += '0';
else
end += '1';
}
// If now both points lie inside or on boundary then simply draw the updated line
if (initial == end && end == "0000") {
line(mylines.x1, mylines.y1, mylines.x2, mylines.y2);
return;
}
// else line was completely outside hence rejected
else
return;
}
}
// Driver Function
int main()
{
int gd = DETECT, gm;
// Setting values of Clipping window
xmin = 40;
xmax = 100;
ymin = 40;
ymax = 80;
// initialize the graph
initgraph(&gd, &gm, NULL);
// Drawing Window using Lines
line(xmin, ymin, xmax, ymin);
line(xmax, ymin, xmax, ymax);
line(xmax, ymax, xmin, ymax);
line(xmin, ymax, xmin, ymin);
// Assume 4 lines to be clipped
struct lines mylines[4];
// Setting the coordinated of 4 lines
mylines[0].x1 = 30;
mylines[0].y1 = 65;
mylines[0].x2 = 55;
mylines[0].y2 = 30;
mylines[1].x1 = 60;
mylines[1].y1 = 20;
mylines[1].x2 = 100;
mylines[1].y2 = 90;
mylines[2].x1 = 60;
mylines[2].y1 = 100;
mylines[2].x2 = 80;
mylines[2].y2 = 70;
mylines[3].x1 = 85;
mylines[3].y1 = 50;
mylines[3].x2 = 120;
mylines[3].y2 = 75;
// Drawing Initial Lines without clipping
for (int i = 0; i < 4; i++) {
line(mylines[i].x1, mylines[i].y1,
mylines[i].x2, mylines[i].y2);
delay(1000);
}
// Drawing clipped Line
for (int i = 0; i < 4; i++) {
// Calling clip() which in term clip the line as per window and draw it
clip(mylines[i]);
delay(1000);
}
delay(4000);
getch();
// For Closing the graph.
closegraph();
return 0;
}
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA