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?
+3
A:
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
tomkaith13
2009-12-04 09:59:24
+1
A:
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.
MSalters
2009-12-04 10:00:42
+3
A:
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
Sebastian
2009-12-04 10:03:35
The separating axis versions are more efficient, this version means you'll always have to do four comparisions.
Andreas Brinck
2009-12-04 10:24:56
+ 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.
Andreas Brinck
2009-12-04 10:26:21
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.
Sebastian
2009-12-04 10:40:35
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.
Charles Beattie
2009-12-04 11:11:52
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`)
Andreas Brinck
2009-12-04 11:46:14
Even if `fsel` is not used, modern compiler is fully capable of optimizing such code for you. If you just don't get in its way, that is.Anyway, this solution gives _correct_ results (unlike some others).It can be optimized later if needed.
Tomek Szpakowicz
2009-12-04 13:12:31
Intel has FCMOV*.
Tomek Szpakowicz
2009-12-04 13:20:52
A:
If you are interested more to a function to do the job, than to implement an algorithm,
check out IntersectRect Function on Windows.
Nick D
2009-12-04 10:18:03