Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.
http://www.geeksforgeeks.org/find-two-rectangles-overlap/
Two rectangles do not overlap if one of the following conditions is true.
1) One rectangle is above top edge of other rectangle.
2) One rectangle is on left side of left edge of other rectangle.
return !( a.ul.x > b.lr.x ||
a.ul.y < b.lr.y ||
a.lr.x < b.ul.x ||
a.lr.y > b.ul.y );
}
boolean overlap( Rect a, Rect b){
return( a.ul.x <= b.lr.x &&
a.ul.y >= b.lr.y &&
a.lr.x >= b.ul.x &&
a.lr.y <= b.ul.y );
}
Given a list of rectangles, how would you determine the set of overlapping rectangles efficiently? Why would this be useful?
Read full article from Determine If Two Rectangles Overlap | LeetCode
http://www.geeksforgeeks.org/find-two-rectangles-overlap/
Two rectangles do not overlap if one of the following conditions is true.
1) One rectangle is above top edge of other rectangle.
2) One rectangle is on left side of left edge of other rectangle.
bool doOverlap(Point l1, Point r1, Point l2, Point r2){ // If one rectangle is on left side of other if (l1.x > r2.x || l2.x > r1.x) return false; // If one rectangle is above other if (l1.y < r2.y || l2.y < r1.y) return false; return true;}
A much easier and better approach would be to think from the opposite. How about asking yourself how the two rectangles cannot overlap each other? Two rectangles do not overlap when one is above/below, or to the left/right of the other rectangle.
The condition’s expression is:
! ( P2.y < P3.y || P1.y > P4.y || P2.x < P3.x || P1.x > P4.x )
Using De Morgan’s law, we can further simplify the above expression to:
boolean overlap( Rect a, Rect b ){
( P2.y ≤ P3.y && P1.y ≥ P4.y && P2.x ≥ P3.x && P1.x ≤ P4.x )
return !( a.ul.x > b.lr.x ||
a.ul.y < b.lr.y ||
a.lr.x < b.ul.x ||
a.lr.y > b.ul.y );
}
boolean overlap( Rect a, Rect b){
return( a.ul.x <= b.lr.x &&
a.ul.y >= b.lr.y &&
a.lr.x >= b.ul.x &&
a.lr.y <= b.ul.y );
}
Given a list of rectangles, how would you determine the set of overlapping rectangles efficiently? Why would this be useful?
Read full article from Determine If Two Rectangles Overlap | LeetCode
