?
Solved

Rectangle intersection

Posted on 2004-09-25
9
Medium Priority
?
4,692 Views
Last Modified: 2012-06-27
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
Comment
Question by:kimos123
  • 2
  • 2
  • 2
  • +2
9 Comments
 
LVL 9

Expert Comment

by:keteracel
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

by:
keteracel earned 500 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

by:Jaime Olivares
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
Worried about phishing attacks?

90% of attacks start with a phish. It’s critical that IT admins and MSSPs have the right security in place to protect their end users from these phishing attacks. Check out our latest feature brief for tips and tricks to keep your employees off a hackers line!

 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12151048
Oops! Too late. Hope still to be useful.
0
 
LVL 5

Expert Comment

by:tzxie2000
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

by:kimos123
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

thanks in advance
0
 
LVL 5

Expert Comment

by:tzxie2000
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

by:kimos123
ID: 12151272
ohh i got it  thanks alot
0
 

Expert Comment

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

Featured Post

What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

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…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

589 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question