如何确定两个矩形是否重叠（成角度）

Question

我想确定两个矩形是否重叠（不相交）。我知道如何为轴对齐的矩形执行此操作，但在这种情况下，我有一个并不总是轴对齐的矩形（也就是在其中心旋转）。 This post shows how to calculate two rectangles intersecting, but it won't classify one rectangle inside another as seen in this picture 因为它们是重叠的，而不是相交的。

在我的例子中，其中一个矩形是轴对齐的（黑框），另一个是旋转的（红框），这样可能会更容易。

我想我需要多个案例来确定它们是否重叠。第一个简单的案例是检查是否有任何红色顶点在黑盒子内。然后我可以检查 red/black 条边是否相交。我不确定如何涵盖上面显示的案例，以及是否有更简单的方法来做到这一点。

额外的细节：这是我的图形软件裁剪器（在这种情况下不能使用硬件裁剪），其中黑框是我的 window/viewport，红框是 "sprite" 等等黑框外面是 clipped/not-rendered 我正在使用 orthoganal/2D 投影。最后我将有两个函数，一个用于检测精灵是否在 window/viewport 之外（我在这个问题中要问的是什么），稍后我将创建一个函数来将精灵裁剪到 window/viewport 之外window/viewport 使用 Sutherland–Hodgman 算法。

编辑：

This is post 大致描述了如何做 SAT，但没有详细说明。如何生成法线？ "Corners" 是屏幕坐标还是距形状中心的距离？我已经尝试根据我的目的调整他们的代码，但我无法弄清楚如何使用每个 shape/rectangle

的顶点列表（屏幕 x 和 y）执行 SAT 测试

Answer 1

这通常称为 AABB-OBB 交集测试。（轴对齐边界框和定向边界框）。如果一个边界框完全在另一个边界框内，这仍被视为 "intersection".

要解决这个问题，请使用分离轴定理。如果 AABB 和 OBB 不重叠，那么它们必须至少有一个分离轴平行于它们的一侧。

对于 OBB-OBB 相交测试，您将两个形状投影到 8 条不同的线上（每个矩形的每条边一条），并对每个投影执行简单的一维重叠测试。

对于 AABB-OBB，这基本相同，但减少到 4 个投影，因为四对边始终平行。

看看下面对OBB-OBB的解释：

https://gamedev.stackexchange.com/questions/25397/obb-vs-obb-collision-detection

Answer 2

首先，我要感谢用户“prideout”为我指明了正确的方向。他的笔记，特别是只需要 4 个法线，帮助我优化了我的代码。奇怪的是，the link provided seemed to not work right (Detecting if the "crushed" vertexes of the shapes overlapped). I found this useful example in C++ 中的代码为我指明了正确的方向，现在我的代码运行良好。

这是我的 AABB-OBB 重叠检测器函数 + SAT 函数（使用的语言是基于 Java 的“Processing”）。

// True if overlap, False if they don't
boolean seperating_axis_theorem(float[] x1, float[] y1, float[] x2, float[] y2, float[] normal){
  float[] range = new float[4];  //minAlong1, maxAlong1, minAlong2, maxAlong2
  range[0] = Float.MAX_VALUE;
  range[1] = -Float.MAX_VALUE;
  range[2] = Float.MAX_VALUE;
  range[3] = -Float.MAX_VALUE;
  
  // Dot is projecting the points onto the seperating axis and then we get the max and min
  float dotVal;
  for(int i = 0; i < 4; i++){
    dotVal = dot(x1[i], y1[i], normal[0], normal[1]);
    if(dotVal < range[0]){range[0] = dotVal;}
    if(dotVal > range[1]){range[1] = dotVal;}
    
    dotVal = dot(x2[i], y2[i], normal[0], normal[1]);
    if(dotVal < range[2]){range[2] = dotVal;}
    if(dotVal > range[3]){range[3] = dotVal;}
  }
  
  if(range[1] < range[2] || range[0] > range[3]){
    return false;
  }
  
  return true;
}

// True if two shapes overlap, False otherwise
Boolean AABB_OBB_Overlap(float[] OBB_X, float[] OBB_Y, float[] AABB_X, float[] AABB_Y){
  
  // Checking the camera's normals, simplified since we know its axis aligned so no unit vector calculations needed
  float[] range = get_range(OBB_X);  // Returns min and max of array
  if(range[1] < AABB_X[0] || range[0] > AABB_X[1]){
    return false;
  }
  range = get_range(OBB_Y);
  if(range[1] < AABB_Y[0] || range[0] > AABB_Y[2]){
    return false;
  }
  
  // Checking the sprite's normals
  float[] normal1 = unit_vector(OBB_X[1] - OBB_X[0], OBB_Y[1] - OBB_Y[0]);  // Top side
  float[] normal2 = unit_vector(OBB_X[2] - OBB_X[0], OBB_Y[2] - OBB_Y[0]);  // Left side
  
  if(!seperating_axis_theorem(OBB_X, OBB_Y, AABB_X, AABB_Y, normal1)){
    return false;
  }
  
  if(!seperating_axis_theorem(OBB_X, OBB_Y, AABB_X, AABB_Y, normal2)){
    return false;
  }
  
  // They overlap
  return true;
}

如何确定两个矩形是否重叠（成角度）

How to determine if two rectangles overlap (At angle)

graphics

shapes

overlap

angle

clip