两个旋转矩形相交的面积 [英] Area of Intersection of Two Rotated Rectangles

问题描述

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

我需要计算这两个矩形的相交面积。

计算<尽管可以，但并不一定要准确。我会将结果与其他交集区域进行比较，以确定矩形集合中交集的最大面积，因此它只需要相对于同一算法的其他计算精确。

>

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

I在Cocoa框架中的Objective-C中编写这个程序是值得的，所以如果有人知道使用 NSBezierPath 的快捷方式，或者欢迎您提供一些建议。

解决方案

将你的一个矩形分成小方格。对于每个交点，检查该点是否在另一个矩形内。位于另一个矩形内的点的数量对于重叠区域的面积来说是相当好的近似值。增加点的密度将以性能为代价提高计算的准确性。

I have two 2D rectangles, defined as an origin (x,y) a size (height, width) and an angle of rotation (0-360°). I can guarantee that both rectangles are the same size.

I need to calculate the approximate area of intersection of these two rectangles.

The calculation does not need to be exact, although it can be. I will be comparing the result with other areas of intersection to determine the largest area of intersection in a set of rectangles, so it only needs to be accurate relative to other computations of the same algorithm.

I thought about using the area of the bounding box of the intersected region, but I'm having trouble getting the vertices of the intersected region because of all of the different possible cases:

I'm writing this program in Objective-C in the Cocoa framework, for what it's worth, so if anyone knows any shortcuts using NSBezierPath or something you're welcome to suggest that too.

解决方案

A simple algorithm that will give an approximate answer is sampling.

Divide one of your rectangles up into grids of small squares. For each intersection point, check if that point is inside the other rectangle. The number of points that lie inside the other rectangle will be a fairly good approximation to the area of the overlapping region. Increasing the density of points will increase the accuracy of the calculation, at the cost of performance.

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