如何交叉两个多边形？

Question

这似乎并不重要(它在各种论坛上得到了很多讨论),但我绝对需要将它作为更复杂算法的构建块.

输入:2D中的2个多边形(A和B),以[(x0, y0, x1, y2), ...]每个边的列表形式给出.这些点由doubles 对表示.我不知道它们是顺时针,逆时针还是任何方向.我不知道他们不一定是凸的.

输出:表示A,B和交叉多边形AB的3个多边形.其中任何一个都可以是空(？)多边形,例如null.

优化提示:这些多边形代表房间和楼层边界.所以房间边界通常与地面边界完全相交,除非它属于同一平面上的另一层(argh!).

我有点希望有人已经在c#中完成了这个并且让我使用他们的策略/代码,因为到目前为止我在这个问题上发现的是相当艰巨的.

编辑:所以看起来我并不完全是鸡,因为这样做的前景微弱.我想在这里重述所需的输出,因为这是一个特例,可能会使计算更简单:

输出:第一个多边形减去所有相交的位,交叉多边形(复数是正常的).我对第二个多边形并不感兴趣,只是它与第一个多边形的交集.

EDIT2:我目前正在使用GPC(General Polygon Clipper)库,这非常容易!

Answer 1

Arash Partow的FastGEO库包含计算几何中许多有趣算法的实现.多边形交叉点就是其中之一.它是用Pascal编写的,但它只是实现数学所以它非常易读.请注意,您肯定需要稍微预处理边缘,以使它们顺时针或逆时针顺序.

ETA:但实际上,最好的办法就是不要这样做.找到另一种方法来解决不涉及任意多边形交叉的问题.

Answer 2

如果您使用.NET Framework进行编程,您可能需要查看作为Microsoft SQL Server系统CLR类型提供的.NET程序集中提供的SqlGeometry类

SqlGeometry类提供STIntersection方法

SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry intersection = g1.STIntersection(g2);

Answer 3

我认为你应该做什么

如果你可以帮助它,不要试图自己这样做.而是使用已存在的许多可用多边形交集算法之一.

我强烈考虑下面的代码库,他们的演示代码的强度以及他们提到他们处理大多数/所有奇怪案例的事实.如果你在商业上使用它,你需要捐赠一定数量(你/你公司的选择),但是获得这种代码的强大版本是值得的.

http://www.cs.man.ac.uk/~toby/gpc/

我实际上做的是使用作为Java2D库一部分的多边形交集算法.您可以在MS自己的C#库中找到类似的东西来使用.

还有其他选择; 寻找"多边形裁剪器"或"多边形裁剪",因为处理多边形交叉的相同基本算法也倾向于可用于一般裁剪情况.

实际上有一个多边形裁剪库之后,您只需要从多边形A中减去多边形B以获得第一个输出,并与多边形A和B相交以获得第二个输出.

如何滚动自己,为无望的自虐

当我考虑自己动手时,我发现Weiler-Atherton算法最有可能进行一般多边形切割.我使用以下作为参考:

http://cs1.bradley.edu/public/jcm/weileratherton.html

http://en.wikipedia.org/wiki/Weiler-Atherton

正如他们所说,细节太密集了,不能包含在这里,但我毫不怀疑你将能够在未来几年内找到Weiler-Atherton的参考资料.从本质上讲,拆分的所有点到那些进入最后多边形或退出的最后多边形,则形成一个图的所有点,然后走在适当的方向,以提取所有多边形件的图表你想.通过更改定义和处理"输入"和"退出"多边形的方式,可以实现多个可能的多边形交叉(AND,OR,XOR等).

它实际上是相当可行的,但与任何计算几何代码一样,魔鬼处于退化状态.