Wie überprüft man den Schnittpunkt zwischen zwei gedrehten Rechtecken?

1. Für jede Kante in beide Polygone, prüfen Sie, ob es verwendet werden kann als eine Trennlinie. Wenn dem so ist, sind Sie fertig: Keinen Schnittpunkt.
2. Wenn keine Trennung Zeile gefunden wurde, haben Sie einen Schnittpunkt.

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

Weitere Informationen finden Sie in diesem Artikel: 2D-Polygon Collision Detection - Code-Projekt

NB: Der Algorithmus funktioniert nur für konvexe Polygone, angegeben entweder im Uhrzeigersinn oder gegen den Uhrzeigersinn um.

InformationsquelleAutor der Antwort Markus Jarderot

Hier der gleiche Algorithmus in Java, wenn jemand interessiert ist.

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

InformationsquelleAutor der Antwort Sri Harsha Chilakapati

Check-out die Methode, entwickelt von Oren Becker, um zu erkennen Kreuzung von gedrehten Rechtecken mit 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;
};

Und rufen Sie die folgende Funktion gibt an, ob zwei gedrehte Rechtecke schneiden oder nicht:

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

InformationsquelleAutor der Antwort herohuyongtao

Einen Typ(Java -) Skript-Implementierung mit einem Knebel zu (ex -) gehören "Touch" - Situationen:

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

InformationsquelleAutor der Antwort Bernoulli IT