如何使两个多边形相交?

我觉得你应该怎么做

如果可能的话,不要试图自己去做。相反,使用已经存在的许多可用多边形交叉算法之一。

我在强烈考虑以下代码的基础上,他们的演示代码和事实上,他们提到了他们处理大多数/所有奇怪的案例。如果你在商业上使用它,你需要捐一笔钱(你/你公司的选择),但是得到这种代码的强大版本是值得的。

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

我实际做的是使用一个多边形交集算法,它是java2d库的一部分。你可以在微软自己的C库中找到类似的东西。

还有其他的选择;寻找“多边形裁剪器”或“多边形裁剪”,因为处理多边形交叉点的相同基本算法也适用于一般的裁剪情况。

一旦你有了一个多边形裁剪库,你只需要从多边形A中减去多边形B就可以得到你的第一个输出,然后与多边形A和B相交就可以得到你的第二个输出。

如何为绝望的受虐狂滚自己的

当我考虑自己滚动时,我发现威勒-阿瑟顿算法对一般多边形切割最有潜力。我将以下内容作为参考:

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

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

正如他们所说,这些细节太过繁琐,不可能包括在这里,但我毫不怀疑,在未来的几年里,你会找到韦勒·阿瑟顿的参考资料。基本上,将所有点拆分为进入最终多边形或退出最终多边形的点,然后从所有点中形成一个图,然后沿着适当的方向移动该图,以提取所需的所有多边形块。通过更改定义和处理“进入”和“退出”多边形的方式,可以实现多个可能的多边形交点(和、或、异或等)。

它实际上是相当可实现的,但与任何计算几何代码一样,最糟糕的是退化。

Arash Partow FastGEO 该库包含许多计算几何中有趣算法的实现。多边形交点就是其中之一。它是用帕斯卡写的,但它只是实现数学,所以可读性很好。请注意,您当然需要对边缘进行一点预处理,以使它们按顺时针或逆时针顺序排列。

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

如果您正在.NET框架中编程,您可能需要查看.NET程序集中作为 Microsoft SQL Server System CLR Types

sqlgeometry类提供 STIntersection 方法

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

你也可以看看 NetTopologySuite 甚至可以尝试将其导入到SQL Server 2008&it的空间工具中。

多边形完全由点的有序列表(p1,p2,…,pn)描述。边缘是(p1-p2),(p2-p3),…,(pn-p1)。如果有两个重叠的多边形A和B,则会有一个点A(从描述多边形A的点列表中)位于多边形B包围的区域内,反之亦然(B的点位于A中)。如果没有找到这样的点,那么多边形就不会重叠。如果找到这样一个点(即a i),检查多边形a(i-1)和a(i+1)的相邻点。重复此操作,直到在区域外找到一个点或选中所有点(然后第一个多边形完全位于第二个多边形内)。如果你在外面找到一个点,那么你可以计算出交叉点。找到多边形B的对应边,然后使用resersed roles=跟随它,现在检查多边形B的点是否位于多边形A内。这样,您可以构建描述重叠多边形的点列表。如果需要,您应该检查多边形是否相同,(p1,p2,p3)==(p2,p3,p1)。

这只是一个想法,也许还有更好的方法。如果你找到一个有效且经过测试的解决方案,我建议你使用它…

麻醉的

尝试使用地理信息系统工具,例如arcObjects、topologySuite、geos、ogr等。我不确定所有这些分布是否都可以用于.net,但它们都可以。

剪刀是一种 开源免费软件 多边形裁剪库(用Delphi和C++编写)完全符合你的要求。 http://sourceforge.net/projects/polyclipping/

在我的测试中,与gpc相比,clipper速度更快,而且更不容易出错(请参阅下面更详细的比较- http://www.angusj.com/delphi/clipper.php#features )此外,尽管Delphi和C++都有源代码,但是clipple库还包括一个编译的DLL,以便在其他(Windows)语言中也很容易使用剪辑功能。

这个 academic paper 解释如何执行此操作。

如果你敢看别人的GPL C++代码,你可以看到他们是如何在

http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (第126行)