多边形相交区域的算法

Question

我有两个简单的多边形，分别由顶点列表定义。

我需要计算它们的交集面积。我需要一个算法来完成这个任务。

- Darko

---

哈哈哈，一旦完成，我需要一个巧克力派...先生，您有什么努力吗？ - Anshul

我不明白为什么这个问题被标记为不清楚。我没有看到任何模糊之处，这是一个很自然的问题。除了将可能非凸多边形定义为顶点列表之外，你还希望如何定义它？关于多边形区域（可能是不连通的）的交集或面积有什么不清楚的地方吗？ - Douglas Zare

我在考虑添加一个涵盖非凸多边形的答案，但是我不能这样做，因为问题已经关闭了。 - Douglas Zare

很不幸，为什么版主关闭/删除了你看似简单、用简单语言表达的问题。我有解决方案，但现在无法发布。 - markroxor

Answer 1

判断两个多边形是否相交的算法

假设：这些多边形是凸多边形。 （这适用于凸多边形。） 您可以查看此链接以获取更多信息。

为了能够确定两个凸多边形是否相交（彼此接触），我们可以使用分离轴定理。本质上：

• 如果两个凸多边形不相交，则存在一条线穿过它们之间。
• 只有在一个多边形的一侧形成这样一条线时才存在这样的线。

第一个语句很容易理解。由于多边形都是凸的，因此您将能够画出一条线，其中一个多边形在一侧，而另一个多边形在另一侧，除非它们相交。第二个语句略微不太直观。请参见图1。除非多边形的最近边缘彼此平行，否则它们彼此最接近的点是其中一个多边形的一个角落最靠近另一个多边形的一侧。然后，该侧将形成多边形之间的分离轴。如果边缘平行，则它们都是分离轴。

那么这如何具体帮助我们确定多边形A和B是否相交？好吧，我们只需检查每个多边形的每条边是否形成分离轴即可。为此，我们将使用一些基本的向量数学，将两个多边形的所有点压缩到垂直于潜在分离线的线上（请参见图2）。现在整个问题方便地变成了一维问题。我们可以确定每个多边形的点所在的区域，如果这些区域不重叠，则该线是分离轴。

如果在检查来自两个多边形的每条线后未找到分离轴，则已经证明多边形相交，必须采取某些措施。

注意：此SO问题出色地描述了此部分。我从这个问题中使用了此部分。

如果重叠，则公共区域（近似）覆盖的区域

算法简单地按如下方式工作：

算法从主题多边形的所有顶点列表开始。接下来，剪辑多边形的一侧在两个方向上无限延伸，并遍历主题多边形的路径。如果输入列表中的顶点位于延长的剪辑多边形线的可见侧，则将其插入到输出列表中，并在主题多边形路径穿过延长的剪辑多边形线时向输出列表添加新顶点。

有关更多详细信息，请访问这些链接

• 点击此处了解Sutherland-Hodgman算法在物理引擎中的应用。

• 点击此处了解Sutherland-Hodgman算法的详细信息。

凸多边形的面积

一个凸多边形的坐标 (x1, y1), (x2, y2), (x3, y3), . . . , (xn, yn) 必须按照逆时针的顺序围绕多边形排列，开始和结束点相同。这些坐标被排列在下面的行列式中。

             | x1 y1 |
             | x2 y2 |
             | x3 y3 |
Area= (1/2)* | .. .. |
             | .. .. |
             | xn yn |
             | x1 y1 |

    = (1/2)[(x1*y2+x2*y3+...xn*y1)- (y1*x2+y2*x3+...+yn*x1)]

以下是解决问题的步骤，请按照步骤操作。希望能对你有所帮助。

- user2736738

---

你是否添加了多边形是凸多边形的假设？ - Douglas Zare

@DouglasZare：好的，谢谢。我已经添加了它。 - user2736738