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

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

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

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

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

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



倚天杖
浏览 1024回答 3
3回答

尚方宝剑之说

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