如何使两个多边形相交？
这看起来并不简单（在各种论坛上都有很多人问这个问题），但我绝对需要它作为更复杂算法的构建块。
输入：2 个二维多边形（A 和 B），分别以边 [(x0, y0, x1, y2), ...] 的列表形式给出。这些点由成对的 double 表示。我不知道它们是顺时针、逆时针还是任何方向。我确实知道它们不一定是凸的。
输出：3个多边形，分别代表A、B和相交的多边形AB。其中任何一个都可以是空（？）多边形，例如null。
优化提示：这些多边形代表房间和地板边界。因此，房间边界通常会与楼层边界完全相交，除非它属于同一平面上的另一个楼层（啊！）。
我有点希望有人已经在 c# 中完成了这个工作，并且让我使用他们的策略/代码，因为到目前为止我在这个问题上发现的内容相当令人畏惧。
编辑：所以看来我并不完全因为想到这样做而感到晕倒。我想在这里重申所需的输出，因为这是一个特殊情况，可能会使计算更简单：
输出：第一个多边形减去所有相交位，相交多边形（复数即可）。我对第二个多边形并不真正感兴趣，只是它与第一个多边形的交集。
EDIT2：我目前正在使用GPC（通用多边形裁剪器） ) 库让这变得非常简单！
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 do know that they are not necessarily convex.
Output: 3 polygons representing A, B and the intersecting polygon AB. Either of which may be an empty (?) polygon, e.g. 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.
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!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
尝试使用 GIS 工具来实现此目的，例如 ArcObjects、TopologySuite、GEOS、OGR 等。我不确定所有这些发行版是否都可用于 .net，但它们的作用都是相同的。
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.
这篇学术论文解释了如何做到这一点。
This academic paper explains how to do this.
如果你敢看别人的 GPL C++ 代码，你可以看看他们在 Inkscape 中是如何做到的：
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp （第 126 行）
If you dare to take a look to other people's GPL C++ code, you can see how do they do it in Inkscape:
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (line 126)
Arash Partow 的 FastGEO 库包含计算几何中许多有趣算法的实现。多边形相交就是其中之一。它是用 Pascal 编写的，但它只实现了数学，所以它非常可读。请注意，您肯定需要对边缘进行一些预处理，以使它们按顺时针或逆时针顺序排列。
ETA：但实际上，最好的方法就是不这样做。寻找另一种不涉及任意多边形相交的方法来解决您的问题。
Arash Partow's FastGEO library 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.
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.
如果您在 .NET Framework 中进行编程，您可能需要查看 .NET 程序集中提供的 SqlGeometry 类，作为 Microsoft SQL Server 系统 CLR 类型
SqlGeometry 类提供 STIntersection 方法
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
The SqlGeometry class provides STIntersection method
我认为你应该做什么
如果可以的话，不要尝试自己这样做。相反，请使用现有的多种可用多边形相交算法之一。
基于他们的演示代码的强度以及他们提到他们对大多数/所有奇怪情况的处理这一事实，我正在强烈考虑以下代码库。如果您将其用于商业用途，您需要捐赠一定金额（您/您公司的选择），但获得此类代码的强大版本是值得的。
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 等）。
它实际上是相当可实现的，但就像任何计算几何代码一样，魔鬼在于简并性。
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/
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.
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.
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:
http://cs1.bradley.edu/public/jcm/weileratherton.html
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.).
It's actually fairly implementable, but like with any computational geometry code, the devil is in the degeneracies.
您可能还想查看 NetTopologySuite，甚至尝试将其导入 Sql 服务器2008年&它是空间工具。
You may also want to have a look at the NetTopologySuite or even try importing it into Sql server 2008 & it's spatial tools.
Clipper 是一个开源免费软件多边形裁剪库（用 Delphi 和 C++ 编写），它完全符合您的要求 - http://sourceforge.net/projects/polyclipping/
在我的测试中，Clipper 比 GPC 明显更快，而且更不容易出错（请参阅此处更详细的比较 - http://www.angusj.com/delphi/clipper.php#features）。此外，虽然有 Delphi 和 C++ 的源代码，但 Clipper 库还包含一个已编译的 DLL，以便在其他 (Windows) 语言中也可以轻松使用剪辑功能。
Clipper is an open source freeware polygon clipping library (written in Delphi and C++) that does exactly what you're asking - 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.
多边形由点的有序列表（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)。
这只是一个想法，也许还有更好的方法。如果您找到一个可行且经过测试的解决方案，我建议您使用它......
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).
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