Solved

Rectangle intersection

Posted on 2004-09-25
9
4,669 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 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

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
Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

 
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

Does Powershell have you tied up in knots?

Managing Active Directory does not always have to be complicated.  If you are spending more time trying instead of doing, then it's time to look at something else. For nearly 20 years, AD admins around the world have used one tool for day-to-day AD management: Hyena. Discover why

Question has a verified solution.

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

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…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

808 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