Can someone explain how to check if one rotated rectangle intersect other rectangle?
-
5Have a look at "Separating axis theorem" :)– Stefan FandlerJun 9, 2012 at 15:52
-
Is it always a rectangle? What is the axis of rotation? Is the axis fixed?– Hari MenonJun 9, 2012 at 15:59
-
I have one rotated rectangle and one fixed and i need to know if they intersect– BuronJun 9, 2012 at 16:26
14 Answers
- 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.
-
4Just to note, this code doesn't seem to work if one polygon is completely contained within the other.– xioxoxApr 19, 2014 at 11:32
-
@xioxox, Could you give an example which gives the wrong result? You could fork this code: ideone.com/H7DWOO Apr 19, 2014 at 17:00
-
1It looks like I made a bug in my conversion to C++. It works now - pastebin.com/03BigiCn– xioxoxApr 20, 2014 at 17:53
-
I can't get this algorithm to always work. I have a Java test case: pastebin.com/TEKHYx6B and a Python test case: pastebin.com/Ahmx1Uir The test code has one rectangle completely to the left of the other rectangle. Yet the algorithm returns true, when false is expected. What is wrong? Dec 26, 2015 at 15:42
-
3@PaulVincentCraven Your polygons are specified in the wrong order. As they stand, they form two time-glass shapes. The algorithm is only guaranteed to work for convex polygons, specified in either clockwise or counterclockwise order. -- Flip the last two coordinates in each polygon to make them into rectangles. Dec 27, 2015 at 16:48
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.
-
9Its worth noting that this is a general algorithm for convex polygons, rather than just rectangles (for rectangles you can reduce the number of sides and points looped over since you know the sides are parallel). Sep 25, 2012 at 7:06
-
THANKS for Javascript– user2039981Mar 27, 2014 at 21:05
-
1When using this, does anyone know if I need to add an extra point for the test? So for example when using a triangle there are 3 points:
first
,second
andlast
. Which means parama
and/orb
would have an array of 3 items, or would you need a fourth item which would be the starting point. So basically do you need the the first point at the beginning and end of the array? Oct 7, 2016 at 15:00 -
1@GetOffMyLawn I think not. All it needs is your points, you don't need to 'close' the shape off by adding the starting point at the end.– SvenOct 8, 2016 at 9:54
-
Not for rectangles, but for polygons, which is wasting tons of CPU cycles. Aug 25, 2020 at 15:10
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;
}
-
1That algorithm didn't work when I used triangles as polygons. It detected intersections when there were none. However, it works when you don't use Double.MAX_VALUE and Double.MIN_VALUE and instead use null and checks for null like Markus Jarderot did in his example.– RolandMar 6, 2016 at 8:38
-
1Right, I forgot that
Double.MIN_VALUE
is the smallest possible positive number and that is why this example fails. I think they should be fixed by changing them toPOSITIVE_INFINITY
andNEGATIVE_INFINITY
. Mar 6, 2016 at 8:47 -
Not for rectangles, but for polygons, which is wasting tons of CPU cycles. Aug 25, 2020 at 15:10
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;
}
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
Maybe it will help someone. The same algorithm in PHP:
function isPolygonsIntersecting($a, $b) {
$polygons = array($a, $b);
for ($i = 0; $i < count($polygons); $i++) {
$polygon = $polygons[$i];
for ($i1 = 0; $i1 < count($polygon); $i1++) {
$i2 = ($i1 + 1) % count($polygon);
$p1 = $polygon[$i1];
$p2 = $polygon[$i2];
$normal = array(
"x" => $p2["y"] - $p1["y"],
"y" => $p1["x"] - $p2["x"]
);
$minA = NULL; $maxA = NULL;
for ($j = 0; $j < count($a); $j++) {
$projected = $normal["x"] * $a[$j]["x"] + $normal["y"] * $a[$j]["y"];
if (!isset($minA) || $projected < $minA) {
$minA = $projected;
}
if (!isset($maxA) || $projected > $maxA) {
$maxA = $projected;
}
}
$minB = NULL; $maxB = NULL;
for ($j = 0; $j < count($b); $j++) {
$projected = $normal["x"] * $b[$j]["x"] + $normal["y"] * $b[$j]["y"];
if (!isset($minB) || $projected < $minB) {
$minB = $projected;
}
if (!isset($maxB) || $projected > $maxB) {
$maxB = $projected;
}
}
if ($maxA < $minB || $maxB < $minA) {
return false;
}
}
}
return true;
}
You can also use Rect.IntersectsWith().
For example, in WPF if you have two UIElements, with RenderTransform and placed on a Canvas, and you want to find out if they intersect you can use something similar:
bool IsIntersecting(UIElement element1, UIElement element2)
{
Rect area1 = new Rect(
(double)element1.GetValue(Canvas.TopProperty),
(double)element1.GetValue(Canvas.LeftProperty),
(double)element1.GetValue(Canvas.WidthProperty),
(double)element1.GetValue(Canvas.HeightProperty));
Rect area2 = new Rect(
(double)element2.GetValue(Canvas.TopProperty),
(double)element2.GetValue(Canvas.LeftProperty),
(double)element2.GetValue(Canvas.WidthProperty),
(double)element2.GetValue(Canvas.HeightProperty));
Transform transform1 = element1.RenderTransform as Transform;
Transform transform2 = element2.RenderTransform as Transform;
if (transform1 != null)
{
area1.Transform(transform1.Value);
}
if (transform2 != null)
{
area2.Transform(transform2.Value);
}
return area1.IntersectsWith(area2);
}
A Type(Java)Script implementation with a toggle to (ex)include "Touch" situations:
class Position {
private _x: number;
private _y: number;
public constructor(x: number = null, y: number = null) {
this._x = x;
this._y = y;
}
public get x() { return this._x; }
public set x(value: number) { this._x = value; }
public get y() { return this._y; }
public set y(value: number) { this._y = value; }
}
class Polygon {
private _positions: Array<Position>;
public constructor(positions: Array<Position> = null) {
this._positions = positions;
}
public addPosition(position: Position) {
if (!position) {
return;
}
if (!this._positions) {
this._positions = new Array<Position>();
}
this._positions.push(position);
}
public get positions(): ReadonlyArray<Position> { return this._positions; }
/**
* https://stackoverflow.com/a/12414951/468910
*
* 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 polygonToCompare a polygon to compare with
* @param allowTouch consider it an intersection when polygons only "touch"
* @return true if there is any intersection between the 2 polygons, false otherwise
*/
public isIntersecting(polygonToCompare: Polygon, allowTouch: boolean = true): boolean {
const polygons: Array<ReadonlyArray<Position>> = [this.positions, polygonToCompare.positions]
const firstPolygonPositions: ReadonlyArray<Position> = polygons[0];
const secondPolygonPositions: ReadonlyArray<Position> = polygons[1];
let 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
const polygon = polygons[i];
for (i1 = 0; i1 < polygon.length; i1++) {
// grab 2 vertices to create an edge
const i2 = (i1 + 1) % polygon.length;
const p1 = polygon[i1];
const p2 = polygon[i2];
// find the line perpendicular to this edge
const 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 < firstPolygonPositions.length; j++) {
projected = normal.x * firstPolygonPositions[j].x + normal.y * firstPolygonPositions[j].y;
if (!minA || projected < minA || (!allowTouch && projected === minA)) {
minA = projected;
}
if (!maxA || projected > maxA || (!allowTouch && 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 < secondPolygonPositions.length; j++) {
projected = normal.x * secondPolygonPositions[j].x + normal.y * secondPolygonPositions[j].y;
if (!minB || projected < minB || (!allowTouch && projected === minB)) {
minB = projected;
}
if (!maxB || projected > maxB || (!allowTouch && 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 || (!allowTouch && maxA === minB) || maxB < minA || (!allowTouch && maxB === minA)) {
return false;
}
}
}
return true;
}
Lua implementation built in love2d framework. Collision detection function works in pure lua anyway
math.inf = 1e309
function love.load()
pol = {{0, 0}, {30, 2}, {8, 30}}
pol2 = {{60, 60}, {90, 61}, {98, 100}, {80, 100}}
end
function love.draw()
for k,v in ipairs(pol) do
love.graphics.line(pol[k][1], pol[k][2], pol[k % #pol + 1][1], pol[k % #pol + 1][2])
end
for k,v in ipairs(pol2) do
love.graphics.line(pol2[k][1], pol2[k][2], pol2[k % #pol2 + 1][1], pol2[k % #pol2 + 1][2])
end
end
function love.update(dt)
pol[1][1] = love.mouse.getX()
pol[1][2] = love.mouse.getY()
pol[2][1] = pol[1][1] + 30
pol[2][2] = pol[1][2] + 2
pol[3][1] = pol[1][1] + 8
pol[3][2] = pol[1][2] + 30
--lazy way to see that's function works
print(doPolygonsIntersect(pol, pol2))
end
-------------------------------------------------------------------------
function doPolygonsIntersect(a,b)
polygons = {a,b}
for i=1, #polygons do
polygon = polygons[i]
for i1=1, #polygon do
i2 = i1 % #polygon + 1
p1 = polygon[i1]
p2 = polygon[i2]
nx,ny = p2[2] - p1[2], p1[1] - p2[1]
minA = math.inf
maxA = -math.inf
for j=1, #a do
projected = nx * a[j][1] + ny * a[j][2]
if projected < minA then minA = projected end
if projected > maxA then maxA = projected end
end
minB = math.inf
maxB = -math.inf
for j=1, #b do
projected = nx * b[j][1] + ny * b[j][2]
if projected < minB then minB = projected end
if projected > maxB then maxB = projected end
end
if maxA < minB or maxB < minA then return false end
end
end
return true
end
Took Sri's JavaScript and made it work with Phaser 3 Polygons.
/// Checks if the two Phaser 3 polygons are intersecting.
gameScene.doPolygonsIntersect=function(a, b) {
// https://stackoverflow.com/questions/10962379/how-to-check-intersection-between-2-rotated-rectangles#10965077
/**
* 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
*/
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.points.length; i1++) {
// grab 2 vertices to create an edge
var i2 = (i1 + 1) % polygon.points.length;
var p1 = polygon.points[i1];
var p2 = polygon.points[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.points.length; j++) {
projected = normal.x * a.points[j].x + normal.y * a.points[j].y;
if (!isDef(minA) || projected < minA) {
minA = projected;
}
if (!isDef(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.points.length; j++) {
projected = normal.x * b.points[j].x + normal.y * b.points[j].y;
if (!isDef(minB) || projected < minB) {
minB = projected;
}
if (!isDef(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.log("polygons don't intersect!");
return false;
}
}
}
return true;
};
Here it is in LUA, hope it will help somebody when they need it:
function doPolygonsIntersect(a, b)
local polygons = { a, b };
local minA, maxA, projected, i, i1, j, minB, maxB;
for i = 1, #polygons do
--// for each polygon, look at each edge of the polygon, and determine if it separates
--// the two shapes
local polygon = polygons[i];
for i1 = 0, (#polygon-1) do
--// grab 2 vertices to create an edge
local i2 = (i1 + 1) % (#polygon);
local p1 = polygon[i1+1];
local p2 = polygon[i2+1];
--// find the line perpendicular to this edge
local normal = { x = p2.y - p1.y, y = p1.x - p2.x };
minA = nil;
maxA = nil;
--// 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 = 1, #a do
projected = normal.x * a[j].x + normal.y * a[j].y;
if (minA == nil or projected < minA) then
minA = projected;
end
if (maxA == nil or projected > maxA) then
maxA = projected;
end
end
--// 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 = nil;
maxB = nil;
for j = 1, #b do
projected = normal.x * b[j].x + normal.y * b[j].y;
if (minB == nil or projected < minB) then
minB = projected;
end
if (maxB == nil or projected > maxB) then
maxB = projected;
end
end
if (maxA < minB or maxB < minA) then
return false;
end
end
end
return true;
end
The accepted algorithm in Go.
func isPolygonIntersecting(a *Polygon, b *Polygon) bool {
for _, polygon := range []*Polygon{a, b} {
for i1 := 0; i1 < len(*polygon); i1++ {
i2 := (i1 + 1) % len(*polygon)
p1 := (*polygon)[i1]
p2 := (*polygon)[i2]
normal := pixel.V(p2.Y-p1.Y, p1.X-p2.X)
minA := math.MaxFloat64
maxA := math.MaxFloat64
for _, p := range *a {
projected := normal.X*p.X + normal.Y*p.Y
if minA == math.MaxFloat64 || projected < minA {
minA = projected
}
if maxA == math.MaxFloat64 || projected > maxA {
maxA = projected
}
}
minB := math.MaxFloat64
maxB := math.MaxFloat64
for _, p := range *b {
projected := normal.X*p.X + normal.Y*p.Y
if minB == math.MaxFloat64 || projected < minB {
minB = projected
}
if maxB == math.MaxFloat64 || projected > maxB {
maxB = projected
}
}
if maxA < minB || maxB < minA {
return false
}
}
}
return true
}
type Polygon []struct {
X float64
Y float64
}
@dabs's answer https://stackoverflow.com/a/56962827/11846040 converted to Dart:
// `CustomPoint` is just a class holding two x/y or y/x values
class Polygon {
final CustomPoint<num> nw;
final CustomPoint<num> ne;
final CustomPoint<num> se;
final CustomPoint<num> sw;
Polygon(this.nw, this.ne, this.se, this.sw);
List<CustomPoint<num>> get points => [nw, ne, se, sw];
}
bool overlap(Polygon a, Polygon b) {
for (int x = 0; x < 2; x++) {
final Polygon polygon = (x == 0) ? a : b;
for (int i1 = 0; i1 < polygon.points.length; i1++) {
final int i2 = (i1 + 1) % polygon.points.length;
final CustomPoint<num> p1 = polygon.points[i1];
final CustomPoint<num> p2 = polygon.points[i2];
final CustomPoint<num> normal =
CustomPoint<num>(p2.y - p1.y, p1.x - p2.x);
double minA = double.infinity;
double maxA = double.negativeInfinity;
for (CustomPoint<num> p in a.points) {
final num projected = normal.x * p.x + normal.y * p.y;
if (projected < minA) minA = projected.toDouble();
if (projected > maxA) maxA = projected.toDouble();
}
double minB = double.infinity;
double maxB = double.negativeInfinity;
for (CustomPoint<num> p in b.points) {
final num projected = normal.x * p.x + normal.y * p.y;
if (projected < minB) minB = projected.toDouble();
if (projected > maxB) maxB = projected.toDouble();
}
if (maxA < minB || maxB < minA) return false;
}
}
return true;
}
I searched for months to find this answer, but couldn't find it. Enjoy your present person 15 years down the line!
Matlab implementation:
function isIntersecting = IsPolygonsIntersecting(polyVertices1, polyVertices2)
isIntersecting = ...
IsPolygon1Intersecting2( polyVertices1, polyVertices2 ) && ...
IsPolygon1Intersecting2( polyVertices2, polyVertices1 );
end
function isIntersecting = IsPolygon1Intersecting2(polyVertices1,polyVertices2)
nVertices = size(polyVertices1,1);
isIntersecting = true;
for i1 = 1:nVertices
% Current edge vertices:
i2 = mod(i1, nVertices) + 1;
p1 = polyVertices1(i1,:);
p2 = polyVertices1(i2,:);
% Project the polygon vertices on the edge normal and find the extreme values:
normal = [p2(2) - p1(2); p1(1) - p2(1)];
minA = min(polyVertices1 * normal);
maxA = max(polyVertices1 * normal);
minB = min(polyVertices2 * normal);
maxB = max(polyVertices2 * normal);
if (maxA < minB || maxB < minA)
isIntersecting = false;
return;
end
end
end