如何检查2个旋转矩形之间的交集？

有人可以解释如何检查一个旋转矩形相交其他矩形 ？

Answer 1

1. 对于两个多边形中的每个边，检查它是否可以用作分隔线。 如果是这样，你就完成了：没有交集。
2. 如果没有find分隔线，则有交叉点。

/// 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 * pX + normal.Y * pY; 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 * pX + normal.Y * pY; if (minB == null || projected < minB) minB = projected; if (maxB == null || projected > maxB) maxB = projected; } if (maxA < minB || maxB < minA) return false; } } return true; } 

有关更多信息，请参阅此文章： 2D多边形碰撞检测 – 代码项目

NB：该algorithm只适用于凸多边形，按顺时针或逆时针顺序指定。

Answer 2

在JavaScript中，完全相同的algorithm是（为了方便）：

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

如果有人感兴趣，这里是Java中的相同algorithm。

 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 * px + normal.y * py; 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 * px + normal.y * py; if (projected < minB) minB = projected; if (projected > maxB) maxB = projected; } if (maxA < minB || maxB < minA) return false; } } return true; } 

Answer 4

也许它会帮助别人。 PHP中的相同algorithm：

 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 5

你也可以使用Rect.IntersectsWith（） 。

例如，在WPF中，如果您有两个UIElement，RenderTransform并放置在Canvas上，并且想要了解它们是否相交，则可以使用类似的东西：

 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 6

查看由Oren Beckerdevise的方法来检测旋转的矩形与窗体的交点：

 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->Sx/2; BL.y -= rr2->Sy/2; TR.x += rr2->Sx/2; TR.y += rr2->Sy/2; // calculate vertices of (rotated := 'r') rr1 Ax = -(rr1->Sy/2)*sina; Bx = Ax; t = (rr1->Sx/2)*cosa; Ax += t; Bx -= t; Ay = (rr1->Sy/2)*cosa; By = Ay; t = (rr1->Sx/2)*sina; Ay += t; By -= t; //--------------------------------------- //// calculate vertices of (rotated := 'r') rr1 //Ax = -rr1->Sy*sina; Bx = Ax; t = rr1->Sx*cosa; Ax += t; Bx -= t; //Ay = rr1->Sy*cosa; By = Ay; t = rr1->Sx*sina; Ay += t; By -= t; t = sina*cosa; // verify that A is vertical min/max, B is horizontal min/max if (t < 0) { t = Ax; Ax = Bx; Bx = t; t = Ay; Ay = By; By = t; } // verify that B is horizontal minimum (leftest-vertex) if (sina < 0) { Bx = -Bx; By = -By; } // if rr2(ma) isn't in the horizontal range of // colliding with rr1(r), collision is impossible if (Bx > TR.x || Bx > -BL.x) return 0; // if rr1(r) is axis-aligned, vertical min/max are easy to get if (t == 0) {ext1 = Ay; ext2 = -ext1; } // else, find vertical min/max in the range [BL.x, TR.x] else { x = BL.xA.x; a = TR.xA.x; ext1 = Ay; // 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 = Ax; if (x < 0) { dx -= Bx; ext1 -= By; x = a; } else { dx += Bx; ext1 += By; } ext1 *= x; ext1 /= dx; ext1 += Ay; } x = BL.x+Ax; a = TR.x+Ax; ext2 = -Ay; // 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 = -Ax; if (x < 0) { dx -= Bx; ext2 -= By; x = a; } else { dx += Bx; ext2 += By; } ext2 *= x; ext2 /= dx; ext2 -= Ay; } } // 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; }