矩形 - 矩形交点的面积 [英] 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:

1. 点数坐标可以是任何


2. 矩形可能重叠或可能不重叠


3. 假设矩形不重叠时的面积为0，或者它们在点或线重叠。


4. 如果一个矩形在另一个矩形内，则计算较小矩形的面积。

1. Coordinates of points might be any
2. Rectangles may or may not overlap
3. Assume area is 0 when rectangles don't overlap, or they overlap at point or line.
4. If one rectangle is inside the other, then calculate area of smaller rectangle.

推荐答案

可能没有对齐，可能的答案可能没有，一个点，一个线段或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（以箭头指示的方向）上的绿色段作为参考段。右边另一个矩形的段是从 到 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.

如果交集是单点或分段， li>

What if the intersection is a single point or a segment?

这篇关于矩形 - 矩形交点的面积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！