Solved

Rectangle intersection

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

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

 
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

Suggested Solutions

Title # Comments Views Activity
Grammars for C C++ and java 1 122
How do I set up two external hard drives with Acronis True Image? 12 88
Acrinis True image 2 79
delete-remove 14 87
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…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
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 opening and reading files in the C programming language.

809 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