Wie um zu überprüfen, Kreuzung zwischen 2 gedrehte Rechtecke?

In javascript, die genaue gleichen Algorithmus (für die Bequemlichkeit):

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

Hoffe, das jemand hilft.

InformationsquelleAutor mstenroos

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 herohuyongtao

Können Sie auch Rect.IntersectsWith().

Beispielsweise in WPF wenn Sie zwei UIElements, mit RenderTransform und platziert auf eine Leinwand, und Sie möchten, um herauszufinden, ob Sie sich schneiden können Sie etwas ähnliches:

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

InformationsquelleAutor Miro Bucko

Lua Umsetzung Baujahr love2d Rahmen. Collision detection-Funktion arbeitet im reinen lua sowieso

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

InformationsquelleAutor Papaew