一种简单的多边形求交算法

Question

一种简单的多边形求交算法我正在寻找一个非常简单的算法来计算多边形的交集/裁剪。也就是说，给定多边形P, Q，我想找到多边形T它包含在P和在Q，我希望T在所有可能的多边形中最大。我不介意运行时间(我有几个非常小的多边形)，我也可以得到多边形交点的近似(即点较少的多边形，但它仍然包含在多边形的交集中)。但对我来说非常重要的是，算法将是简单的(更便宜的测试)，最好是短(少代码)。编辑：请注意，我希望得到一个表示交集的多边形。对于这两个多边形是否相交的问题，我不需要一个布尔的答案。

Answer 1

我知道最初的海报是在寻找一个简单的解决方案，但不幸的是，真的没有简单的解决方案。

尽管如此，我最近创建了一个开源的免费裁剪库(用Delphi、C+和C#编写)，它剪辑了各种多边形(包括自相交的多边形)。这个库非常容易使用：http://sourceforge.net/projects/polyclipping/ .

Answer 2

你还没有给我们你的多边形的表示法。因此，我选择(更像是建议)一个给你：)

将每个多边形表示为一个大凸多边形，以及一个需要从那个大凸多边形中“减去”的小凸多边形列表。

现在，给定该表示中的两个多边形，您可以将交集计算为：

计算大凸多边形的相交，形成交的大多边形。然后“减去”所有较小的多边形的交点，得到一个相减多边形的列表。

在相同的表示形式下，你会得到一个新的多边形。

由于凸多边形相交很容易，这种求交也应该很容易。

这似乎是可行的，但我还没有对正确性/时间/空间复杂性进行更深入的思考。