矩形与矩形相交的面积 [英] Area of rectangle-rectangle intersection
问题描述
下面是 2 个矩形.给定矩形顶点的坐标-(x1, y1)...(x8, y8)，如何计算重叠区域(下图中的白色)的面积?
注意:
Below are 2 rectangles. Given the coordinates of the rectangle vertices - (x1, y1)...(x8, y8), how can the area of the overlapping region (white in the figure below) be caclulated?
Note that:
- 点的坐标可以是任意的
- 矩形可以重叠也可以不重叠
- 当矩形不重叠，或者它们在点或线处重叠时，假设面积为 0.
- 如果一个矩形在另一个矩形内，则计算较小矩形的面积.
推荐答案
既然你说矩形可能没有对齐，那么可能的答案可能是空无、一个点、一条线段或一个有 3-8 条边的多边形.
Since you stated that the rectangles may not be aligned, possible answers may be nothing, a point, a line segment, or a polygon with 3-8 sides.
执行此2d boolean 操作的通常方法是选择边缘的逆时针顺序，然后评估临界点(交点或角)之间的边缘段.在每个交点处，您可以在第一个矩形的边缘段和第二个矩形的边缘之间切换，反之亦然.您总是选择上一个片段左侧的片段.
The usual way to do this 2d boolean operation is to choose a counterclockwise ordering of the edges, and then evaluate edge segments between critical points (intersections or corners). At each intersection you switch between an edge segment of the first rectangle to an edge of the second, or visa-versa. You always pick the segment to the left of the previous segment.
有很多细节，但基本算法是找到所有交叉点并使用适当的数据结构在它们的边缘上对它们进行排序.选择一个交点(如果有)并选择一条远离该交点的线段.找到所选起始线段左侧的另一个矩形的线段.在图中，我们选择交叉点a(箭头所示方向)上的绿色线段作为参考线段.另一个矩形右侧的线段是从a 到b 的线段.将其用作下一个参考线段，并在其左侧选择一个绿色线段.这是从 b 到 c 的片段.以相同的方式查找段 cd.下一段是从 d 到角点，所以角点也在交点的顶点列表中.从玉米我们回到a.
There are LOTS of details, but the basic algorithm is to find all intersections and order them on their edges with an appropriate data structure. Choose an intersection (if there is one) and choose a line segment leading away from that intersection. Find the segment of the other rectangle to the left of the chosen starting segment. In the picture, we choose the green segment on intersection a (in the direction indicated by the arrow) as the reference segment. The segment of the other rectangle that is to the right, is the segment from a to b. Use that as the next reference segment, and choose a green segment to the left of it. That's the segment from b to c. Find segment cd the same way. The next segment is from d to the corner, so the corner is in the vertex list for the intersection as well. From the corn we get back to a.
要每次选择左侧，请使用相交边的方向向量坐标的确定.如果有序的有向边对的行列式是正的，那么你就走对了.
To choose the left side each time, you use the determinate of the coordinates of the direction vectors for the edges that meet. If the determinant for the ordered pair of directed edges is positive, you're going the right way.
既然您有了相交多边形的顶点，您就可以使用调查者的公式得到面积.
Now that you have the vertices of the intersection polygon, you can use the surveyor's formula to get the area.
我要留给你的一些细节是:
Some of the details that I'm leaving to you are:
如果一个角与另一个三角形的边或顶点重合怎么办?
What if a corner is coincident to to an edge or vertex of the other triangle?
如果没有交叉点怎么办?(一个矩形在另一个里面，或者它们是不相交的——你可以使用多边形点检查来解决这个问题.参见 关于多边形的维基百科文章.
What if there are no intersections? (one rectangle is inside the other, or they are disjoint--you can use point-in-polygon checks to figure this out. See the Wikipedia article on polygons.
如果交点是单点或线段怎么办?
What if the intersection is a single point or a segment?
这篇关于矩形与矩形相交的面积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
