为了账号安全,请及时绑定邮箱和手机立即绑定

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

/ 猿问

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

倚天杖 2019-08-02 16:02:35

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

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

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

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

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



查看完整描述

3 回答

?
白衣非少年

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

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


查看完整回答
反对 回复 2019-08-03
?
慕村225694

你可以用一个多边形裁剪求两个多边形交集的算法。然而,当考虑到所有的边缘情况时,这些算法往往是复杂的。

可以使用您最喜欢的搜索引擎查找的多边形裁剪的一个实现是韦勒-阿瑟顿. 维基百科关于韦勒-阿瑟顿的文章

AlanMurta有一个多边形裁剪器的完整实现。GPC.

编辑:

另一种方法是首先将每个多边形划分成一组三角形,这些三角形更容易处理。这个双耳定理加里·H·梅斯特的作品。这,这个麦吉尔很好地解释了三角剖分。




查看完整回答
反对 回复 2019-08-03
?
尚方宝剑之说

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

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

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

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

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

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

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




查看完整回答
反对 回复 2019-08-03
  • 3 回答
  • 0 关注
  • 124 浏览
我要回答
慕课专栏
更多

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信