如何确定一个非零填充多边形的边是否为外边缘？

Question

假设我有一个多边形，并计算出了所有的自相交。按照非零环绕数规则，如何确定特定边缘是内部还是外部？所谓的“外部边缘”是指位于填充区域和未填充区域之间的边缘。

例如：

左侧是一个示例多边形，根据非零环绕数规则填充。右侧是同一多边形，其外部边缘用红色突出显示。我正在寻找一种算法，能够根据多边形的边缘及其相互交叉情况，将每个边缘标记为内部或外部。

最好的解决方案应该适用于由贝塞尔曲线等组成的路径。

[编辑] 还有两个要考虑的示例：

- Krzysztof Kosiński

---

如果某个形状有两个不相交的部分（例如http://i.stack.imgur.com/9Va6m.png），应该发生什么？只应该识别与形状相邻的边缘吗？ - Jonny

在你的图片所示的情况下，所有的边缘都是在外面的，中间区域应该被填充。 - Krzysztof Kosiński

Answer 1

我注意到被形状包围的“外边缘”必须在到达外部之前穿过偶数个交点。被包围的“非外边缘”必须穿过奇数个交点。

您可以尝试这样的算法。

isOutside = true
edge = find first outside edge*
edge.IsOutside = isOutside
while (not got back to start) {
  edge = next
  if (gone over intersection)
    isOutside = !isOutside
  edge.IsOutside = isOutside
}

例如：

*我认为你可以通过逐行尝试来找到外边缘：尝试将其无限延伸-如果它没有与另一条线交叉，则应该在外部。这似乎直观上是正确的，但我想知道是否存在一些病态情况，无法使用此规则找到起始线。使用此方法查找第一条线不适用于曲线。

- Jonny

---

这个多边形内外状态在交叉点处的变化仅对该多边形有效。请参见我在问题中添加的示例。然而，如果考虑相交线的方向（即从跟随该多边形的“车”观察时，相交的轨迹向左还是向右），这可能接近正确的解决方案。 - Krzysztof Kosiński

例如，可以通过查找连接到极值顶点（最小/最大X/Y）的边缘来找到外边缘。对于曲线，我们必须查看紧密的边界框而不是顶点。 - Krzysztof Kosiński

Answer 2

我认为，您的问题可以通过以下两个步骤解决：

1. 使用支持自相交多边形的算法对源多边形进行三角剖分。Seidel algorithm是一个不错的开始。链接PDF文档的5.2节描述了自相交多边形。

2. 使用支持空洞的算法将三角形合并成单个多边形，即Weiler-Atherton algorithm算法。该算法可用于剪辑和合并，因此需要它的“合并”情况。也许您可以简化该算法，因为第一步中的三角形没有相交。

- Mark Shevchenko

---

也许您可以详细说明一下？我不明白这与问题有什么关系，即查找外部边缘。此外，任何涉及三角剖分的内容都无法推广到路径。 - Krzysztof Kosiński

第二个算法的结果是一个外部顶点列表（以及一些内部顶点列表）。据我所知，这就是你需要的东西。至于你的第二个问题，我认为你可以将Seidel算法应用于Bezier曲线。你需要能够检测曲线/曲线和曲线/直线的交点，然后通过交点将你的曲线/直线分成两段。但据我所知，一对曲线可能有两个或三个交点，因此你需要考虑到这一点。 - Mark Shevchenko

我认为我找到了解决方案，但我没有信心。我思考这个问题已经两天了，我认为所有这些内部交叉使它变得非常复杂。因此，我决定使用整个多边形而不是边来操作。如果原始多边形可以分成子多边形，则它们可以再次合并。我的“决定”只是实现这个想法。 - Mark Shevchenko

Answer 3

我意识到这可以通过稍微修改计算绕数的标准例程来相对简单地确定，它在概念上类似于在目标边缘的左侧和右侧立即评估绕数。以下是适用于任意曲线而不仅仅是线段的算法：

1. 在目标线段上选择一个点。确保该点的Y导数不为零。
2. 在其导数的Y根处将目标线段进行细分。在下一个点中，忽略包含步骤1中选择的点的线段部分。
3. 确定步骤1中选择的点的绕数。可以通过向+X方向投射光线并查看相交点及其方向来完成。导数Y分量为正的交点计为+1。在此过程中，忽略包含步骤1中选择的点的Y单调部分。
4. 如果绕数为0，则我们完成了——这绝对是一个外边缘。如果它不为-1、0或1且非零，则我们完成了——这绝对是一个内边缘。
5. 检查步骤1中选择的点的导数。如果光线与该点的交点被计为-1，并且步骤3中获得的绕数为+1，则这是一个外边缘；对于+1/-1情况也是如此。否则，这是一个内边缘。

实质上，我们正在检查光线与目标线段的交点是否在0和非零之间改变了绕数。

- Krzysztof Kosiński

Answer 4

我建议一个我认为更简单的实现方案，这对我很有效：

1. 在目标线段上选择任意一点。（我随意选择中点。）

2. 从该点构造一条垂直于线段的射线。（对于顺时针多边形，我使用左法线射线；对于逆时针多边形，我使用右法线射线。）

3. 计算射线与多边形的交点数量，忽略目标线段本身。在这里，您可以选择非零环绕规则[对于向左（逆时针）穿过的多边形线段减少，对于向右（顺时针）穿过的增加；其中内部边缘产生零计数]或奇偶规则[计算所有交叉点，其中内部边缘产生奇数计数]。对于线段，交叉方向是通过其起点和终点的简单左右测试确定的。对于弧和曲线，可以通过交点处的切线来完成，这是读者的练习。

我的目的是将一个自相交的多边形分成一组等效的非自相交多边形。为此，同样分析相反方向的射线并感知原始多边形是否会在那里填充是有用的。这导致了对于段的两侧的内部/外部确定，产生了四种可能的状态。我怀疑OUTSIDE-OUTSIDE状态只适用于非闭合多边形，但对于这个分析来说，暂时关闭它可能是可取的。具有相同状态的段可以通过跟踪它们的共享交点收集到非相交多边形中。在某些情况下，例如使用纯填充，您甚至可以决定消除INSIDE-INSIDE多边形，因为它们填充了已经填充的空间。

感谢您的原始解决方案！

- Scott Ferguson