Solved

Rectangle intersection

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

Expert Comment

by:Jaime Olivares
ID: 12151048
Oops! Too late. Hope still to be useful.
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Suggested Solutions

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
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.
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.

708 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

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now