How to check intersection between 2 rotated rectangles?
30,137
Solution 1
- For each edge in both polygons, check if it can be used as a separating line. If so, you are done: No intersection.
- If no separation line was found, you have an intersection.
/// Checks if the two polygons are intersecting.
bool IsPolygonsIntersecting(Polygon a, Polygon b)
{
foreach (var polygon in new[] { a, b })
{
for (int i1 = 0; i1 < polygon.Points.Count; i1++)
{
int i2 = (i1 + 1) % polygon.Points.Count;
var p1 = polygon.Points[i1];
var p2 = polygon.Points[i2];
var normal = new Point(p2.Y - p1.Y, p1.X - p2.X);
double? minA = null, maxA = null;
foreach (var p in a.Points)
{
var projected = normal.X * p.X + normal.Y * p.Y;
if (minA == null || projected < minA)
minA = projected;
if (maxA == null || projected > maxA)
maxA = projected;
}
double? minB = null, maxB = null;
foreach (var p in b.Points)
{
var projected = normal.X * p.X + normal.Y * p.Y;
if (minB == null || projected < minB)
minB = projected;
if (maxB == null || projected > maxB)
maxB = projected;
}
if (maxA < minB || maxB < minA)
return false;
}
}
return true;
}
For more information, see this article: 2D Polygon Collision Detection - Code Project
NB: The algorithm only works for convex polygons, specified in either clockwise, or counterclockwise order.
Solution 2
In javascript, the exact same algorithm is (for convenience):
/**
* Helper function to determine whether there is an intersection between the two polygons described
* by the lists of vertices. Uses the Separating Axis Theorem
*
* @param a an array of connected points [{x:, y:}, {x:, y:},...] that form a closed polygon
* @param b an array of connected points [{x:, y:}, {x:, y:},...] that form a closed polygon
* @return true if there is any intersection between the 2 polygons, false otherwise
*/
function doPolygonsIntersect (a, b) {
var polygons = [a, b];
var minA, maxA, projected, i, i1, j, minB, maxB;
for (i = 0; i < polygons.length; i++) {
// for each polygon, look at each edge of the polygon, and determine if it separates
// the two shapes
var polygon = polygons[i];
for (i1 = 0; i1 < polygon.length; i1++) {
// grab 2 vertices to create an edge
var i2 = (i1 + 1) % polygon.length;
var p1 = polygon[i1];
var p2 = polygon[i2];
// find the line perpendicular to this edge
var normal = { x: p2.y - p1.y, y: p1.x - p2.x };
minA = maxA = undefined;
// for each vertex in the first shape, project it onto the line perpendicular to the edge
// and keep track of the min and max of these values
for (j = 0; j < a.length; j++) {
projected = normal.x * a[j].x + normal.y * a[j].y;
if (isUndefined(minA) || projected < minA) {
minA = projected;
}
if (isUndefined(maxA) || projected > maxA) {
maxA = projected;
}
}
// for each vertex in the second shape, project it onto the line perpendicular to the edge
// and keep track of the min and max of these values
minB = maxB = undefined;
for (j = 0; j < b.length; j++) {
projected = normal.x * b[j].x + normal.y * b[j].y;
if (isUndefined(minB) || projected < minB) {
minB = projected;
}
if (isUndefined(maxB) || projected > maxB) {
maxB = projected;
}
}
// if there is no overlap between the projects, the edge we are looking at separates the two
// polygons, and we know there is no overlap
if (maxA < minB || maxB < minA) {
CONSOLE("polygons don't intersect!");
return false;
}
}
}
return true;
};
Hope this helps someone.
Solution 3
Here's the same algorithm in Java if anybody is interested.
boolean isPolygonsIntersecting(Polygon a, Polygon b)
{
for (int x=0; x<2; x++)
{
Polygon polygon = (x==0) ? a : b;
for (int i1=0; i1<polygon.getPoints().length; i1++)
{
int i2 = (i1 + 1) % polygon.getPoints().length;
Point p1 = polygon.getPoints()[i1];
Point p2 = polygon.getPoints()[i2];
Point normal = new Point(p2.y - p1.y, p1.x - p2.x);
double minA = Double.POSITIVE_INFINITY;
double maxA = Double.NEGATIVE_INFINITY;
for (Point p : a.getPoints())
{
double projected = normal.x * p.x + normal.y * p.y;
if (projected < minA)
minA = projected;
if (projected > maxA)
maxA = projected;
}
double minB = Double.POSITIVE_INFINITY;
double maxB = Double.NEGATIVE_INFINITY;
for (Point p : b.getPoints())
{
double projected = normal.x * p.x + normal.y * p.y;
if (projected < minB)
minB = projected;
if (projected > maxB)
maxB = projected;
}
if (maxA < minB || maxB < minA)
return false;
}
}
return true;
}
Solution 4
Check out the method designed by Oren Becker to detect intersection of rotated rectangles with form:
struct _Vector2D
{
float x, y;
};
// C:center; S: size (w,h); ang: in radians,
// rotate the plane by [-ang] to make the second rectangle axis in C aligned (vertical)
struct _RotRect
{
_Vector2D C;
_Vector2D S;
float ang;
};
And calling the following function will return whether two rotated rectangles intersect or not:
// Rotated Rectangles Collision Detection, Oren Becker, 2001
bool check_two_rotated_rects_intersect(_RotRect * rr1, _RotRect * rr2)
{
_Vector2D A, B, // vertices of the rotated rr2
C, // center of rr2
BL, TR; // vertices of rr2 (bottom-left, top-right)
float ang = rr1->ang - rr2->ang, // orientation of rotated rr1
cosa = cos(ang), // precalculated trigonometic -
sina = sin(ang); // - values for repeated use
float t, x, a; // temporary variables for various uses
float dx; // deltaX for linear equations
float ext1, ext2; // min/max vertical values
// move rr2 to make rr1 cannonic
C = rr2->C;
SubVectors2D(&C, &rr1->C);
// rotate rr2 clockwise by rr2->ang to make rr2 axis-aligned
RotateVector2DClockwise(&C, rr2->ang);
// calculate vertices of (moved and axis-aligned := 'ma') rr2
BL = TR = C;
/*SubVectors2D(&BL, &rr2->S);
AddVectors2D(&TR, &rr2->S);*/
//-----------------------------------
BL.x -= rr2->S.x/2; BL.y -= rr2->S.y/2;
TR.x += rr2->S.x/2; TR.y += rr2->S.y/2;
// calculate vertices of (rotated := 'r') rr1
A.x = -(rr1->S.y/2)*sina; B.x = A.x; t = (rr1->S.x/2)*cosa; A.x += t; B.x -= t;
A.y = (rr1->S.y/2)*cosa; B.y = A.y; t = (rr1->S.x/2)*sina; A.y += t; B.y -= t;
//---------------------------------------
//// calculate vertices of (rotated := 'r') rr1
//A.x = -rr1->S.y*sina; B.x = A.x; t = rr1->S.x*cosa; A.x += t; B.x -= t;
//A.y = rr1->S.y*cosa; B.y = A.y; t = rr1->S.x*sina; A.y += t; B.y -= t;
t = sina*cosa;
// verify that A is vertical min/max, B is horizontal min/max
if (t < 0)
{
t = A.x; A.x = B.x; B.x = t;
t = A.y; A.y = B.y; B.y = t;
}
// verify that B is horizontal minimum (leftest-vertex)
if (sina < 0) { B.x = -B.x; B.y = -B.y; }
// if rr2(ma) isn't in the horizontal range of
// colliding with rr1(r), collision is impossible
if (B.x > TR.x || B.x > -BL.x) return 0;
// if rr1(r) is axis-aligned, vertical min/max are easy to get
if (t == 0) {ext1 = A.y; ext2 = -ext1; }
// else, find vertical min/max in the range [BL.x, TR.x]
else
{
x = BL.x-A.x; a = TR.x-A.x;
ext1 = A.y;
// if the first vertical min/max isn't in (BL.x, TR.x), then
// find the vertical min/max on BL.x or on TR.x
if (a*x > 0)
{
dx = A.x;
if (x < 0) { dx -= B.x; ext1 -= B.y; x = a; }
else { dx += B.x; ext1 += B.y; }
ext1 *= x; ext1 /= dx; ext1 += A.y;
}
x = BL.x+A.x; a = TR.x+A.x;
ext2 = -A.y;
// if the second vertical min/max isn't in (BL.x, TR.x), then
// find the local vertical min/max on BL.x or on TR.x
if (a*x > 0)
{
dx = -A.x;
if (x < 0) { dx -= B.x; ext2 -= B.y; x = a; }
else { dx += B.x; ext2 += B.y; }
ext2 *= x; ext2 /= dx; ext2 -= A.y;
}
}
// check whether rr2(ma) is in the vertical range of colliding with rr1(r)
// (for the horizontal range of rr2)
return !((ext1 < BL.y && ext2 < BL.y) ||
(ext1 > TR.y && ext2 > TR.y));
}
inline void AddVectors2D(_Vector2D * v1, _Vector2D * v2)
{
v1->x += v2->x; v1->y += v2->y;
}
inline void SubVectors2D(_Vector2D * v1, _Vector2D * v2)
{
v1->x -= v2->x; v1->y -= v2->y;
}
inline void RotateVector2DClockwise(_Vector2D * v, float ang)
{
float t, cosa = cos(ang), sina = sin(ang);
t = v->x;
v->x = t*cosa + v->y*sina;
v->y = -t*sina + v->y*cosa;
}
Solution 5
In Python:
def do_polygons_intersect(a, b):
"""
* Helper function to determine whether there is an intersection between the two polygons described
* by the lists of vertices. Uses the Separating Axis Theorem
*
* @param a an ndarray of connected points [[x_1, y_1], [x_2, y_2],...] that form a closed polygon
* @param b an ndarray of connected points [[x_1, y_1], [x_2, y_2],...] that form a closed polygon
* @return true if there is any intersection between the 2 polygons, false otherwise
"""
polygons = [a, b];
minA, maxA, projected, i, i1, j, minB, maxB = None, None, None, None, None, None, None, None
for i in range(len(polygons)):
# for each polygon, look at each edge of the polygon, and determine if it separates
# the two shapes
polygon = polygons[i];
for i1 in range(len(polygon)):
# grab 2 vertices to create an edge
i2 = (i1 + 1) % len(polygon);
p1 = polygon[i1];
p2 = polygon[i2];
# find the line perpendicular to this edge
normal = { 'x': p2[1] - p1[1], 'y': p1[0] - p2[0] };
minA, maxA = None, None
# for each vertex in the first shape, project it onto the line perpendicular to the edge
# and keep track of the min and max of these values
for j in range(len(a)):
projected = normal['x'] * a[j][0] + normal['y'] * a[j][1];
if (minA is None) or (projected < minA):
minA = projected
if (maxA is None) or (projected > maxA):
maxA = projected
# for each vertex in the second shape, project it onto the line perpendicular to the edge
# and keep track of the min and max of these values
minB, maxB = None, None
for j in range(len(b)):
projected = normal['x'] * b[j][0] + normal['y'] * b[j][1]
if (minB is None) or (projected < minB):
minB = projected
if (maxB is None) or (projected > maxB):
maxB = projected
# if there is no overlap between the projects, the edge we are looking at separates the two
# polygons, and we know there is no overlap
if (maxA < minB) or (maxB < minA):
print("polygons don't intersect!")
return False;
return True
Comments
-
Buron over 2 years
Can someone explain how to check if one rotated rectangle intersect other rectangle?