如何识别二维中两个矩形重叠区域的边界点？

Question

我希望返回二维中两个任意矩形之间重叠区域的边界点的坐标。解决这个问题的最佳方法是什么，可以处理所有特殊情况，例如：

• 仅在单个顶点上相交的矩形？ （程序必须返回单独的顶点）
• 共享整个或部分边的矩形？ （程序必须返回公共线段的端点）

为了增加复杂性，它必须以顺时针/逆时针顺序对点进行排序。因此，我可以在报告之前使用凸包算法对它们进行排序，但如果有一种算法可以直接按顺序找出边界点，那就最好了！

我应该考虑哪些途径有什么想法吗？我不是在寻找代码项目等，只是寻找通用算法的一般概念，我不必保留很多 如果“特殊情况”则“执行此操作” 类型的代码。

编辑：矩形是任意的 - 即它们可能/可能不平行于 X/Y 轴...

Answer 1

使用一般的凸多边形相交方法即可。查找相交凸多边形旋转卡尺。

Answer 2

好吧，我们再试一次...

考虑两者的并集，由通过从 ABCD（黑色）中的每个顶点到 EFGH（红色）的每个顶点绘制一条线来定义的区域组成：

这里困难的部分是想出由这些线定义的所有形状（灰线和来自 ABCD 的原始线）和 EFGH 矩形。）

一次你弄清楚了，创建这些形状的链接列表，并假设这些形状中的每一个都存在于交叉点内。

第 1 步。 翻译并翻译旋转所有物体，使 ABCD 在 0,0 处有一个顶点，并且其线平行/垂直于 x 轴和 y 轴。

步骤 1A。 找到 ABCD 中 y 值最低的顶点，然后从场景中的所有其他顶点中减去它。为了演示目的，我们假设该顶点是 C。通过从场景中的每个顶点减去 C，我们将有效地将原点 (0,0) 移动到 C，从而使围绕 C 的旋转变得容易。

for all shapes in linked list {
    for all vertices in shape {
        vertex -= C;
    }
}

步骤 1B。围绕原点旋转所有物体，旋转角度等于 C→B 向量与 x 轴之间的角度，使 B 落在 x 轴上：

// see http://en.wikipedia.org/wiki/Atan2
float rotRadians = atan2(B.x, B.y);  // assuming ABCD vertices are labelled clockwise

for all shapes in linked list {
    for all vertices in shape {
        rot(thisVert, rotRadians);
    }
}


// ...

// function declaration
void rot(theVertex, theta) {
    tempX = theVertex.x;
    tempY = theVertex.y;

    theVertex.x = cos(theta) * tempX + sin(theta) * tempY;
    theVertex.y = cos(theta) * tempY - sin(theta) * tempX;

}

如果 ABCD 顶点是顺时针标记，ABCD 顶点现在应该如下所示：（

A = ABCDx , ABCDy
B = ABCDx ,   0
C = 0     ,   0
D = 0     , ABCDy

如果它们没有顺时针标记，那么步骤 2 中的“位于”检查将不起作用，因此请确保在atan2(...) 调用是从最低顶点逆时针计算顶点。）

第 2 步。 现在我们可以轻松分析形状是否位于 ABCD 矩形内，例如 if (thisVert.x >= 0 && thisVert.y >= 0 && thisVert.x <= ABCDx && thisVert.y <= ABCDy)。遍历形状的链接列表，并检查以确保每个形状的每个顶点都位于 ABCD 内。如果形状的一个顶点不在 ABCD 内，则该形状不是 ABCD/EFGH 交集的一部分。将其标记为不属于交叉点并跳到下一个形状。

步骤 3. 撤消步骤 1B 中的旋转，然后撤消步骤 1A 中的平移。

步骤 4. 使用 EFGH 而不是 ABCD 重复步骤 1-3，您将设置交集。

---

如果两个集合之间的唯一交集是一条线，那么上面将不会返回任何交集。如果交集 == NULL，则检查相交的线。

如果交集仍然为 NULL，则检查交点。

Answer 3

这可能真的很粗糙但是：

object rectangle { 

     pos  { x, y }              // top-left position
     size { height, width }     // rectangle-size
}


collision::check (rectangle rect) {

     // collision-detection logic 

     collision->order_coords(coords);   // order-coords clockwise;
     return collision_result_object;    // return collided vertices, ordered clockwise, or 0 if rect hit nothing
}

collision::order_rects (rectangle *rect, opt angle)  {

     return clockwise_rects; // returns rectangles ordered clockwise
}

collision::order_coords (coordinate *coord, opt angle) {

     return ordered_coords; // recieves coordinates and returns ordered clockwise
}

rectangle rects; // bunch of rectangles

ordered_rects = collision->order_rects (rects); // order rects starting at 12PM

loop {    

       foreach ordered_rects as i {

           if (collision->check(i)) {

           array_of_collision_result_objects[i] = collision->check(i);      // start checking rects starting at 12PM, if collision found, return ordered vertexes
           }
       }

}

Answer 4

找到矩形线段的所有交点。结果由其中一些顶点和一些初始顶点组成。要找到它们，只需检查位于两个矩形中的每个点即可。删除不必要的点（如果一条线上有 3 个或更多点）。结果是凸的，并且您得到的点都不是严格位于其内部的，因此（如果至少有 3 个点）按角度对某个内部点进行排序并享受结果。

Answer 5

我想出了一个合理的方法，应该涵盖所有可能的情况：

我们需要的基本上是 3 个步骤：

步骤 1：

for each side Si of R1
    for each side Sj of R2
           Check if Si and Sj intersect. If they do, push the point in results array
           (This also has to take care of the case in case Si and Sj overlap, which is 
           basically checking if they  have the same equation or not - if so, push in 
           the points of overlap. This also takes care of the case where a vertex of 
           R2 lies on Si).
    next
next

步骤 2：

for each vertex Vi of R1
   Check if Vi lies inside R2, If so, push it in the results array.
next

步骤 3：

for each vertex Vi of R2
   Check if Vi lies inside R1, If so, push it in the results array.
next

现在，对结果数组进行排序，然后返回

对于步骤 2 和步骤 2： 3（如何查找一个点是否位于矩形内）-我会使用 这篇优秀的文章（其中提到的最后一个算法）。