24

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

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

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

我考虑过使用相交区域的边界框区域，但由于所有不同的可能情况，我无法获取相交区域的顶点： 这么多可能的交叉点形状

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

4

6 回答 6

9

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

您可以从有关该主题的 Wikipedia 文章开始，然后从那里进行调查。

于 2012-07-26T15:07:19.780 回答
7

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

将您的一个矩形分成小正方形的网格。对于每个交点，检查该点是否在另一个矩形内。位于另一个矩形内的点数将很好地近似于重叠区域的面积。增加点的密度将提高计算的准确性，但会以性能为代价。

于 2012-07-26T13:14:26.647 回答
4

在任何情况下，计算两个凸多边形的精确交多边形是一件容易的事，因为任何凸多边形都可以看作是半平面的交集。“连续切割”可以完成这项工作。

选择一个矩形（任意）作为切割矩形。一个接一个地遍历切割矩形的边。通过包含切割矩形当前边的线切割第二个矩形，并丢弃位于“外部”半平面中的所有内容。

一旦你完成了所有切割边的迭代，剩下的就是另一个矩形的结果。

于 2012-07-26T14:52:01.667 回答
3

您实际上可以计算确切的面积。

  1. 从两个矩形中制作一个多边形。看到这个问题（尤其是这个答案），或者使用gpc库。
  2. 求这个多边形的面积。见这里。

  3. 共享区域是

    area of rectangle 1 + area of rectangle 2 - area of aggregated polygon
于 2012-07-26T13:29:45.880 回答
1

取每个矩形的每个线段，看看它们是否相交。会有几种可能：

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

  2. a 如果一个矩形的两条连续边与另一个矩形的一条边相交，则形成一个三角形。计算它的面积。

    湾。如果边不是连续的，则形成四边形。从四边形的两个对角计算一条线，这会产生两个三角形。计算每个的面积并求和。

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

  4. 如果一个的每个边缘与另一个的每个边缘相交，您将有一个八边形。将其分解为三角形（例如，从一个顶点到另一个顶点绘制一条射线以形成 4 个三角形）

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

检查1中的特殊情况。

然后从任何相交的顶点开始，沿着边缘从那里到任何其他相交点，直到回到第一个相交的顶点。这形成了一个凸多边形。从第一个顶点到每个相对的顶点绘制一条射线（例如跳过左右的顶点。）这会将它分成一堆三角形。计算每个的面积并求和。

于 2012-07-26T14:08:04.863 回答
1

蛮力式的方式：

  • 从 [矩形的角] + [边缘的交点] 集合中获取所有点
  • 删除不在两个矩形内部或边缘上的点。
  • 现在你有路口的角落。请注意，交点是凸的。
  • 按集合中任意点、任意其他点和给定点之间的角度对剩余点进行排序。
  • 现在您已经按顺序排列了交点。
  • 以通常的方式计算面积（通过叉积）

.

于 2012-07-26T14:34:18.843 回答