Как проверить пересечение между 2 повернутыми прямоугольниками?

Вот тот же алгоритм на Java, если кому-то интересно.

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

Может быть, это кому-нибудь поможет. Тот же алгоритм в 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;
    }

В 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