Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Rectangle intersection

Reply
Thread Tools

Rectangle intersection

 
 
kimos
Guest
Posts: n/a
 
      09-25-2004
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?
 
Reply With Quote
 
 
 
 
Joona I Palaste
Guest
Posts: n/a
 
      09-25-2004
kimos <(E-Mail Removed)> scribbled the following:
> 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?


Which part are you having trouble with, calculating the intersection's
coordinates or implementing the algorithm as a C program?

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"Immanuel Kant but Genghis Khan."
- The Official Graffitist's Handbook
 
Reply With Quote
 
 
 
 
Malcolm
Guest
Posts: n/a
 
      09-25-2004

"kimos" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) m...
> 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?
>


Rectangle intersection(Rectangle r1, Rectangle r2)
{
Find the leftmost and the bottommost rectangle.
Find the rightmost and the topmost rectangle.

If the left x co-ordinate of the non-leftmost rectangle is between the
left and the right of the leftmost rectangle, you have the left cordinate of
your intersection. If it is to the right you have no intersection, and the
rectangles don't overlap. (If it is to the left you didn't calculate the
leftmost rectangle correctly).

Repeat for all the other coordinates (bottom, right, top).
}


 
Reply With Quote
 
Simon Stienen
Guest
Posts: n/a
 
      09-25-2004
kimos <(E-Mail Removed)> wrote:
> hi all,
>
> how to calculate the intersection of 2 rectangle


Take the rightmost left-border, the left-most right border, the bottom-most
top border and the top-most bottom border as borders for your intersection.
If the left border of the intersection is on the right of the right border
ot the top border below the bottom border, there is no intersection.
--
Simon Stienen <http://dangerouscat.net> <http://slashlife.de>
»What you do in this world is a matter of no consequence,
The question is, what can you make people believe that you have done.«
-- Sherlock Holmes in "A Study in Scarlet" by Sir Arthur Conan Doyle
 
Reply With Quote
 
SM Ryan
Guest
Posts: n/a
 
      09-25-2004
# this should return the intersection of the 2 rectangles
# anyone can help me plz?

Take two pieces of paper, overlay them, and think about you're looking at. Hint:
the intersection is either empty, a point, or a rectangle.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
OOOOOOOOOO! NAVY SEALS!
 
Reply With Quote
 
xarax
Guest
Posts: n/a
 
      09-25-2004

"SM Ryan" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> # this should return the intersection of the 2 rectangles
> # anyone can help me plz?
>
> Take two pieces of paper, overlay them, and think about you're looking at.

Hint:
> the intersection is either empty, a point, or a rectangle.


Or two points forming a line segment (the
rectangles share some part of a border).


 
Reply With Quote
 
Derrick Coetzee
Guest
Posts: n/a
 
      09-25-2004
kimos wrote:
> how to calculate the intersection of 2 rectangle


The easiest way to think about this problem conceptually is to first
come up with an algorithm for the 1D version, intersecting two line
segments, then generalize it.

Suppose we have a line from a to b and a line from c to d. There are
four cases for intersecting them:

a <= b < c <= d : a----b c----d
In this case the intersection is empty.

a <= b = c <= d : a----b/c----d
In this case the intersection is the single point b=c (the line segment
from b to b.)

a <= c <= b <= d : a---c===b---d
In this case the intersection is the line from c to b.

a <= c <= d <= b : a---c===d---b
In this case the intersection is the line from c to d.

If you simply apply these same four cases to the x and y coordinate
ranges of your rectangles separately, the result will be the x and y
coordinate ranges of the intersection of the rectangles.
--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Line intersection detection.... SPG Java 15 11-07-2006 10:02 AM
intersection simulation zaebos@gmail.com Java 6 09-14-2005 06:12 PM
XML Schema spec: Attribute Wildcard Intersection Alain Frisch XML 3 05-03-2005 11:57 AM
ray/triangle intersection in java bob@coolgroups.com Java 1 04-11-2005 01:08 AM
Intersection of Multiple Sets Ryan R. Rosario C++ 1 09-06-2003 12:40 PM



Advertisments