logo标签列表

两个旋转矩形的交集区域

algorithmgraphicsgeometryintersection
27
我有两个二维矩形，定义为一个原点（x，y），一个大小（高度，宽度）和旋转角度（0-360°）。我可以保证这两个矩形的大小相同。
我需要计算这两个矩形相交的近似面积。 Rectangle intersection 计算不需要精确，尽管可以。我将比较结果与其他相交区域的面积，以确定一组矩形中的最大相交面积，因此只需要相对于同一算法的其他计算准确即可。
我考虑使用相交区域的边界框面积，但由于所有可能的情况，我无法获得相交区域的顶点： So many possible intersection shapes 就我所知，我正在使用Cocoa框架中的Objective-C编写此程序，因此，如果有人知道使用NSBezierPath或其他快捷方式，请随时提出建议。
我不太清楚您需要的内容。但我认为两个矩形最大的交集面积总是等于其中一个矩形的面积，因为这两个矩形的面积相同。 - Narendra
@rain，他不想要最大可能的交集面积，而是两个给定矩形的实际交集面积。 - Shahbaz
是的，你说得对。但在问题中他提到了“我可以保证两个矩形的大小相同。”和“我将比较结果与其他交叉区域的面积来确定一组矩形中最大的交叉面积”。所以我怀疑需要什么样的解决方案。 - Narendra
@Rain，Shahbaz是正确的；我有一组矩形--在这个集合中，我需要确定任意两个矩形之间最大的交集面积。我提到这个只是为了说明为什么我需要能够找到两个矩形的交集面积。 - Nate Thorn
这本质上是 https://dev59.com/82sz5IYBdhLWcg3wR1kc 的副本。 - Codie CodeMonkey
6个回答
12
为了补充其他答案，你的问题是“线段裁剪”的一个实例，这是计算机图形学中研究得非常深入的一个主题，有许多可用的算法。如果您旋转坐标系，使一个矩形有一条水平边，那么从那里开始，问题就完全变成了线段裁剪。您可以从维基百科文章开始调查。
9

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

将其中一个矩形分成小正方形的网格。对于每个交点，请检查该点是否在另一个矩形内部。位于另一个矩形内部的点的数量将是重叠区域面积的相当好的近似值。增加点的密度会提高计算的准确性，但会降低性能。

1
由于在我的情况下，开发时间比效率或准确性更为重要，因此我选择了这个答案。但是，请查看其他答案以获取更高效/准确的解决方案。 - Nate Thorn
1
如果您有一个网格，您可以使用皮克定理 http://en.wikipedia.org/wiki/Pick%27s_theorem - Ismael
4
无论如何，计算两个凸多边形的精确交集是一项容易的任务，因为任何凸多边形都可以看作是半平面的交集。"顺序切割"可以完成这项工作。
选择一个矩形（任意一个）作为切割矩形。逐个迭代切割矩形的边缘。通过包含当前切割矩形侧的线条切割第二个矩形，并丢弃位于"外部"半平面的所有内容。
一旦你完成了所有切割边的迭代，另一个矩形中剩余的部分就是结果。
3
你可以准确计算出面积。
  1. Make one polygon out of the two rectangles. See this question (especially this answer), or use the gpc library.
  2. Find the area of this polygon. See here.

  3. The shared area is

    area of rectangle 1 + area of rectangle 2 - area of aggregated polygon
您提供的链接似乎没有完全解释如何实现第一步？该问题没有被接受的答案。 - Mark Byers
@MarkByers，是的，但那个问题的提问者有30%的未被采纳的答案。那里有很多解决方案，肯定有一个会起作用。不过我还会继续搜索。 - Shahbaz
我很高兴不是只有我一个人这样，我以为我理解了，但现在我正在尝试实现它时，我卡在了尝试形成两个矩形的并集上；假设我能找到交点，这些点的顺序是什么？ - Nate Thorn
@NateThorn，我更新了我的回答并介绍了一个可以完成这个功能的库。你也可以在互联网上搜索更多关于这个具体子问题的信息。 - Shahbaz
如果您要使用gpc库，则无需执行这三个步骤。它可以直接计算交集。 "支持差异，交集，异或和联合剪辑操作。" - Mark Byers
显示剩余3条评论
1

对于每个矩形的每条线段，检查它们是否相交。可能会有几种情况：

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

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

    b. 如果边不是相邻的，则形成一个四边形。从四边形的两个对角线上计算一条直线，这将形成两个三角形。计算每个三角形的面积并求和。

  3. 如果一个矩形的两条边与另一个矩形的两条边相交，则你将得到一个四边形。按照2b的方法计算。

  4. 如果一个矩形的每条边都与另一个矩形的每条边相交，则你将得到一个八边形。将其分解为三角形（例如，从一个顶点向每个其他顶点绘制一条射线以形成4个三角形）

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

检查第1种情况的特殊情况。

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

如果一个矩形的两条边与另一个矩形的一条边相交，就会形成一个三角形。或者是一个矩形。 - Mark Byers
再给你举一个例子：“如果一个矩形的两条相邻边与另一个矩形的一条边相交，就会形成一个三角形”……或五边形。 - Mark Byers
有一个更通用的解决方案。我会简要概述一下。 - Rafael Baptista
1
@RafaelBaptista，您还漏掉了六边形的情况：http://screenshoot.me/IMQZcV - Pacerier
1
一种类似于暴力的方法：
  • 从[矩形的角] + [边缘交点]集合中获取所有点
  • 删除不在或不在两个矩形内部或边缘上的点。
  • 现在你有了交点的角落。请注意，交点是凸的。
  • 按任意点集、任意其他点和给定点之间的角度对剩余点进行排序。
  • 现在您按顺序拥有交点。
  • 通常的方式计算面积（通过叉积）

.

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接