# Clipping 2d lines on a boundry rectangle

This topic is 4848 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

if i have the starting and ending coords of a 2d line . and im trying to know if ANY part of this line pass inside the boundry of my ClientRect , to mark that line as Should Draw. but i need to do this with minimum resources. so can anyone help ?

##### Share on other sites
You can use a line clipping routine to get this done. The function below will return 1 if any part of the line is visible, and 0 if not. Pass in your end-points and the client rectangle.

int is_line_visible(int x0, int y0, int x1, int y1, RECT r)
{
if ( y0 > y1 ) {
x0 ^= x1; x1 ^= x0; x0 ^= x1;
y0 ^= y1; y1 ^= y0; y0 ^= y1;
}
if (y0 < r.top) {
if (y1 < r.top) return 0;
x0 += (int)floor((float)(x1 - x0) * (float)(r.top - y0) / (float)(y1 - y0));
y0 = r.top;
}
if (y1 > r.bottom) {
if (y0 > r.bottom) return 0;
x1 += (int)floor((float)(x0 - x1) * (float)(r.bottom - y1)/(float)(y0 - y1));
y1 = r.bottom;
}
if (x0 < r.left) {
if (x1 < r.left) return 0;
y0 += (int)floor((float)(y1 - y0) * (float)(r.left - x0)/(float)(x1 - x0));
x0 = r.left;
}
else
if (x1 < r.left) {
y1 += (int)floor((float)(y0 - y1) * (float)(r.left - x1)/(float)(x0 - x1));
x1 = r.left;
}
if (x1 > r.right) {
if (x0 > r.right) return 0;
y1 += (int)floor((float)(y0 - y1) * (float)(r.right - x1)/(float)(x0 - x1));
x1 = r.right;
}
else
if (x0 > r.right) {
y0 += (int)floor((float)(y1 - y0) * (float)(r.right - x0)/(float)(x1 - x0));
x0 = r.right;
}
return 1;
}

##### Share on other sites
Your rectangle has it upper corner at (u, v), and it dimensions are (w, h)

For each point of your line (2 points I guess :) ), you will compute the number :
mnA = magicNumber(xa, ya);
mnB = magicNumber(xb, yb);

where magicNumber(x, y, u, v, w, h) is :

int
magicNumber(x, y, u, v, w, h) {
int result = 0;

if (y < v)
result |= 1;

if (x >= u + w)
result |= 2;

if (y >= v + h)
result |= 4;

if (x < u)
result |= 8;

return result;
}

So now, if (nmA & nmB) != 0, your line is very probably in your rectangle.
Else, it's sure it is not in your rectangle. It's a very cheap and simple test.

##### Share on other sites

A good description of the classic Cohen Sutherland algorithm is here:
http://www.cs.brown.edu/courses/cs123/lectures/Clipping.pdf

A Java demonstration of the Cohen Sutherland algorithm:
http://graphics.lcs.mit.edu/classes/6.837/F99/assignment2/CohenSutherland.html

Documentation of 3 different algorithms:
http://www.cis.ohio-state.edu/~hwshen/681/0118.pdf

##### Share on other sites
thnx alot for your help guys, and Marmakoide your MagicNumber algorithm is really cheap, and very efficient. there was small syntax error though:

"if (nmA & nmB) != 0, your line is very probably in your rectangle"

that should be "(nmA & nmB) = 0" .. not '!= 0'
but ive got the point ;)

##### Share on other sites
Nice it helps you :)

##### Share on other sites
Very nice function, Marmakoide. Are you the author? I couldn't get it to conflict with my line-clipping routine, so I'm going to use this function to cull off-screen lines just before clipping. Should save some time.

##### Share on other sites
No, it's not mine. This idea is from Cohen and Sutherland, with their clipping algorithms. When they found this nice trick, I wasn't born ;)

It's here :
http://www.cs.brown.edu/courses/cs123/lectures/Clipping.pdf

1. 1
Rutin
49
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633410
• Total Posts
3011723
• ### Who's Online (See full list)

There are no registered users currently online

×