How to check intersection between 2 rotated rectan

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

1. For each edge in both polygons, check if it can be used as a separating line. If so, you are done: No intersection.
2. 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.