如何檢查2個旋轉的矩形之間的交集？

Question

有人可以解釋如何檢查一個旋轉矩形相交其他矩形？

Answer 1

1. 對於兩個多邊形中的每條邊，檢查它是否可以用作分隔線。如果是這樣，你就完成了：沒有交集。
2. 如果未找到分隔線，則表示有交點。

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

欲瞭解更多信息，請參閱這篇文章：2D Polygon Collision Detection - Code Project

注：算法只適用於凸多邊形，在順時針規定，或逆時針順序。

Answer 2

在JavaScript中，完全相同的算法是（爲方便起見）：

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

希望這可以幫助別人。

Answer 3

退房由奧倫貝克爾設計的方法來檢測旋轉的矩形的交叉口形式：

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

並調用以下函數將返回兩個是否旋轉矩形相交或不：

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

Answer 4

您也可以使用Rect.IntersectsWith()。

例如，在WPF如果你有兩個UI元素，用的RenderTransform並放置在畫布，你想看看它們相交，你可以使用類似的東西：

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 5

也許這將幫助別人。在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

如果有人感興趣，這裏是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; 
}