If I have two rectangles whose positions are deifned using two 2D vectors (i.e. top left, bottom right) how can I check for the points they are intersecting?
Add a comment
|
4 Answers
I assume you actually want the result of the intersection, not only the test if both rectangles intersect.
The intersection of rect1 = (l1, t1, r1, b1) and rect2 = (l2, t2, r2, b2) is again a rectangle:
rectIntersection = ( max(l1, l2), max(t1, t2), min(r1, r2), min(b1, b2) )
rectIntersection is of course empty if left >= right || top >= bottom assuming a rectangle is left/top-inclusive and right/bottom-exclusive.
The rectangles intersect if
l1 < r2 && l2<r1 && t1<b2 && t2<t1
7 Comments
Andreas Brinck
The separating axis versions are more efficient, this version means you'll always have to do four comparisions.
Andreas Brinck
+ You'll have to do at least one extra test to see if the resulting rect is empty. That means this version is 5-6 conditionals compared to 1-4 for SAT-version.
Sebastian
I do think the poster actually wants the resulting set of intersecting points and not only the test if both intersect. Depending on the context, it may be better to calculate the intersection and assert it is not empty.
Charles Beattie
Quite often code is faster on modern processors if you don't branch. Max and Min often turn into fsel. So there is no code branching in the above seudo code. The only real answer is to profile of course.
Andreas Brinck
Sorry for not reading the question properly, does the Intel processors really have
fsel, I thought this was a PPC/CELL instruction? (Visual Studio 2008 generates branching code for a < b ? a : b) |
Assuming the origin is on left-top of the screen.
If Check if the the top left of one rectangle (x3,y3) is lesser than the bottom right of another rectangle (x2,y2) then the two are intersecting.
The points are (x2,|y2-y3|) and (|x2-x3|,y2).
This is for a rectangle1 and reactangle2 to the right of rectangle1.
Apply inverse to the left translation.
Comments
Two rectangles overlap is there is at least one interior point X,Y common to both. Let the first rectable be {T1, L1, B1, R1} and the second {T2, L2, B2, R2} (top, left, bottom, right). Now it follows that (X>L1) and (X<R1) and (Y>T1) and (Y<B1), and similarly for rectangle 2. From (X>L1) and (X<R2) it follows that (L1<R2). Similarly, (L2<R1), (T1<B2) and (T2<B1).
These 4 conditions are thus necessary. It's not directly obvious that they are also sufficient, but that too is the case.
Comments
If you are interested more to a function to do the job, than to implement an algorithm,
check out IntersectRect Function on Windows.
answered Dec 4, 2009 at 10:18
Nick Dandoulakis
43.3k17 gold badges106 silver badges139 bronze badges