C# 如何相交两个多边形？

How to intersect two polygons?

提问by Daren Thomas

This seems non-trivial (it gets asked quite a lot on various forums), but I absolutely need this as a building block for a more complex algorithm.

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

Input: 2 polygons (A and B) in 2D, given as a list of edges [(x0, y0, x1, y2), ...]each. The points are represented by pairs of doubles. I do not know if they are given clockwise, counter-clockwise or in any direction at all. I doknow that they are not necessarily convex.

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

Output: 3 polygons representing A, B and the intersecting polygon AB. Either of which may be an empty (?) polygon, e.g. null.

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

Hint for optimization: These polygons represent room and floor boundaries. So the room boundary will normally fully intersect with the floor boundary, unless it belongs to another floor on the same plane (argh!).

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

I'm kind of hoping someone has already done this in c# and will let me use their strategy/code, as what I have found so far on this problem is rather daunting.

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

EDIT: So it seems I'm not entirely chicken for feiling faint at the prospect of doing this. I would like to restate the desired output here, as this is a special case and might make computation simpler:

编辑：所以看起来我并不完全是因为对这样做的前景感到昏昏欲睡。我想在这里重申所需的输出，因为这是一个特殊情况，可能会使计算更简单：

Output: First polygon minus all the intersecting bits, intersection polygons (plural is ok). I'm not really interested in the second polygon, just its intersection with the first.

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

EDIT2: I am currently using the GPC (General Polygon Clipper)library that makes this really easy!

EDIT2：我目前正在使用GPC（General Polygon Clipper）库，这使得这真的很容易！

采纳答案by jprete

What I think you should do

我认为你应该做什么

Do not attempt to do this yourself if you can possibly help it. Instead, use one of the many available polygon intersection algorithms that already exist.

如果您可以提供帮助，请不要尝试自己执行此操作。相反，使用已经存在的许多可用多边形相交算法之一。

I was strongly considering the following codebase on the strength of their demonstration code and the fact that they mentioned their handling of most/all of the weird cases. You would need to donate an amount (of you/your company's choice) if you use it commercially, but it's worth it to get a robust version of this kind of code.

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

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

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

What I actually did was to use a polygon-intersection algorithm that is part of the Java2D libraries. You can possibly find something similar in MS's own C# libraries to use.

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

There are other options out there as well; look for "polygon clipper" or "polygon clipping", since the same basic algorithms that handle polygon intersection also tend to be usable for the general clipping cases.

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

Once you actually have a polygon clipping library, you just need to subtract polygon B from polygon A to get your first piece of output, and intersect polygons A and B to get your second piece of output.

一旦你真正有了一个多边形裁剪库，你只需要从多边形 A 中减去多边形 B 来得到你的第一个输出，并与多边形 A 和 B 相交得到你的第二个输出。

How to roll your own, for the hopelessly masochistic

如何滚动你自己的，对于绝望的自虐狂

When I was considering rolling my own, I found the Weiler-Atherton algorithm to have the most potential for general polygon-cutting. I used the following as a reference:

当我考虑自己滚动时，我发现 Weiler-Atherton 算法最有可能用于一般多边形切割。我使用以下作为参考：

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

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

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

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

The details, as they say, are too dense to include here, but I have no doubt that you'll be able to find references on Weiler-Atherton for years to come. Essentially, you split all the points into those that are entering the final polygon or exiting the final polygon, then you form a graph out of all the points, and then walk the graph in the appropriate directions in order to extract all the polygon pieces you want. By changing the way you define and treat the "entering" and "exiting" polygons, you can achieve several possible polygon intersections (AND, OR, XOR, etc.).

正如他们所说，细节过于密集，无法包含在此处，但我毫不怀疑，您将能够在未来几年内找到有关 Weiler-Atherton 的参考资料。从本质上讲，您将所有点拆分为进入最终多边形或退出最终多边形的点，然后将所有点形成一个图形，然后沿适当的方向走该图形以提取所有多边形部分想。通过改变定义和处理“进入”和“退出”多边形的方式，您可以实现多种可能的多边形相交（AND、OR、XOR 等）。

It's actually fairly implementable, but like with any computational geometry code, the devil is in the degeneracies.

它实际上是相当可实现的，但与任何计算几何代码一样，问题在于退化。

回答by David Seiler

Arash Partow's FastGEOlibrary contains implementations of many interesting algorithms in computational geometry. Polygon intersection is one of them. It's written in Pascal, but it's only implementing math so it's pretty readable. Note that you will certainly need to preprocess your edges a little, to get them into clockwise or counterclockwise order.

Arash Partow 的FastGEO库包含计算几何中许多有趣算法的实现。多边形交集就是其中之一。它是用 Pascal 编写的，但它只是实现了数学运算，因此可读性很强。请注意，您当然需要对边缘进行一些预处理，以使它们按顺时针或逆时针顺序排列。

ETA: But really, the best way to do this is to not do this. Find another way to approach your problem that doesn't involve arbitrary polygon intersections.

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

回答by oharab

You may also want to have a look at the NetTopologySuiteor even try importing it into Sql server 2008 & it's spatial tools.

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

回答by fortran

If you dare to take a look to other people's GPL C++ code, you can see how do they do it in Inkscape:

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

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

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

回答by narozed

A polygon is fully described by an ordered list of points (P1, P2, ..., Pn). The edges are (P1 - P2), (P2 - P3), ..., (Pn - P1). If you have two polygons A and B which overlaps, there will be a point An (from the list on points describing polygon A) which lies within the area surrounded by polygon B or vice versa (a point of B lies in A). If no such point is found, then the polygons does not overlap. If such a point is found (i.e. Ai) check the adjacent points of the polygon A(i-1) and A(i+1). Repeat until you find a point outside the area or all points are checked (then the first polygon lies completly within the second polygon). If you found a point outside then you can calculate the crossing point. Find the corresponding edge of polygon B and follow it with resersed roles = now check if the points of polygon B lie within polygon A. This way you can build a list of points which describe the overlapping polygon. If needed you should check if the polygons are identical, (P1, P2, P3) === (P2, P3, P1).

多边形由点的有序列表 (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)。

This is just an idea and there maybe better ways. If you find a working and tested solution I would recommend that you use it...

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

narozed

心烦意乱

回答by George Silva

Try to use GIS tools for that, such as ArcObjects, TopologySuite, GEOS, OGR, etc. I'm not sure if all of these distributions are availuable to .net, but they all do the same.

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

回答by mloskot

If you are programming in .NET Framework, you may want to take a look at SqlGeometry class available in .NET assemblies shipped as Microsoft SQL Server System CLR Types

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

The SqlGeometry class provides STIntersectionmethod

SqlGeometry 类提供STIntersection方法

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

回答by Angus Johnson

Clipper is an open source freewarepolygon clipping library (written in Delphi and C++) that does exactly what you're asking - http://sourceforge.net/projects/polyclipping/

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

In my testing, Clipper is both significantly faster and far less prone to error than GPC (see more detailed comparisons here - http://www.angusj.com/delphi/clipper.php#features). Also, while there's source code for both Delphi and C++, the Clipper library also includes a compiled DLL to make it very easy to use the clipping functions in other (Windows) languages too.

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

回答by Charles Bretana

This academic paperexplains how to do this.

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