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

Question

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

我正在寻找一个非常简单的算法来计算多边形的交集/裁剪。也就是说，给定多边形P, Q，我想找到多边形T它包含在P和在Q，我希望T在所有可能的多边形中最大。

我不介意运行时间(我有几个非常小的多边形)，我也可以得到多边形交点的近似(即点较少的多边形，但它仍然包含在多边形的交集中)。

但对我来说非常重要的是，算法将是简单的(更便宜的测试)，最好是短(少代码)。

编辑：请注意，我希望得到一个表示交集的多边形。对于这两个多边形是否相交的问题，我不需要一个布尔的答案。

Answer 1

你还没有给我们你的多边形的表示法。因此，我选择(更像是建议)一个给你：)将每个多边形表示为一个大凸多边形，以及一个需要从那个大凸多边形中“减去”的小凸多边形列表。现在，给定该表示中的两个多边形，您可以将交集计算为：计算大凸多边形的相交，形成交的大多边形。然后“减去”所有较小的多边形的交点，得到一个相减多边形的列表。在相同的表示形式下，你会得到一个新的多边形。由于凸多边形相交很容易，这种求交也应该很容易。这似乎是可行的，但我还没有对正确性/时间/空间复杂性进行更深入的思考。