Solved

# Rectangle intersection

Posted on 2004-09-25
4,672 Views
hi all,

how to calculate the intersection of 2 rectangle?

a rectangle is the following:

Rectangle makeRectangle (Point lowerLeft, Point upperRight) {

Rectangle r;

r.pt1 = lowerLeft;
r.pt2 = upperRight;
return r;
}

and Point is the following:

Point makePoint(int x, int y) {
Point p;
p.x = x;
p.y = y;
return p;
}

And i want the know how to make:

Rectangle intersection(Rectangle r1, Rectangle r2)

this should return the intersection of the 2 rectangles
anyone can help me plz?

i am not good in math
0
Question by:kimos123
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 2
• 2
• 2
• +2

LVL 9

Expert Comment

ID: 12150960
Rectangle intersection (Rectangle r1, Rectangle r2)
{
int intLeft = 0, intBottom = 0, intRight = 0, intTop = 0;
int emptyIntersection = 0;

// check on horizontal overlap
if (r1.pt1.x <= r2.pt1.x)
{
intLeft = r2.pt1.x;

if (r1.pt2.x < r2.pt1.x)
emptyIntersection = 1;
else
intRight = (r1.pt2.x < r2.pt2.x)?r1.pt2.x:r2.pt2.x;
}
else
{
intLeft = r1.pt1.x;
if (r2.pt2.x< r1.pt1.x)
emptyIntersection = 1;
else
intRight = (r1.pt2.x < r2.pt2.x)?r1.pt2.x:r2.pt2.x;
}

// check on vertical overlap
if (r1.pt1.y<= r2.pt1.y)
{
intBottom = r2.pt1.y;
if (r1Top < r2.left)
emptyIntersection = 1;
else
intTop = (r1.pt2.y < r2.pt2.y)?r1.pt2.y:r2.pt2.y;
}
else
{
intBottom = r1.pt1.y;
if (r2.pt2.y< r1.pt1.x)
emptyIntersection = 1;
else
intTop = (r1.pt2.y < r2.pt2.y)?r1.pt2.y:r2.pt2.y;
}

if (emptyIntersection)
intLeft = intBottom = intTop = intRight = 0;

return makeRectangle(makePoint(intLeft,intBottom),makePoint(intRight, intTop));
}

0

LVL 9

Accepted Solution

keteracel earned 125 total points
ID: 12150966
oops... couple of wrong things....

Rectangle intersection (Rectangle r1, Rectangle r2)
{
int intLeft = 0, intBottom = 0, intRight = 0, intTop = 0;
int emptyIntersection = 0;

// check on horizontal overlap
if (r1.pt1.x <= r2.pt1.x)
{
intLeft = r2.pt1.x;

if (r1.pt2.x < r2.pt1.x)
emptyIntersection = 1;
else
intRight = (r1.pt2.x < r2.pt2.x)?r1.pt2.x:r2.pt2.x;
}
else
{
intLeft = r1.pt1.x;
if (r2.pt2.x< r1.pt1.x)
emptyIntersection = 1;
else
intRight = (r1.pt2.x < r2.pt2.x)?r1.pt2.x:r2.pt2.x;
}

// check on vertical overlap
if (r1.pt1.y<= r2.pt1.y)
{
intBottom = r2.pt1.y;
if (r1.pt2.y < r2.pt1.x)
emptyIntersection = 1;
else
intTop = (r1.pt2.y < r2.pt2.y)?r1.pt2.y:r2.pt2.y;
}
else
{
intBottom = r1.pt1.y;
if (r2.pt2.y< r1.pt1.x)
emptyIntersection = 1;
else
intTop = (r1.pt2.y < r2.pt2.y)?r1.pt2.y:r2.pt2.y;
}

if (emptyIntersection)
intLeft = intBottom = intTop = intRight = 0;

return makeRectangle(makePoint(intLeft,intBottom),makePoint(intRight, intTop));
}

0

LVL 55

Expert Comment

ID: 12151045
First of all, you must ensure your rentangles are normalized, that is pt1.x < pt2.x and pt1.y < pt2.y

Second, you can make a helper macro

#define BETWEEN(n, nmin, nmax) ((n>nmin)&&(n>nmax))

Here is the function, writting from my memory please check carefully, drawing in a paper all possible cases

Rectangle insersection(Rectangle r1, Rectangle r2)
{
CRectangle r;   // I expect to be empty

/* Test if rectangle overlaps, if not return empty Rectangle */

if((BETWEEN(r2.pt1.x,r1.pt1.x,r1.pt2.x) && BETWEEN(r2.pt1.y,r1.pt1.y,r1.pt2.y) ||
(BETWEEN(r2.pt2.x,r1.pt1.x,r1.pt2.x) && BETWEEN(r2.pt2.y,r1.pt1.y,r1.pt2.y) ||
(BETWEEN(r2.pt1.x,r1.pt1.x,r1.pt2.x) && BETWEEN(r2.pt2.y,r1.pt1.y,r1.pt2.y) ||
(BETWEEN(r2.pt2.x,r1.pt1.x,r1.pt2.x) && BETWEEN(r2.pt1.y,r1.pt1.y,r1.pt2.y) ) {

r.MakeRectangle(
MakePoint(max(r1.pt1.x, r2.pt1.x), max(r1.pt1.y, r2.pt1.y),
MakePoint(min(r1.pt2.x, r2.pt2.x), max(r1.pt2.y, r2.pt2.y),
);
}

return r;
}
0

LVL 55

Expert Comment

ID: 12151048
Oops! Too late. Hope still to be useful.
0

LVL 5

Expert Comment

ID: 12151069
may be simple

Rectangle intersection (Rectangle r1, Rectangle r2)
{
int x[4],y[4];
int i,j,temp;

x[0]=r1.pt1.x;
x[1]=r1.pt2.x;
x[2]=r2.pt1.x;
x[3]=r2.pt2.x;

y[0]=r1.pt1.y;
y[1]=r1.pt2.y;
y[2]=r2.pt1.y;
y[3]=r2.pt2.y;

for(i=0;i<3;i--)
for(j=0;j<3-i;j++)
{
if(x[j]>x[j+1])
{
temp=x[j];
x[j]=x[j+1];
x[j+1]=temp;
}
if(y[j]>y[j+1])
{
temp=y[j];
y[j]=y[j+1];
y[j+1]=temp;
}
}
return makeRectangle(makePoint(x[1],y[1]),makePoint(x[2],y[2]));
}
0

Author Comment

ID: 12151165
ohh sorry guys i didnt refeshed my page and saw only the first answer of keteracel   and i accepted it becouse its good.   i should had spiltted the points...

anyways thanks for the reactions  but one thing i still dont know what is intersection of 2 rectangels  ?   can someone explane it to me  in english not in C plz
the C code is working thanks to u

0

LVL 5

Expert Comment

ID: 12151177
you can use two book and place them together but not just one on another. the part with two book is intersection
0

Author Comment

ID: 12151272
ohh i got it  thanks alot
0

Expert Comment

ID: 15107418
return (x1 < x2 + width2) && (y1 < y2 + height2) &&
(x1 + width1 > x2) && (y1 + height1 > y2);
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

### Suggested Solutions

Test against App 49 139
Console based application in Linux 1 104
nested if statement in excel help 4 48
MySQL recovery 7 56
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ouā¦
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallā¦
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
###### Suggested Courses
Course of the Month8 days, 7 hours left to enroll