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

Question

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

我不介意运行时间(我有一些非常小的多边形),我也可以得到一个近似的多边形交叉点(也就是说,一个点数较少的多边形,但它仍包含在多边形的交叉点中).

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

编辑:请注意,我希望获得一个代表交叉点的多边形.对于两个多边形是否相交的问题,我不需要一个布尔答案.

Answer 1

我理解原始海报正在寻找一个简单的解决方案,但不幸的是,确实没有简单的解决方案.

不过,我最近创建了一个开源免费软件剪辑库(用Delphi,C++和C#编写),它剪辑了各种多边形(包括自相交的多边形).这个库使用起来非常简单:http://sourceforge.net/projects/polyclipping/.

Answer 2

您可以使用多边形剪切算法来查找两个多边形之间的交集.然而,当考虑所有边缘情况时,这些往往是复杂的算法.

您可以使用自己喜欢的搜索引擎查找的多边形裁剪的一个实现是Weiler-Atherton.关于Weiler-Atherton的维基百科文章

Alan Murta完全实现了多边形裁剪器GPC.

编辑:

另一种方法是首先将每个多边形划分为一组三角形,这些三角形更容易处理.该两耳朵定理由Gary H. Meisters的伎俩.McGill的这个页面很好地解释了三角形细分.

Answer 3

如果您使用C++,并且不想自己创建算法,则可以使用Boost.Geometry.它使用上面提到的Weiler-Atherton算法的改编版本.

Answer 4

你还没有给我们你的多边形表示.所以我选择(更像是建议)一个给你:)

将每个多边形表示为一个大凸多边形,以及需要从该大凸多边形"减去"的较小凸多边形的列表.

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

计算大凸多边形的交点,形成交点的大多边形.然后'减去'两者中所有较小的交点,得到一个减法多边形列表.

您将获得一个遵循相同表示的新多边形.

由于凸多边形交叉很容易,这种交点发现也应该很容易.

这似乎应该有效,但我没有在正确性/时间/空间复杂性方面给予更深入的思考.

Answer 5

这是一种简单而愚蠢的方法：在输入时，将多边形离散化为位图。为了相交，将位图与在一起。要产生输出多边形，请找出位图的锯齿状边界，并使用多边形逼近算法对锯齿进行平滑处理。（我不记得该链接是否提供了最合适的算法，这只是Google的第一个热门产品。您可以查看其中的一种工具，将位图图像转换为矢量表示。也许您可以在不重新实现算法的情况下调用它们？）

我认为，最复杂的部分是划定边界。

顺便说一句，在90年代初期，我在工作中遇到了类似的问题。我闷闷不乐：我想出了一种（完全不同的）算法，该算法可以在实数坐标上工作，但是面对浮点数（和嘈杂的输入）的现实，似乎陷入了一个完全不可修复的退化案例中。 。也许借助互联网，我会做得更好！

Answer 6

这是一种基于三角测量的方法,它非常简单,可以在O(N ²)中运行.

BTW,O(N ²)对于这个问题是最佳的.想象一下两个多边形形状像干草叉刀片以直角相交.每个都有一些与尖齿数量成比例的部分; 交叉点中多边形的数量与尖齿数的平方成正比.

1. 首先,对每个多边形进行三角测量.

2. 将P中的所有三角形与Q中的所有三角形进行比较,以检测交叉点.任何一对相交的三角形都可以分成较小的三角形,每个三角形都在P,Q或交叉点中.(无论你在步骤1中使用什么,都可以重复使用来帮助解决这个问题.)只保留交叉点中的三角形.

3. 通过成对比较每个三角形的邻居,并构建邻接图.该图将包含P和Q交叉点中每个多边形的一个连通子图.

4. 对于每个这样的子图,选择一个三角形,走到边缘,然后在边缘处走动,产生限定相应输出多边形的线段.