如何相交两个多边形？ [英] How to intersect two polygons?

问题描述

这似乎是不平凡的（它被要求在各种论坛上不少），但我绝对需要以此为基石更复杂的算法。

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.

<青霉>输入的：给定为边缘的列表2多边形（A和B）在2D中， [（X0，Y0，X1，Y2），...] 每个。这些点重新由对的psented $ P $双秒。我不知道他们被给予顺时针，逆时针或在任何方向都没有。我的不的知道，他们不一定是凸的。

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.

的输出的：3个多边形重新presenting A，B和相交的多边形AB。其中的任一个可以是空的（？）多边形，例如空。

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

的提示进行优化的：这些多边形重新present房间和地板的边界。所以房间边界通常完全与地面的边界相交时，除非它属于在同一平​​面上（哎呀！）。

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!).

我有点希望有人在C＃中已经做到了这一点，并让我使用他们的策略/ code，正如我至今对这个问题是相当艰巨的发现。

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 ：我目前使用的是 GPC（一般多边形快船）库，使这真的很容易！

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

推荐答案

我认为你应该做

不要尝试这样做自己，如果你都不可能帮助它。相反，使用了已存在许多可用的多边形相交算法之一。

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.

我强烈考虑在他们的示范code的力量，他们提到的最多处理/所有的怪异的案件事实如下codeBase的。您需要捐赠，如果你使用它的商业化量（您/贵司的选择），但它是值得的，得到这样的code的一个强大的版本。

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 /

我实际上做是使用多边形相交算法，是的Java2D库的一部分。你可以找到可能在MS自己的C＃库使用类似的东西。

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.

一旦你实际上有一个多边形裁剪库，你只需要从多边形A减去多边形B，让您第一件输出，和相交多边形A和B，让您的第二件的输出。

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.

如何推出自己的，在绝望自虐

当我在考虑我自己的滚动，我发现维勒 - 阿瑟顿算法对一般的多边形切割最有潜力的。我用下面作为参考：

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

的细节，如他们所说，过于密集，包括在这里，但我毫不怀疑，你就可以找到维勒 - 阿瑟顿引用几年来。从本质上讲，拆分的所有点到那些进入最后多边形或退出的最后多边形，则可以形成一个图形的所有点，然后走在适当的方向，以提取所有多边形件的图表你想。通过改变你的方式定义和看待进入和退出多边形，可以实现多种可能的多边形交集（AND，OR，XOR等）。

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.).

这实际上是相当实施的，但像任何计算几何code，魔鬼在简并。

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

这篇关于如何相交两个多边形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！