How to check intersection between 2 rotated rectangles?

Asked 9/6, 2012 at 15:50 Answered 9/11, 2021 at 12:17

Solved math intersection rect

Can someone explain how to check if one rotated rectangle intersect other rectangle?

Anabal answered 9/6, 2012 at 15:50 Comment(3)

Have a look at "Separating axis theorem" :) – Transistor 9/6, 2012 at 15:52

Is it always a rectangle? What is the axis of rotation? Is the axis fixed? – Cartierbresson 9/6, 2012 at 15:59

I have one rotated rectangle and one fixed and i need to know if they intersect – Anabal 9/6, 2012 at 16:26

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.

Loren answered 9/6, 2012 at 22:35 Comment(6)

Just to note, this code doesn't seem to work if one polygon is completely contained within the other. – Truthvalue 19/4, 2014 at 11:32

@xioxox, Could you give an example which gives the wrong result? You could fork this code: ideone.com/H7DWOO – Loren 19/4, 2014 at 17:0

It looks like I made a bug in my conversion to C++. It works now - pastebin.com/03BigiCn – Truthvalue 20/4, 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? – Striking 26/12, 2015 at 15:42

@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. – Loren 27/12, 2015 at 16:48

Not for rectangles, but for polygons, which is wasting tons of CPU cycles. – Derail 25/8, 2020 at 15:10

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.

Sacha answered 13/9, 2012 at 21:18 Comment(5)

Its 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). – Bathometer 25/9, 2012 at 7:6

THANKS for Javascript – Ammieammine 27/3, 2014 at 21:5

When 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 and last. Which means param a and/or b 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? – Ume 7/10, 2016 at 15:0

@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. – Couplet 8/10, 2016 at 9:54

Not for rectangles, but for polygons, which is wasting tons of CPU cycles. – Derail 25/8, 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;
}

Chara answered 5/12, 2014 at 5:34 Comment(3)

That 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. – Bullock 6/3, 2016 at 8:38

Right, 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 to POSITIVE_INFINITY and NEGATIVE_INFINITY. – Chara 6/3, 2016 at 8:47

Not for rectangles, but for polygons, which is wasting tons of CPU cycles. – Derail 25/8, 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;
}

Mascle answered 26/12, 2013 at 6:20 Comment(0)

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

Nonaligned answered 10/7, 2019 at 2:58 Comment(0)

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;
}

Ilocano answered 12/8, 2014 at 10:12 Comment(0)

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);
}

Fascinating answered 18/2, 2014 at 12:15 Comment(0)

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://mcmap.net/q/399611/-how-to-check-intersection-between-2-rotated-rectangles
 * 
 * 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;
}

Fragrant answered 18/5, 2018 at 11:13 Comment(0)

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

Antebellum answered 21/4, 2019 at 8:15 Comment(0)

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://mcmap.net/q/399611/-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;
    };

Rosales answered 14/12, 2019 at 14:7 Comment(0)

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

Thyratron answered 21/2, 2020 at 19:37 Comment(0)

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
}

Nikolai answered 31/1, 2021 at 4:10 Comment(0)

@dabs's answer https://mcmap.net/q/399611/-how-to-check-intersection-between-2-rotated-rectangles 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 gift, whoever's looking at this in 15 years time!

Nedrud answered 9/10, 2021 at 11:31 Comment(0)

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

Slaughterhouse answered 9/11, 2021 at 12:17 Comment(1)

Please add some more details explaining your code. – Grotto 16/11, 2021 at 10:15

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Recommended topics

Hot tags