两个循环矩形的交集的区域(Area of Intersection of Two Rotated R

我有两个2D矩形，定义为原点 （x，y）处的尺寸 （高度，宽度）和转动角度 （0-360°）。 我可以保证，两个矩形的大小相同。

我需要计算这两个矩形的交集的大致区域。

计算并不需要准确的说，虽然它可以。 我会比较相交确定一组矩形的交集面积最大其他地区的结果，所以只需要相对于相同的算法的其他计算精确到是。

我想过使用相交区域的边界框的面积，但我遇到了麻烦贯穿的区域的，因为所有的不同可能情况的顶点：

我在Cocoa框架编写这个程序的Objective-C，对于它的价值，所以如果有人知道使用任何快捷键NSBezierPath什么欢迎您的建议了。

Answer 1:

一个简单的算法，这将使大概的答案是采样。

把你的矩形的一个成小方块的网格。 对于每一个交叉点，检查是否该点是其他矩形内。 摆在另一矩形内的点的数目将是一个相当良好的近似，以重叠区域的面积。 增加点的密度将提高计算的精度，性能为代价。

Answer 2:

为了补充其他的答案，你的问题是线裁剪的一个实例，一个沉重的话题研究了计算机图形，且有很多可用的算法。 如果你旋转你的坐标系，使一个矩形的水平边缘，那么问题是完全线从那里裁剪。

你可以在开始的话题维基百科的文章 ，并从那里调查。

Answer 3:

在任何情况下，计算两个凸多边形的确切相交多边形是一件容易的事，因为任何凸多边形可以被看作是半平面的交点。 “连续切削”做这项工作。

选择一个矩形（任何）作为切割矩形。 通过切割矩形的边迭代，一个接一个。 削减由包含切割矩形的电流侧的线的第二矩形和丢弃出在“外”半平面的一切。

一旦你完成在所有切割面迭代，剩下的其他矩形的是结果。

Answer 4:

实际上，你可以计算出精确的区域。

1. 让一个多边形了两个矩形的。 见这个问题 （尤其是这个答案 ），或使用GPC库。
2. 找到这个多边形的面积。 见这里 。

3. 共享区

    area of rectangle 1 + area of rectangle 2 - area of aggregated polygon 

Answer 5:

以每个矩形的每条线段，看他们是否相交。 将有几种可能：

1. 如果没有相交 - 共享区域为零 - 除非所有的点都在另一个内。 在这种情况下共享区域是较小的一个的面积。

2. a。如果一个rectactangle的两个连续的边缘与另一个矩形的单个边缘相交，这形成一个三角形。 计算其面积。

   湾 如果边缘没有consequtive，这形成了一个四边形。 计算从四边形的两个相对的角的线，这使得两个三角形。 计算每总和的面积。

3. 如果一个人的两条边与另外两个边相交，那么你将有一个四边形。 计算为2B。

4. 如果一个人的每个边缘与其他的每个边缘相交，你将有一个八边形。 它分解成三角形（例如，从一个顶点画一个射线彼此顶点，使4个三角形）

@edit：我有一个更通用的解决方案。

检查1的特殊情况。

然后用任何相交的顶点开始，并按照相应的边缘到任何其他的交点，直到你又回到了第一相交顶点。 这形成了一个凸多边形。 从第一顶点到每个相对VETEX绘制射线（例如跳过顶点至左边和右边。）这将它分成一束三角形。 计算每个与和地区。

Answer 6:

蛮力上下的方式：

• 采取的所有点从集合[矩形的拐角] +的[边缘的交点]
• 删除不内侧或两个矩形的边缘的点。
• 现在你有交集的角落。 注意，交叉点是凸的。
• 通过从该组，任意其他点，和给定的点的任意点之间的角度的剩余点进行排序。
• 现在你有交点的秩序。
• 计算面积的通常的方式（通过叉积）

。

文章来源: Area of Intersection of Two Rotated Rectangles