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

我正在寻找返回2个任意矩形之间重叠区域边界的坐标。最好的方法来处理这个问题，将照顾所有的特殊情况，例如：如何识别2D中两个矩形重叠区域的边界点？

只在单个顶点相交的矩形？（该程序将不得不返回单独的顶点）
共享全部或部分边的矩形？（程序将不得不返回公共线段的端点）

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

任何想法，我应该看什么途径？我不是在寻找代码项目等，只是泛型算法的一般思路，我不需要保留很多类型的代码。

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

来源

2011-08-07 TCSGrad

许多重复例如[非轴对齐的矩形相交]（http://stackoverflow.com/questions/2089173/non-axis-aligned-rectangle-intersection） –

只需使用一般凸多边形相交法。查找intersect convex polygons rotating calipers。

来源

2011-08-07 20:52:40

是的，但他们利用矩形的属性 - 我正在寻找一个会做所以为了尽量减少执行开销... – TCSGrad

一个非轴向的矩形可能没有特别容易利用的属性。如果您可以旋转场景以使其中一个矩形是轴平行的，那么可以使用更简单的方法夹紧这种矩形。 –

@ n.m。这是我的后备计划 - 选择一个矩形（我们可以称之为“基本矩形”），将原点设置为基准矩形的最低点（“最低”意味着最低的y值），然后旋转两个矩形（通过矩阵乘法[ http://en.wikipedia.org/wiki/Rotation_matrix]），以便基本矩形存在于右上象限中。我会想象这会大大简化事情。在计算结束时，你必须不旋转它，然后将原点移回原来的位置。 – TimFoolery

这可能是真的，但粗糙：

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

}

来源

2011-08-07 21:40:43

错过了基本点 - 矩形是非轴对齐的，所以左上角和高度，宽度不会给你其余的点！ – TCSGrad

查找矩形段的所有路口。结果由其中的一些和一些初始顶点组成。要找到它们，只需检查它在两个矩形中的每个点。删除不必要的点（如果一行有3个或更多）。结果是凸的，并且没有任何一点是严格的，所以（如果至少有3个）从某个内点按角度排序点并享受结果。

来源

2011-08-08 09:44:23

不可以 - 当一个矩形完全位于另一个矩形的内部时，您会错过这种情况，因此重叠区域由较小的矩形本身组成。观察问题中的措辞 - 它不仅仅指出相交点，而是指重叠区域的边界点。 – TCSGrad

我没有看到任何矛盾。通过初始顶点，我指的是矩形本身的顶点。在这种情况下，我们将得到没有交点，检查内部矩形的4个点位于两个角度，然后按角度排序。 –

你的答案与我的答案完全相同。要检查点P是否在某个凸多边形内部，您应该检查每个边AB的向量积AB \ times AP是否具有相同的符号（除非为0）。这里边应该朝一个方向走。 –

好吧，我们将再次尝试这个......

考虑了两下，由通过在ABCD从每一个顶点画一条线（黑色）到EFGH（红色）定义区域的联合：

enter image description here

这里最难的是未来与所有这些线定义的形状

一旦你（无论是灰色系和原线从ABCD和EFGH矩形来了。）图出来，创建一个链接l并且假设这些形状中的每一个存在于交叉点内。

第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轴之间的角度的角度的原点一切，所以在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(...)调用中使用的是VERT顶点逆时针从最低点开始）。

第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，则检查相交点。

来源

2011-08-09 00:12:36 TimFoolery

我假设两个矩形的命名都是从左上角开始的（一旦与x-y轴对齐），然后顺时针继续 - 使顶点B位于EFGH内而E，F位于ABCD内？ – TCSGrad

此外，计算的关键在于步骤0（其中必须生成所有“形状”）和步骤2（遍历形状的链接链接并确定它们是否相交）。这些，以及两次轮换和转换使其实现相当长 - 我想知道是否应该如此。 – TCSGrad

@ shan23只要最低点位于原点，并且在atan2（...）调用中使用逆时针方向的顶点，命名应该从哪里开始。这些要求确保与轴对齐的矩形放置在右上象限内。 – TimFoolery

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

我们需要的是基本上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步& 3（如何找到一个点是否位于矩形内） - 我会用this excellent article（表示有最后的算法）。

来源

2011-08-09 03:29:32 TCSGrad

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

回答

相关问题