I am trying to write a C++ program that takes the following inputs from the user to construct rectangles (between 2 and 5): height, width, x-pos, y-pos. All of these rectangles will exist parallel to the x and the y axis, that is all of their edges will have slopes of 0 or infinity.
I've tried to implement what is mentioned in this question but I am not having very much luck.
My current implementation does the following:
// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2
// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];
int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;
However I'm not quite sure if (a) I've implemented the algorithm I linked to correctly, or if I did exactly how to interpret this?
Any suggestions?
This question is related to
c++
algorithm
geometry
overlap
rectangles
The answer is
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
bool
overlap(const Rect &r1, const Rect &r2)
{
// The rectangles don't overlap if
// one rectangle's minimum in some dimension
// is greater than the other's maximum in
// that dimension.
bool noOverlap = r1.x1 > r2.x2 ||
r2.x1 > r1.x2 ||
r1.y1 > r2.y2 ||
r2.y1 > r1.y2;
return !noOverlap;
}
I have a very easy solution
let x1,y1 x2,y2 ,l1,b1,l2,be cordinates and lengths and breadths of them respectively
consider the condition ((x2
now the only way these rectangle will overlap is if the point diagonal to x1,y1 will lie inside the other rectangle or similarly the point diagonal to x2,y2 will lie inside the other rectangle. which is exactly the above condition implies.
For those of you who are using center points and half sizes for their rectangle data, instead of the typical x,y,w,h, or x0,y0,x1,x1, here's how you can do it:
#include <cmath> // for fabsf(float)
struct Rectangle
{
float centerX, centerY, halfWidth, halfHeight;
};
bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b)
{
return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) &&
(fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight));
}
A and B be two rectangle. C be their covering rectangle.
four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom)
four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom)
A.width = abs(xAleft-xAright);
A.height = abs(yAleft-yAright);
B.width = abs(xBleft-xBright);
B.height = abs(yBleft-yBright);
C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright);
C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom);
A and B does not overlap if
(C.width >= A.width + B.width )
OR
(C.height >= A.height + B.height)
It takes care all possible cases.
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
r1.y1 < r2.y2 && r2.x1 < r1.y2;
}
//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}
In the question, you link to the maths for when rectangles are at arbitrary angles of rotation. If I understand the bit about angles in the question however, I interpret that all rectangles are perpendicular to one another.
A general knowing the area of overlap formula is:
Using the example:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates
1 3 4 5 6
2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates
1 2 3 4 6
3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates.
4 * 4
4) paint all the rectangles into this grid, incrementing the count of each cell it occurs over:
1 3 4 5 6
1 +---+
| 1 | 0 0 0
2 +---+---+---+
| 1 | 1 | 1 | 0
3 +---+---+---+---+
| 1 | 1 | 2 | 1 |
4 +---+---+---+---+
0 0 | 1 | 1 |
6 +---+---+
5) As you paint the rectangles, its easy to intercept the overlaps.
Ask yourself the opposite question: How can I determine if two rectangles do not intersect at all? Obviously, a rectangle A completely to the left of rectangle B does not intersect. Also if A is completely to the right. And similarly if A is completely above B or completely below B. In any other case A and B intersect.
What follows may have bugs, but I am pretty confident about the algorithm:
struct Rectangle { int x; int y; int width; int height; };
bool is_left_of(Rectangle const & a, Rectangle const & b) {
if (a.x + a.width <= b.x) return true;
return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
return is_left_of(b, a);
}
bool not_intersect( Rectangle const & a, Rectangle const & b) {
if (is_left_of(a, b)) return true;
if (is_right_of(a, b)) return true;
// Do the same for top/bottom...
}
bool intersect(Rectangle const & a, Rectangle const & b) {
return !not_intersect(a, b);
}
Don't think of coordinates as indicating where pixels are. Think of them as being between the pixels. That way, the area of a 2x2 rectangle should be 4, not 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
Java code to figure out if Rectangles are contacting or overlapping each other
...
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < n; j++ ) {
if ( i != j ) {
Rectangle rectangle1 = rectangles.get(i);
Rectangle rectangle2 = rectangles.get(j);
int l1 = rectangle1.l; //left
int r1 = rectangle1.r; //right
int b1 = rectangle1.b; //bottom
int t1 = rectangle1.t; //top
int l2 = rectangle2.l;
int r2 = rectangle2.r;
int b2 = rectangle2.b;
int t2 = rectangle2.t;
boolean topOnBottom = t2 == b1;
boolean bottomOnTop = b2 == t1;
boolean topOrBottomContact = topOnBottom || bottomOnTop;
boolean rightOnLeft = r2 == l1;
boolean leftOnRight = l2 == r1;
boolean rightOrLeftContact = leftOnRight || rightOnLeft;
boolean leftPoll = l2 <= l1 && r2 >= l1;
boolean rightPoll = l2 <= r1 && r2 >= r1;
boolean leftRightInside = l2 >= l1 && r2 <= r1;
boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside;
boolean bottomPoll = t2 >= b1 && b2 <= b1;
boolean topPoll = b2 <= b1 && t2 >= b1;
boolean topBottomInside = b2 >= b1 && t2 <= t1;
boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside;
boolean topInBetween = t2 > b1 && t2 < t1;
boolean bottomInBetween = b2 > b1 && b2 < t1;
boolean topBottomInBetween = topInBetween || bottomInBetween;
boolean leftInBetween = l2 > l1 && l2 < r1;
boolean rightInBetween = r2 > l1 && r2 < r1;
boolean leftRightInBetween = leftInBetween || rightInBetween;
if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) {
path[i][j] = true;
}
}
}
}
...
I have implemented a C# version, it is easily converted to C++.
public bool Intersects ( Rectangle rect )
{
float ulx = Math.Max ( x, rect.x );
float uly = Math.Max ( y, rect.y );
float lrx = Math.Min ( x + width, rect.x + rect.width );
float lry = Math.Min ( y + height, rect.y + rect.height );
return ulx <= lrx && uly <= lry;
}
Here's how it's done in the Java API:
public boolean intersects(Rectangle r) {
int tw = this.width;
int th = this.height;
int rw = r.width;
int rh = r.height;
if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
return false;
}
int tx = this.x;
int ty = this.y;
int rx = r.x;
int ry = r.y;
rw += rx;
rh += ry;
tw += tx;
th += ty;
// overflow || intersect
return ((rw < rx || rw > tx) &&
(rh < ry || rh > ty) &&
(tw < tx || tw > rx) &&
(th < ty || th > ry));
}
Lets say the two rectangles are rectangle A and rectangle B. Let their centers be A1 and B1 (coordinates of A1 and B1 can be easily found out), let the heights be Ha and Hb, width be Wa and Wb, let dx be the width(x) distance between A1 and B1 and dy be the height(y) distance between A1 and B1.
Now we can say we can say A and B overlap: when
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
r1.y1 < r2.y2 && r2.x1 < r1.y2;
}
//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
bool
overlap(const Rect &r1, const Rect &r2)
{
// The rectangles don't overlap if
// one rectangle's minimum in some dimension
// is greater than the other's maximum in
// that dimension.
bool noOverlap = r1.x1 > r2.x2 ||
r2.x1 > r1.x2 ||
r1.y1 > r2.y2 ||
r2.y1 > r1.y2;
return !noOverlap;
}
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
r1.y1 < r2.y2 && r2.x1 < r1.y2;
}
//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}
A and B be two rectangle. C be their covering rectangle.
four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom)
four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom)
A.width = abs(xAleft-xAright);
A.height = abs(yAleft-yAright);
B.width = abs(xBleft-xBright);
B.height = abs(yBleft-yBright);
C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright);
C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom);
A and B does not overlap if
(C.width >= A.width + B.width )
OR
(C.height >= A.height + B.height)
It takes care all possible cases.
Don't think of coordinates as indicating where pixels are. Think of them as being between the pixels. That way, the area of a 2x2 rectangle should be 4, not 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
r1.y1 < r2.y2 && r2.x1 < r1.y2;
}
//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
bool
overlap(const Rect &r1, const Rect &r2)
{
// The rectangles don't overlap if
// one rectangle's minimum in some dimension
// is greater than the other's maximum in
// that dimension.
bool noOverlap = r1.x1 > r2.x2 ||
r2.x1 > r1.x2 ||
r1.y1 > r2.y2 ||
r2.y1 > r1.y2;
return !noOverlap;
}
"If you perform subtraction x or y coordinates corresponding to the vertices of the two facing each rectangle, if the results are the same sign, the two rectangle do not overlap axes that" (i am sorry, i am not sure my translation is correct)
Source: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
Java code to figure out if Rectangles are contacting or overlapping each other
...
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < n; j++ ) {
if ( i != j ) {
Rectangle rectangle1 = rectangles.get(i);
Rectangle rectangle2 = rectangles.get(j);
int l1 = rectangle1.l; //left
int r1 = rectangle1.r; //right
int b1 = rectangle1.b; //bottom
int t1 = rectangle1.t; //top
int l2 = rectangle2.l;
int r2 = rectangle2.r;
int b2 = rectangle2.b;
int t2 = rectangle2.t;
boolean topOnBottom = t2 == b1;
boolean bottomOnTop = b2 == t1;
boolean topOrBottomContact = topOnBottom || bottomOnTop;
boolean rightOnLeft = r2 == l1;
boolean leftOnRight = l2 == r1;
boolean rightOrLeftContact = leftOnRight || rightOnLeft;
boolean leftPoll = l2 <= l1 && r2 >= l1;
boolean rightPoll = l2 <= r1 && r2 >= r1;
boolean leftRightInside = l2 >= l1 && r2 <= r1;
boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside;
boolean bottomPoll = t2 >= b1 && b2 <= b1;
boolean topPoll = b2 <= b1 && t2 >= b1;
boolean topBottomInside = b2 >= b1 && t2 <= t1;
boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside;
boolean topInBetween = t2 > b1 && t2 < t1;
boolean bottomInBetween = b2 > b1 && b2 < t1;
boolean topBottomInBetween = topInBetween || bottomInBetween;
boolean leftInBetween = l2 > l1 && l2 < r1;
boolean rightInBetween = r2 > l1 && r2 < r1;
boolean leftRightInBetween = leftInBetween || rightInBetween;
if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) {
path[i][j] = true;
}
}
}
}
...
It is easier to check if a rectangle is completly outside the other, so if it is either
on the left...
(r1.x + r1.width < r2.x)
or on the right...
(r1.x > r2.x + r2.width)
or on top...
(r1.y + r1.height < r2.y)
or on the bottom...
(r1.y > r2.y + r2.height)
of the second rectangle, it cannot possibly collide with it. So to have a function that returns a Boolean saying weather the rectangles collide, we simply combine the conditions by logical ORs and negate the result:
function checkOverlap(r1, r2) : Boolean
{
return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}
To already receive a positive result when touching only, we can change the "<" and ">" by "<=" and ">=".
I have implemented a C# version, it is easily converted to C++.
public bool Intersects ( Rectangle rect )
{
float ulx = Math.Max ( x, rect.x );
float uly = Math.Max ( y, rect.y );
float lrx = Math.Min ( x + width, rect.x + rect.width );
float lry = Math.Min ( y + height, rect.y + rect.height );
return ulx <= lrx && uly <= lry;
}
Lets say the two rectangles are rectangle A and rectangle B. Let their centers be A1 and B1 (coordinates of A1 and B1 can be easily found out), let the heights be Ha and Hb, width be Wa and Wb, let dx be the width(x) distance between A1 and B1 and dy be the height(y) distance between A1 and B1.
Now we can say we can say A and B overlap: when
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
Easiest way is
/**
* Check if two rectangles collide
* x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
* x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
*/
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}
first of all put it in to your mind that in computers the coordinates system is upside down. x-axis is same as in mathematics but y-axis increases downwards and decrease on going upward.. if rectangle are drawn from center. if x1 coordinates is greater than x2 plus its its half of widht. then it means going half they will touch each other. and in the same manner going downward + half of its height. it will collide..
I have a very easy solution
let x1,y1 x2,y2 ,l1,b1,l2,be cordinates and lengths and breadths of them respectively
consider the condition ((x2
now the only way these rectangle will overlap is if the point diagonal to x1,y1 will lie inside the other rectangle or similarly the point diagonal to x2,y2 will lie inside the other rectangle. which is exactly the above condition implies.
In the question, you link to the maths for when rectangles are at arbitrary angles of rotation. If I understand the bit about angles in the question however, I interpret that all rectangles are perpendicular to one another.
A general knowing the area of overlap formula is:
Using the example:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates
1 3 4 5 6
2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates
1 2 3 4 6
3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates.
4 * 4
4) paint all the rectangles into this grid, incrementing the count of each cell it occurs over:
1 3 4 5 6
1 +---+
| 1 | 0 0 0
2 +---+---+---+
| 1 | 1 | 1 | 0
3 +---+---+---+---+
| 1 | 1 | 2 | 1 |
4 +---+---+---+---+
0 0 | 1 | 1 |
6 +---+---+
5) As you paint the rectangles, its easy to intercept the overlaps.
struct point { int x, y; };
struct rect { point tl, br; }; // top left and bottom right points
// return true if rectangles overlap
bool overlap(const rect &a, const rect &b)
{
return a.tl.x <= b.br.x && a.br.x >= b.tl.x &&
a.tl.y >= b.br.y && a.br.y <= b.tl.y;
}
Suppose that you have defined the positions and sizes of the rectangles like this:
My C++ implementation is like this:
class Vector2D
{
public:
Vector2D(int x, int y) : x(x), y(y) {}
~Vector2D(){}
int x, y;
};
bool DoRectanglesOverlap( const Vector2D & Pos1,
const Vector2D & Size1,
const Vector2D & Pos2,
const Vector2D & Size2)
{
if ((Pos1.x < Pos2.x + Size2.x) &&
(Pos1.y < Pos2.y + Size2.y) &&
(Pos2.x < Pos1.x + Size1.x) &&
(Pos2.y < Pos1.y + Size1.y))
{
return true;
}
return false;
}
An example function call according to the given figure above:
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
The comparisons inside the if block will look like below:
if ((Pos1.x < Pos2.x + Size2.x) &&
(Pos1.y < Pos2.y + Size2.y) &&
(Pos2.x < Pos1.x + Size1.x) &&
(Pos2.y < Pos1.y + Size1.y))
?
if (( 3 < 6 + 9 ) &&
( 7 < 4 + 4 ) &&
( 6 < 3 + 8 ) &&
( 4 < 7 + 5 ))
struct rect
{
int x;
int y;
int width;
int height;
};
bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }
bool rectOverlap(rect A, rect B)
{
bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width);
bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height);
return xOverlap && yOverlap;
}Ask yourself the opposite question: How can I determine if two rectangles do not intersect at all? Obviously, a rectangle A completely to the left of rectangle B does not intersect. Also if A is completely to the right. And similarly if A is completely above B or completely below B. In any other case A and B intersect.
What follows may have bugs, but I am pretty confident about the algorithm:
struct Rectangle { int x; int y; int width; int height; };
bool is_left_of(Rectangle const & a, Rectangle const & b) {
if (a.x + a.width <= b.x) return true;
return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
return is_left_of(b, a);
}
bool not_intersect( Rectangle const & a, Rectangle const & b) {
if (is_left_of(a, b)) return true;
if (is_right_of(a, b)) return true;
// Do the same for top/bottom...
}
bool intersect(Rectangle const & a, Rectangle const & b) {
return !not_intersect(a, b);
}
Here's how it's done in the Java API:
public boolean intersects(Rectangle r) {
int tw = this.width;
int th = this.height;
int rw = r.width;
int rh = r.height;
if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
return false;
}
int tx = this.x;
int ty = this.y;
int rx = r.x;
int ry = r.y;
rw += rx;
rh += ry;
tw += tx;
th += ty;
// overflow || intersect
return ((rw < rx || rw > tx) &&
(rh < ry || rh > ty) &&
(tw < tx || tw > rx) &&
(th < ty || th > ry));
}
In the question, you link to the maths for when rectangles are at arbitrary angles of rotation. If I understand the bit about angles in the question however, I interpret that all rectangles are perpendicular to one another.
A general knowing the area of overlap formula is:
Using the example:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates
1 3 4 5 6
2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates
1 2 3 4 6
3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates.
4 * 4
4) paint all the rectangles into this grid, incrementing the count of each cell it occurs over:
1 3 4 5 6
1 +---+
| 1 | 0 0 0
2 +---+---+---+
| 1 | 1 | 1 | 0
3 +---+---+---+---+
| 1 | 1 | 2 | 1 |
4 +---+---+---+---+
0 0 | 1 | 1 |
6 +---+---+
5) As you paint the rectangles, its easy to intercept the overlaps.
This is from exercise 3.28 from the book Introduction to Java Programming- Comprehensive Edition. The code tests whether the two rectangles are indenticle, whether one is inside the other and whether one is outside the other. If none of these condition are met then the two overlap.
**3.28 (Geometry: two rectangles) Write a program that prompts the user to enter the center x-, y-coordinates, width, and height of two rectangles and determines whether the second rectangle is inside the first or overlaps with the first, as shown in Figure 3.9. Test your program to cover all cases. Here are the sample runs:
Enter r1's center x-, y-coordinates, width, and height: 2.5 4 2.5 43 Enter r2's center x-, y-coordinates, width, and height: 1.5 5 0.5 3 r2 is inside r1
Enter r1's center x-, y-coordinates, width, and height: 1 2 3 5.5 Enter r2's center x-, y-coordinates, width, and height: 3 4 4.5 5 r2 overlaps r1
Enter r1's center x-, y-coordinates, width, and height: 1 2 3 3 Enter r2's center x-, y-coordinates, width, and height: 40 45 3 2 r2 does not overlap r1
import java.util.Scanner;
public class ProgrammingEx3_28 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out
.print("Enter r1's center x-, y-coordinates, width, and height:");
double x1 = input.nextDouble();
double y1 = input.nextDouble();
double w1 = input.nextDouble();
double h1 = input.nextDouble();
w1 = w1 / 2;
h1 = h1 / 2;
System.out
.print("Enter r2's center x-, y-coordinates, width, and height:");
double x2 = input.nextDouble();
double y2 = input.nextDouble();
double w2 = input.nextDouble();
double h2 = input.nextDouble();
w2 = w2 / 2;
h2 = h2 / 2;
// Calculating range of r1 and r2
double x1max = x1 + w1;
double y1max = y1 + h1;
double x1min = x1 - w1;
double y1min = y1 - h1;
double x2max = x2 + w2;
double y2max = y2 + h2;
double x2min = x2 - w2;
double y2min = y2 - h2;
if (x1max == x2max && x1min == x2min && y1max == y2max
&& y1min == y2min) {
// Check if the two are identicle
System.out.print("r1 and r2 are indentical");
} else if (x1max <= x2max && x1min >= x2min && y1max <= y2max
&& y1min >= y2min) {
// Check if r1 is in r2
System.out.print("r1 is inside r2");
} else if (x2max <= x1max && x2min >= x1min && y2max <= y1max
&& y2min >= y1min) {
// Check if r2 is in r1
System.out.print("r2 is inside r1");
} else if (x1max < x2min || x1min > x2max || y1max < y2min
|| y2min > y1max) {
// Check if the two overlap
System.out.print("r2 does not overlaps r1");
} else {
System.out.print("r2 overlaps r1");
}
}
}
struct rect
{
int x;
int y;
int width;
int height;
};
bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }
bool rectOverlap(rect A, rect B)
{
bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width);
bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height);
return xOverlap && yOverlap;
}It is easier to check if a rectangle is completly outside the other, so if it is either
on the left...
(r1.x + r1.width < r2.x)
or on the right...
(r1.x > r2.x + r2.width)
or on top...
(r1.y + r1.height < r2.y)
or on the bottom...
(r1.y > r2.y + r2.height)
of the second rectangle, it cannot possibly collide with it. So to have a function that returns a Boolean saying weather the rectangles collide, we simply combine the conditions by logical ORs and negate the result:
function checkOverlap(r1, r2) : Boolean
{
return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}
To already receive a positive result when touching only, we can change the "<" and ">" by "<=" and ">=".
struct point { int x, y; };
struct rect { point tl, br; }; // top left and bottom right points
// return true if rectangles overlap
bool overlap(const rect &a, const rect &b)
{
return a.tl.x <= b.br.x && a.br.x >= b.tl.x &&
a.tl.y >= b.br.y && a.br.y <= b.tl.y;
}
This is a very fast way to check with C++ if two rectangles overlap:
return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
&& std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);
It works by calculating the left and right borders of the intersecting rectangle, and then comparing them: if the right border is equal to or less than the left border, it means that the intersection is empty and therefore the rectangles do not overlap; otherwise, it tries again with the top and bottom borders.
What is the advantage of this method over the conventional alternative of 4 comparisons? It's about how modern processors are designed. They have something called branch prediction, which works well when the result of a comparison is always the same, but have a huge performance penalty otherwise. However, in the absence of branch instructions, the CPU performs quite well. By calculating the borders of the intersection instead of having two separate checks for each axis, we're saving two branches, one per pair.
It is possible that the four comparisons method outperforms this one, if the first comparison has a high chance of being false. That is very rare, though, because it means that the second rectangle is most often on the left side of the first rectangle, and not on the right side or overlapping it; and most often, you need to check rectangles on both sides of the first one, which normally voids the advantages of branch prediction.
This method can be improved even more, depending on the expected distribution of rectangles:
- If you expect the checked rectangles to be predominantly to the left or right of each other, then the method above works best. This is probably the case, for example, when you're using the rectangle intersection to check collisions for a game, where the game objects are predominantly distributed horizontally (e.g. a SuperMarioBros-like game).
- If you expect the checked rectangles to be predominantly to the top or bottom of each other, e.g. in an Icy Tower type of game, then checking top/bottom first and left/right last will probably be faster:
return std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom)
&& std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right);
- If the probability of intersecting is close to the probability of not intersecting, however, it's better to have a completely branchless alternative:
return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
& std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);
(Note the change of && to a single &)
"If you perform subtraction x or y coordinates corresponding to the vertices of the two facing each rectangle, if the results are the same sign, the two rectangle do not overlap axes that" (i am sorry, i am not sure my translation is correct)
Source: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
struct rect
{
int x;
int y;
int width;
int height;
};
bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }
bool rectOverlap(rect A, rect B)
{
bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width);
bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height);
return xOverlap && yOverlap;
}I have implemented a C# version, it is easily converted to C++.
public bool Intersects ( Rectangle rect )
{
float ulx = Math.Max ( x, rect.x );
float uly = Math.Max ( y, rect.y );
float lrx = Math.Min ( x + width, rect.x + rect.width );
float lry = Math.Min ( y + height, rect.y + rect.height );
return ulx <= lrx && uly <= lry;
}
Don't think of coordinates as indicating where pixels are. Think of them as being between the pixels. That way, the area of a 2x2 rectangle should be 4, not 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
bool Square::IsOverlappig(Square &other)
{
bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
return result1 | result2 | result3 | result4;
}
Ask yourself the opposite question: How can I determine if two rectangles do not intersect at all? Obviously, a rectangle A completely to the left of rectangle B does not intersect. Also if A is completely to the right. And similarly if A is completely above B or completely below B. In any other case A and B intersect.
What follows may have bugs, but I am pretty confident about the algorithm:
struct Rectangle { int x; int y; int width; int height; };
bool is_left_of(Rectangle const & a, Rectangle const & b) {
if (a.x + a.width <= b.x) return true;
return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
return is_left_of(b, a);
}
bool not_intersect( Rectangle const & a, Rectangle const & b) {
if (is_left_of(a, b)) return true;
if (is_right_of(a, b)) return true;
// Do the same for top/bottom...
}
bool intersect(Rectangle const & a, Rectangle const & b) {
return !not_intersect(a, b);
}
This is a very fast way to check with C++ if two rectangles overlap:
return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
&& std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);
It works by calculating the left and right borders of the intersecting rectangle, and then comparing them: if the right border is equal to or less than the left border, it means that the intersection is empty and therefore the rectangles do not overlap; otherwise, it tries again with the top and bottom borders.
What is the advantage of this method over the conventional alternative of 4 comparisons? It's about how modern processors are designed. They have something called branch prediction, which works well when the result of a comparison is always the same, but have a huge performance penalty otherwise. However, in the absence of branch instructions, the CPU performs quite well. By calculating the borders of the intersection instead of having two separate checks for each axis, we're saving two branches, one per pair.
It is possible that the four comparisons method outperforms this one, if the first comparison has a high chance of being false. That is very rare, though, because it means that the second rectangle is most often on the left side of the first rectangle, and not on the right side or overlapping it; and most often, you need to check rectangles on both sides of the first one, which normally voids the advantages of branch prediction.
This method can be improved even more, depending on the expected distribution of rectangles:
- If you expect the checked rectangles to be predominantly to the left or right of each other, then the method above works best. This is probably the case, for example, when you're using the rectangle intersection to check collisions for a game, where the game objects are predominantly distributed horizontally (e.g. a SuperMarioBros-like game).
- If you expect the checked rectangles to be predominantly to the top or bottom of each other, e.g. in an Icy Tower type of game, then checking top/bottom first and left/right last will probably be faster:
return std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom)
&& std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right);
- If the probability of intersecting is close to the probability of not intersecting, however, it's better to have a completely branchless alternative:
return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
& std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);
(Note the change of && to a single &)
Ask yourself the opposite question: How can I determine if two rectangles do not intersect at all? Obviously, a rectangle A completely to the left of rectangle B does not intersect. Also if A is completely to the right. And similarly if A is completely above B or completely below B. In any other case A and B intersect.
What follows may have bugs, but I am pretty confident about the algorithm:
struct Rectangle { int x; int y; int width; int height; };
bool is_left_of(Rectangle const & a, Rectangle const & b) {
if (a.x + a.width <= b.x) return true;
return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
return is_left_of(b, a);
}
bool not_intersect( Rectangle const & a, Rectangle const & b) {
if (is_left_of(a, b)) return true;
if (is_right_of(a, b)) return true;
// Do the same for top/bottom...
}
bool intersect(Rectangle const & a, Rectangle const & b) {
return !not_intersect(a, b);
}
This is from exercise 3.28 from the book Introduction to Java Programming- Comprehensive Edition. The code tests whether the two rectangles are indenticle, whether one is inside the other and whether one is outside the other. If none of these condition are met then the two overlap.
**3.28 (Geometry: two rectangles) Write a program that prompts the user to enter the center x-, y-coordinates, width, and height of two rectangles and determines whether the second rectangle is inside the first or overlaps with the first, as shown in Figure 3.9. Test your program to cover all cases. Here are the sample runs:
Enter r1's center x-, y-coordinates, width, and height: 2.5 4 2.5 43 Enter r2's center x-, y-coordinates, width, and height: 1.5 5 0.5 3 r2 is inside r1
Enter r1's center x-, y-coordinates, width, and height: 1 2 3 5.5 Enter r2's center x-, y-coordinates, width, and height: 3 4 4.5 5 r2 overlaps r1
Enter r1's center x-, y-coordinates, width, and height: 1 2 3 3 Enter r2's center x-, y-coordinates, width, and height: 40 45 3 2 r2 does not overlap r1
import java.util.Scanner;
public class ProgrammingEx3_28 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out
.print("Enter r1's center x-, y-coordinates, width, and height:");
double x1 = input.nextDouble();
double y1 = input.nextDouble();
double w1 = input.nextDouble();
double h1 = input.nextDouble();
w1 = w1 / 2;
h1 = h1 / 2;
System.out
.print("Enter r2's center x-, y-coordinates, width, and height:");
double x2 = input.nextDouble();
double y2 = input.nextDouble();
double w2 = input.nextDouble();
double h2 = input.nextDouble();
w2 = w2 / 2;
h2 = h2 / 2;
// Calculating range of r1 and r2
double x1max = x1 + w1;
double y1max = y1 + h1;
double x1min = x1 - w1;
double y1min = y1 - h1;
double x2max = x2 + w2;
double y2max = y2 + h2;
double x2min = x2 - w2;
double y2min = y2 - h2;
if (x1max == x2max && x1min == x2min && y1max == y2max
&& y1min == y2min) {
// Check if the two are identicle
System.out.print("r1 and r2 are indentical");
} else if (x1max <= x2max && x1min >= x2min && y1max <= y2max
&& y1min >= y2min) {
// Check if r1 is in r2
System.out.print("r1 is inside r2");
} else if (x2max <= x1max && x2min >= x1min && y2max <= y1max
&& y2min >= y1min) {
// Check if r2 is in r1
System.out.print("r2 is inside r1");
} else if (x1max < x2min || x1min > x2max || y1max < y2min
|| y2min > y1max) {
// Check if the two overlap
System.out.print("r2 does not overlaps r1");
} else {
System.out.print("r2 overlaps r1");
}
}
}
If the rectangles overlap then the overlap area will be greater than zero. Now let us find the overlap area:
If they overlap then the left edge of overlap-rect will be the max(r1.x1, r2.x1) and right edge will be min(r1.x2, r2.x2). So the length of the overlap will be min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
So the area will be:
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
If area = 0 then they don't overlap.
Simple isn't it?
If the rectangles overlap then the overlap area will be greater than zero. Now let us find the overlap area:
If they overlap then the left edge of overlap-rect will be the max(r1.x1, r2.x1) and right edge will be min(r1.x2, r2.x2). So the length of the overlap will be min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
So the area will be:
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
If area = 0 then they don't overlap.
Simple isn't it?
In the question, you link to the maths for when rectangles are at arbitrary angles of rotation. If I understand the bit about angles in the question however, I interpret that all rectangles are perpendicular to one another.
A general knowing the area of overlap formula is:
Using the example:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates
1 3 4 5 6
2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates
1 2 3 4 6
3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates.
4 * 4
4) paint all the rectangles into this grid, incrementing the count of each cell it occurs over:
1 3 4 5 6
1 +---+
| 1 | 0 0 0
2 +---+---+---+
| 1 | 1 | 1 | 0
3 +---+---+---+---+
| 1 | 1 | 2 | 1 |
4 +---+---+---+---+
0 0 | 1 | 1 |
6 +---+---+
5) As you paint the rectangles, its easy to intercept the overlaps.
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
bool
overlap(const Rect &r1, const Rect &r2)
{
// The rectangles don't overlap if
// one rectangle's minimum in some dimension
// is greater than the other's maximum in
// that dimension.
bool noOverlap = r1.x1 > r2.x2 ||
r2.x1 > r1.x2 ||
r1.y1 > r2.y2 ||
r2.y1 > r1.y2;
return !noOverlap;
}
bool Square::IsOverlappig(Square &other)
{
bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
return result1 | result2 | result3 | result4;
}
Suppose that you have defined the positions and sizes of the rectangles like this:
My C++ implementation is like this:
class Vector2D
{
public:
Vector2D(int x, int y) : x(x), y(y) {}
~Vector2D(){}
int x, y;
};
bool DoRectanglesOverlap( const Vector2D & Pos1,
const Vector2D & Size1,
const Vector2D & Pos2,
const Vector2D & Size2)
{
if ((Pos1.x < Pos2.x + Size2.x) &&
(Pos1.y < Pos2.y + Size2.y) &&
(Pos2.x < Pos1.x + Size1.x) &&
(Pos2.y < Pos1.y + Size1.y))
{
return true;
}
return false;
}
An example function call according to the given figure above:
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
The comparisons inside the if block will look like below:
if ((Pos1.x < Pos2.x + Size2.x) &&
(Pos1.y < Pos2.y + Size2.y) &&
(Pos2.x < Pos1.x + Size1.x) &&
(Pos2.y < Pos1.y + Size1.y))
?
if (( 3 < 6 + 9 ) &&
( 7 < 4 + 4 ) &&
( 6 < 3 + 8 ) &&
( 4 < 7 + 5 ))
Easiest way is
/**
* Check if two rectangles collide
* x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
* x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
*/
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}
first of all put it in to your mind that in computers the coordinates system is upside down. x-axis is same as in mathematics but y-axis increases downwards and decrease on going upward.. if rectangle are drawn from center. if x1 coordinates is greater than x2 plus its its half of widht. then it means going half they will touch each other. and in the same manner going downward + half of its height. it will collide..
I have implemented a C# version, it is easily converted to C++.
public bool Intersects ( Rectangle rect )
{
float ulx = Math.Max ( x, rect.x );
float uly = Math.Max ( y, rect.y );
float lrx = Math.Min ( x + width, rect.x + rect.width );
float lry = Math.Min ( y + height, rect.y + rect.height );
return ulx <= lrx && uly <= lry;
}
For those of you who are using center points and half sizes for their rectangle data, instead of the typical x,y,w,h, or x0,y0,x1,x1, here's how you can do it:
#include <cmath> // for fabsf(float)
struct Rectangle
{
float centerX, centerY, halfWidth, halfHeight;
};
bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b)
{
return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) &&
(fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight));
}
Source: Stackoverflow.com