c# - 如何使两个多边形相交？

Question

这似乎很重要（在各种论坛上被问了很多），但我绝对需要它作为更复杂算法的构建块。

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

输出：代表 A、B 和相交多边形 AB 的 3 个多边形。其中任何一个都可能是空 (?) 多边形，例如null.

优化提示：这些多边形代表房间和地板的边界。所以房间边界通常会与楼层边界完全相交，除非它属于同一平面上的另一个楼层（啊！）。

我有点希望有人已经在 c# 中做到了这一点，并让我使用他们的策略/代码，因为到目前为止我在这个问题上发现的内容相当令人生畏。

编辑：所以看起来我并不完全因为这样做而感到头晕目眩。我想在这里重申所需的输出，因为这是一种特殊情况，可能会使计算更简单：

输出：第一个多边形减去所有相交位，相交多边形（复数可以）。我对第二个多边形并不感兴趣，只是它与第一个多边形的交集。

EDIT2：我目前正在使用GPC（通用多边形剪裁器）库，这使得这非常容易！

score 17 · Accepted Answer

Arash Partow 的FastGEO库包含计算几何中许多有趣算法的实现。多边形相交就是其中之一。它是用 Pascal 编写的，但它只是实现数学，所以它非常易读。请注意，您肯定需要对边缘进行一些预处理，以使它们按顺时针或逆时针顺序排列。

ETA：但实际上，最好的方法是不这样做。找到另一种不涉及任意多边形交叉点的方法来解决您的问题。

score 14 · Accepted Answer

如果您在 .NET Framework 中进行编程，您可能需要查看作为Microsoft SQL Server System CLR Types提供的 .NET 程序集中可用的 SqlGeometry 类

SqlGeometry 类提供STIntersection方法

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

score 11 · Accepted Answer

我认为你应该做什么

如果您能帮上忙，请不要尝试自己做这件事。相反，使用已经存在的许多可用的多边形相交算法之一。

我根据他们的演示代码的强度以及他们提到他们对大多数/所有奇怪案例的处理这一事实，强烈考虑了以下代码库。如果您将其用于商业用途，您将需要捐赠一定数量（您/您公司的选择），但获得此类代码的强大版本是值得的。

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 等）。

它实际上是相当可实现的，但就像任何计算几何代码一样，魔鬼在退化中。

score 3 · Accepted Answer

您可能还想看看NetTopologySuite，甚至尝试将其导入 Sql server 2008 和它的空间工具。

score 3 · Accepted Answer

Clipper 是一个开源免费软件多边形裁剪库（用 Delphi 和 C++ 编写），它完全符合您的要求 - http://sourceforge.net/projects/polyclipping/

在我的测试中，Clipper 比 GPC 快得多，而且更不容易出错（在此处查看更详细的比较 - http://www.angusj.com/delphi/clipper.php#features）。此外，虽然有 Delphi 和 C++ 的源代码，但 Clipper 库还包括一个已编译的 DLL，以便在其他 (Windows) 语言中使用剪辑功能也非常容易。

score 2 · Accepted Answer

如果你敢看别人的 GPL C++ 代码，你可以看看他们在 Inkscape 中是如何做到的：

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

score 2 · Accepted Answer

多边形由点的有序列表 (P1, P2, ..., Pn) 完全描述。边缘是 (P1 - P2), (P2 - P3), ..., (Pn - P1)。如果您有两个重叠的多边形 A 和 B，则将有一个点 An（来自描述多边形 A 的点列表）位于多边形 B 包围的区域内，反之亦然（B 的一个点位于 A 中）。如果没有找到这样的点，则多边形不会重叠。如果找到这样的点（即 Ai），则检查多边形 A(i-1) 和 A(i+1) 的相邻点。重复直到找到该区域外的一个点或检查所有点（然后第一个多边形完全位于第二个多边形内）。如果你在外面找到一个点，那么你可以计算交叉点。找到多边形 B 的对应边，然后使用重新分配的角色跟随它 = 现在检查多边形 B 的点是否位于多边形 A 内。这样，您可以构建描述重叠多边形的点列表。如果需要，您应该检查多边形是否相同，（P1，P2，P3）===（P2，P3，P1）。

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

清醒的

score 2 · Accepted Answer

尝试为此使用 GIS 工具，例如 ArcObjects、TopologySuite、GEOS、OGR 等。我不确定所有这些发行版是否都可用于 .net，但它们都一样。

score 2 · Accepted Answer

2

这篇学术论文解释了如何做到这一点。

于 2011-10-05T00:25:37.417 回答

c# - 如何使两个多边形相交？

9 回答 9

Related

Reference