确定一个多边形是否包含另一个多边形
Determine whether one polygon contains another
（出于我的目的 "polygons" 不包括自相交多边形或带孔的多边形 - 只是简单的（凹或凸）多边形。）
我找到了针对这个问题的各种建议，主要基于以下几点：
If there are no intersections between the edges of Polygon1 and the edges of Polygon2, and at least one vertex of Polygon2 is "inside" Polygon1, then Polygon1 contains Polygon2.
（例如查看接受的答案 here）
然而，细节决定成败：
"inside" Polygon1 是否包含 "on an edge of" Polygon1？明明是
必须，否则在图 F 中（见下面链接的图像）Polygon2（红色）将没有
vertex "inside" Polygon1 (blue) 等未能通过上述测试，当
它应该通过。
两条边的"intersection"是否包含一条边的末端点
边缘（即顶点）？如果"yes"，则下图A和E
有交叉点，因此在它们应该通过时却未能通过测试。但
如果"no"，那么图B、C、D没有交点，所以通过
他们应该失败的测试。
（NB 图 A、B 和 C 在 Polygon1 的边上有 Polygon2 的顶点，图 D 和 E 反之亦然。）
我无法找出一个条件来测试如何正确区分这些不同的情况。我会很感激任何指示？
如果我们要检查多边形 B 是否在多边形 A 内部：
就像您链接到的答案中提到的那样，开始为每对边做一个 line intersection test，每个多边形一个。如果任何边相交（不包括位于边上的顶点和公共顶点），则 B 不在 A 内。
如果一个多边形的顶点 V 位于另一个多边形的边上，则将该边视为 2 条边，并将顶点 V 作为该多边形的新顶点。
现在我们只需要考虑公共顶点。
对于每个公共顶点 V:
- 我们可以说 V 有边 EA1 和 EA2（来自 A）和 EB1 和 EB2（来自 B）。
- 获取所有 4 条边的梯度。
使用它来确定哪些边是相邻的。
如果EB1和EB2不相邻，则B不在A之内
如果EB2在A上（即EB2在EA2上，即梯度相等），我们还不知道B是否在A中
在这种情况下，我们需要跟踪 EB1 在哪一侧，然后移动到相邻顶点 VB（EB2 的另一个顶点），并检查 EB3 是否位于之后的边EB2，与 EB1 在同一侧。如果它们在不同的边上，则 B 不在 A 内。
如果 EB3 也在 A 上，我们需要检查 EB4，依此类推，直到找到一个不在 A 上的。
如果 EB1 在 EA1 上并且 EB2 在 EA2 上，我们需要向两个方向移动以确定我们需要在哪一边。如果B的所有边都在A上，则A等于B。
（注意：例如，如果 EB2 位于 EA1 而不是 EA2，您只需重命名它们即可满足上述条件）
所有这些都假设我们不允许多边形与 自身相交 - 允许这可能会破坏这一点。
这里可能有一些重要的细节，但这应该是一个不错的起点。
我们可以遍历 O(|EA| + |EB|) 中的边并播放 "catch:" 当一个多边形的当前边至少在一个维度上超出另一个边时，沿着下一个 edge/s 的另一个多边形，然后再次切换。断言包含，我们可以通过监视交叉点以及边缘的哪一侧在其多边形内来判断。
The sweepline algorithm (as nearly always) gives us the most robust and efficient solution.
In its simplest form, sweepline finds all line segment intersections. It is trivial to extend it to check polygon containment. You just keep track which line or point belong to each polygon. At any step of the algorithm, the intersection of the sweeping line and the interior of each polygon is a finite set of vertical segments. You have these cases:
- If there is a proper (i.e. not at an endpoint) edge intersection at any step, game over.
- Otherwise if at every step red and blue segments are disjoint, then the polygons are completely outside each other.
- Otherwise if at every step red segments are identical to blue segments (i.e. the red set and the blue set are the same), then the two polygons are the same.
- Otherwise if at every step each red segment is completely inside some blue segment, then the red polygon is inside the blue one.
- Otherwise if at every step each blue segment is completely inside some red segment, then the blue polygon is inside the red one.
- Otherwise polygon boundaries intersect.
This takes care of all edge cases. If you want to classify your cases A, E and F as "inside", test only intersection of segment interiors (i.e. segments (0,1) and (1,2) are not intersecting, and (0,1) is inside of (0,2)). Otherwise, just treat the above cases as proper intersections.
If at some step there are two edges that are collinear and parallel to the sweep line and they intersect, it could be a bit hard to decide. However all edge cases can be resolved by calculating sweepline-polygon intersection not at vertices (as is normal to the sweepline algorithm) but between vertices (say at a midpoint between the current vertex and the next). This way only polygon interiors (not boundaries) are ever considered.
In effect the algorithm breaks up our polygons into a bunch of little trapezoids, sandwiched between parallel (say vertical) lines drawn through each vertex. It's very easy to check whether these trapezoids are intersecting, or disjoint, or completely contain one another. An illustration can be found here.
Edit: clarified some wording.
Edit 2: found an edge case ;)
非常感谢您的回复，尤其是@Dukeling 和@n.m。
我已经实现了（在Python）@n.m提出的扫描线解决方案。并将其张贴在这里以防其他人发现它有用。 （我发现一个比 Dukeling 的解决方案更容易编码。）在我的用例中，我知道哪个将是包含多边形（如果有的话），所以我不需要双向测试。
我已经用二十多个测试用例对其进行了测试，包括上图中的所有测试用例，以及它们在 y=x 中的反映。
但是，如果有人发现实施不起作用的任何边缘情况，或代码效率的任何改进，欢迎发表评论。
编辑：
我已经删除了代码，因为我发现它在很多情况下都不起作用。最后我找到了一个更全面的解决方案，给定两个多边形A和B来确定A是否包含B，A在B内部，A和B重叠，还是A和B不相交。
为了加快速度，它首先查看边界框，这消除了一些可能性，然后如果边界框相等，它会查看区域，然后才继续扫掠线算法。
代码比较长，这里就不放了，有兴趣的可以看https://github.com/andy31lewis/brySVG处PolygonObject的positionRelativeTo方法。这已经用几百个测试用例进行了测试，看起来非常可靠。
（出于我的目的 "polygons" 不包括自相交多边形或带孔的多边形 - 只是简单的（凹或凸）多边形。）
我找到了针对这个问题的各种建议，主要基于以下几点：
If there are no intersections between the edges of Polygon1 and the edges of Polygon2, and at least one vertex of Polygon2 is "inside" Polygon1, then Polygon1 contains Polygon2.
（例如查看接受的答案 here）
然而，细节决定成败：
"inside" Polygon1 是否包含 "on an edge of" Polygon1？明明是 必须，否则在图 F 中（见下面链接的图像）Polygon2（红色）将没有 vertex "inside" Polygon1 (blue) 等未能通过上述测试，当 它应该通过。
两条边的"intersection"是否包含一条边的末端点 边缘（即顶点）？如果"yes"，则下图A和E 有交叉点，因此在它们应该通过时却未能通过测试。但 如果"no"，那么图B、C、D没有交点，所以通过 他们应该失败的测试。
我无法找出一个条件来测试如何正确区分这些不同的情况。我会很感激任何指示？
如果我们要检查多边形 B 是否在多边形 A 内部：
就像您链接到的答案中提到的那样，开始为每对边做一个 line intersection test，每个多边形一个。如果任何边相交（不包括位于边上的顶点和公共顶点），则 B 不在 A 内。
如果一个多边形的顶点 V 位于另一个多边形的边上，则将该边视为 2 条边，并将顶点 V 作为该多边形的新顶点。
现在我们只需要考虑公共顶点。
对于每个公共顶点 V:
- 我们可以说 V 有边 EA1 和 EA2（来自 A）和 EB1 和 EB2（来自 B）。
- 获取所有 4 条边的梯度。
使用它来确定哪些边是相邻的。
如果EB1和EB2不相邻，则B不在A之内
如果EB2在A上（即EB2在EA2上，即梯度相等），我们还不知道B是否在A中
在这种情况下，我们需要跟踪 EB1 在哪一侧，然后移动到相邻顶点 VB（EB2 的另一个顶点），并检查 EB3 是否位于之后的边EB2，与 EB1 在同一侧。如果它们在不同的边上，则 B 不在 A 内。
如果 EB3 也在 A 上，我们需要检查 EB4，依此类推，直到找到一个不在 A 上的。
如果 EB1 在 EA1 上并且 EB2 在 EA2 上，我们需要向两个方向移动以确定我们需要在哪一边。如果B的所有边都在A上，则A等于B。
（注意：例如，如果 EB2 位于 EA1 而不是 EA2，您只需重命名它们即可满足上述条件）
所有这些都假设我们不允许多边形与 自身相交 - 允许这可能会破坏这一点。
这里可能有一些重要的细节，但这应该是一个不错的起点。
我们可以遍历 O(|EA| + |EB|) 中的边并播放 "catch:" 当一个多边形的当前边至少在一个维度上超出另一个边时，沿着下一个 edge/s 的另一个多边形，然后再次切换。断言包含，我们可以通过监视交叉点以及边缘的哪一侧在其多边形内来判断。
The sweepline algorithm (as nearly always) gives us the most robust and efficient solution.
In its simplest form, sweepline finds all line segment intersections. It is trivial to extend it to check polygon containment. You just keep track which line or point belong to each polygon. At any step of the algorithm, the intersection of the sweeping line and the interior of each polygon is a finite set of vertical segments. You have these cases:
- If there is a proper (i.e. not at an endpoint) edge intersection at any step, game over.
- Otherwise if at every step red and blue segments are disjoint, then the polygons are completely outside each other.
- Otherwise if at every step red segments are identical to blue segments (i.e. the red set and the blue set are the same), then the two polygons are the same.
- Otherwise if at every step each red segment is completely inside some blue segment, then the red polygon is inside the blue one.
- Otherwise if at every step each blue segment is completely inside some red segment, then the blue polygon is inside the red one.
- Otherwise polygon boundaries intersect.
This takes care of all edge cases. If you want to classify your cases A, E and F as "inside", test only intersection of segment interiors (i.e. segments (0,1) and (1,2) are not intersecting, and (0,1) is inside of (0,2)). Otherwise, just treat the above cases as proper intersections.
If at some step there are two edges that are collinear and parallel to the sweep line and they intersect, it could be a bit hard to decide. However all edge cases can be resolved by calculating sweepline-polygon intersection not at vertices (as is normal to the sweepline algorithm) but between vertices (say at a midpoint between the current vertex and the next). This way only polygon interiors (not boundaries) are ever considered.
In effect the algorithm breaks up our polygons into a bunch of little trapezoids, sandwiched between parallel (say vertical) lines drawn through each vertex. It's very easy to check whether these trapezoids are intersecting, or disjoint, or completely contain one another. An illustration can be found here.
Edit: clarified some wording. Edit 2: found an edge case ;)
非常感谢您的回复，尤其是@Dukeling 和@n.m。
我已经实现了（在Python）@n.m提出的扫描线解决方案。并将其张贴在这里以防其他人发现它有用。 （我发现一个比 Dukeling 的解决方案更容易编码。）在我的用例中，我知道哪个将是包含多边形（如果有的话），所以我不需要双向测试。
我已经用二十多个测试用例对其进行了测试，包括上图中的所有测试用例，以及它们在 y=x 中的反映。 但是，如果有人发现实施不起作用的任何边缘情况，或代码效率的任何改进，欢迎发表评论。
编辑：
我已经删除了代码，因为我发现它在很多情况下都不起作用。最后我找到了一个更全面的解决方案，给定两个多边形A和B来确定A是否包含B，A在B内部，A和B重叠，还是A和B不相交。
为了加快速度，它首先查看边界框，这消除了一些可能性，然后如果边界框相等，它会查看区域，然后才继续扫掠线算法。
代码比较长，这里就不放了，有兴趣的可以看https://github.com/andy31lewis/brySVG处PolygonObject的positionRelativeTo方法。这已经用几百个测试用例进行了测试，看起来非常可靠。