两个旋转矩形的交点面积

Question

我有两个2D矩形,定义为原点(x,y)的大小(高度,宽度)和旋转角度(0-360°).我可以保证两个矩形的大小相同.

我需要计算这两个矩形的近似交叉区域.

计算不需要精确,尽管可以.我将把结果与其他交叉区域进行比较,以确定一组矩形中最大的交叉区域,因此它只需要相对于同一算法的其他计算准确.

我想过使用相交区域的边界框区域,但由于所有不同的可能情况,我无法获取相交区域的顶点:

我正在Cocoa框架中的Objective-C中编写这个程序,这是值得的,所以如果有人知道任何快捷方式使用NSBezierPath或者你也欢迎提出建议.

Answer 1

为了补充其他答案,您的问题是线裁剪的一个实例,一个在计算机图形学中经过深入研究的主题,并且有许多算法可用.如果旋转坐标系使一个矩形具有水平边,那么问题就是从那里开始的线剪裁.

您可以从关于该主题的维基百科文章开始,并从那里进行调查.

Answer 2

一个可以给出近似答案的简单算法是采样。

将您的一个矩形划分为小正方形的网格。对于每个相交点，检查该点是否在另一个矩形内。位于另一个矩形内的点的数量将非常接近重叠区域的面积。增加点的密度会提高计算的准确性，但会降低性能。