如何判断nonzero-fill多边形的一条边是否为外边？
How to determine whether an edge of a nonzero-fill polygon is an outside edge?
假设我有一个多边形并且我已经计算了它的所有 self-intersections。如何根据非零填充规则确定特定边缘是内部还是外部？ "outside edge" 是指位于填充区域和 non-filled 区域之间的边缘。
示例：
左边是根据非零填充规则填充的示例多边形。右侧是相同的多边形，其外边缘以红色突出显示。我正在寻找一种算法，给定多边形的边及其彼此的交点，可以将每条边标记为外部或内部。
最好，解决方案应该推广到由例如组成的路径。贝塞尔曲线。
[编辑]另外两个要考虑的例子：
我注意到包围在形状中的 "outside edge" 在到达外面之前必须穿过偶数个交叉点。围起来的"non-outside edges"必须经过奇数个路口。
你可以试试这样的算法
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
}
例如：
*我认为你总是可以通过依次尝试每条线来找到外边缘：尝试无限延伸它 - 如果它没有穿过另一条线那么它应该在外面。这在直觉上似乎是正确的，但我想知道是否存在一些无法使用此规则找到起始线的病态情况。使用这种查找第一条线的方法不适用于曲线。
我想，你的问题可以分两步解决。
使用支持自相交多边形的算法对源多边形进行三角剖分。良好的开端是 Seidel algorithm。链接的 PDF 文档的第 5.2 节描述了自相交多边形。
A 使用支持空洞的算法将三角形合并为单个多边形，即 Weiler-Atherton algorithm。该算法可用于裁剪和合并，因此您需要它是 "merging" 的情况。也许你可以简化算法，因为第一步形成的三角形不相交。
我意识到这可以通过一种相当简单的方法来确定，只需对计算绕组数的标准例程稍作修改即可。它在概念上类似于评估紧邻目标边缘左侧和紧邻右侧的绕组。这是任意曲线的算法，而不仅仅是线段：
- 在目标线段上选择一个点。确保该点的 Y 导数不为零。
- 在其导数的 Y 根处细分目标片段。在下一个点中，忽略包含您在步骤 1 中选取的点的线段部分。
- 确定在 1 中选取的点处的缠绕数。这可以通过在 +X 方向投射光线并查看与它相交的对象以及在哪个方向相交来完成。导数的 Y 分量为正的点处的交点计为 +1。执行此操作时，忽略包含您在步骤 1 中选取的点的 Y 单调部分。
- 如果绕数为 0，我们就完成了——这绝对是一个外边。如果它非零且不同于 -1、0 或 1，我们就完成了 - 这绝对是一个内边。
- 检查步骤1中选取的点处的导数，如果射线与该点的交点为-1，而步骤3中得到的绕数为+1，则为外边； +1/-1 情况类似。否则这是一个内边。
本质上，我们正在检查射线与目标线段的交点是否改变了零和非零之间的绕组数。
我建议我认为是对我有用的解决方案的更简单实施：
1.选择目标段上的任意点。（我任意选择中点。）
2。从垂直于线段的那个点构造一条射线。（我对 CW 多边形使用左法线，对 CCW 多边形使用右法线。）
3。计算射线与多边形的交点，忽略目标线段本身。 在这里您可以选择非零缠绕规则[递减多边形线段向左交叉 (CCW) 并递增向右交叉 (连续波）；其中内边产生零计数]或 EvenOdd 规则[计算内边产生奇数的所有交叉点]。对于线段，交叉方向是通过对其起点和终点进行简单的向左或向右测试来确定的。对于圆弧和曲线，可以在交点处使用切线来完成，这是 reader.
的练习
我进行此分析的目的是将自相交多边形划分为一组等效的非自相交多边形。为此，同样可以分析相反方向的光线并感知原始多边形是否会在那里填充，这很有用。这导致对段的两侧进行 inside/outside 确定，从而产生四种可能的状态。我怀疑 OUTSIDE-OUTSIDE 状态可能仅对非闭合多边形有效，但对于此分析，可能需要暂时关闭它。通过跟踪它们的共享交点，可以将具有相同状态的线段收集到非相交的多边形中。在某些情况下，例如使用纯填充，您甚至可能决定消除 INSIDE-INSIDE 多边形作为冗余，因为它们填充了已经填充的 space.
感谢您的原始解决方案！！
假设我有一个多边形并且我已经计算了它的所有 self-intersections。如何根据非零填充规则确定特定边缘是内部还是外部？ "outside edge" 是指位于填充区域和 non-filled 区域之间的边缘。
示例：
左边是根据非零填充规则填充的示例多边形。右侧是相同的多边形，其外边缘以红色突出显示。我正在寻找一种算法，给定多边形的边及其彼此的交点，可以将每条边标记为外部或内部。
最好，解决方案应该推广到由例如组成的路径。贝塞尔曲线。
[编辑]另外两个要考虑的例子：
我注意到包围在形状中的 "outside edge" 在到达外面之前必须穿过偶数个交叉点。围起来的"non-outside edges"必须经过奇数个路口。
你可以试试这样的算法
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
}
例如：
*我认为你总是可以通过依次尝试每条线来找到外边缘：尝试无限延伸它 - 如果它没有穿过另一条线那么它应该在外面。这在直觉上似乎是正确的，但我想知道是否存在一些无法使用此规则找到起始线的病态情况。使用这种查找第一条线的方法不适用于曲线。
我想，你的问题可以分两步解决。
使用支持自相交多边形的算法对源多边形进行三角剖分。良好的开端是 Seidel algorithm。链接的 PDF 文档的第 5.2 节描述了自相交多边形。
A 使用支持空洞的算法将三角形合并为单个多边形，即 Weiler-Atherton algorithm。该算法可用于裁剪和合并，因此您需要它是 "merging" 的情况。也许你可以简化算法，因为第一步形成的三角形不相交。
我意识到这可以通过一种相当简单的方法来确定，只需对计算绕组数的标准例程稍作修改即可。它在概念上类似于评估紧邻目标边缘左侧和紧邻右侧的绕组。这是任意曲线的算法，而不仅仅是线段：
- 在目标线段上选择一个点。确保该点的 Y 导数不为零。
- 在其导数的 Y 根处细分目标片段。在下一个点中，忽略包含您在步骤 1 中选取的点的线段部分。
- 确定在 1 中选取的点处的缠绕数。这可以通过在 +X 方向投射光线并查看与它相交的对象以及在哪个方向相交来完成。导数的 Y 分量为正的点处的交点计为 +1。执行此操作时，忽略包含您在步骤 1 中选取的点的 Y 单调部分。
- 如果绕数为 0，我们就完成了——这绝对是一个外边。如果它非零且不同于 -1、0 或 1，我们就完成了 - 这绝对是一个内边。
- 检查步骤1中选取的点处的导数，如果射线与该点的交点为-1，而步骤3中得到的绕数为+1，则为外边； +1/-1 情况类似。否则这是一个内边。
本质上，我们正在检查射线与目标线段的交点是否改变了零和非零之间的绕组数。
我建议我认为是对我有用的解决方案的更简单实施：
1.选择目标段上的任意点。（我任意选择中点。）
2。从垂直于线段的那个点构造一条射线。（我对 CW 多边形使用左法线，对 CCW 多边形使用右法线。）
3。计算射线与多边形的交点，忽略目标线段本身。 在这里您可以选择非零缠绕规则[递减多边形线段向左交叉 (CCW) 并递增向右交叉 (连续波）；其中内边产生零计数]或 EvenOdd 规则[计算内边产生奇数的所有交叉点]。对于线段，交叉方向是通过对其起点和终点进行简单的向左或向右测试来确定的。对于圆弧和曲线，可以在交点处使用切线来完成，这是 reader.
的练习我进行此分析的目的是将自相交多边形划分为一组等效的非自相交多边形。为此，同样可以分析相反方向的光线并感知原始多边形是否会在那里填充，这很有用。这导致对段的两侧进行 inside/outside 确定，从而产生四种可能的状态。我怀疑 OUTSIDE-OUTSIDE 状态可能仅对非闭合多边形有效，但对于此分析，可能需要暂时关闭它。通过跟踪它们的共享交点，可以将具有相同状态的线段收集到非相交的多边形中。在某些情况下，例如使用纯填充，您甚至可能决定消除 INSIDE-INSIDE 多边形作为冗余，因为它们填充了已经填充的 space.
感谢您的原始解决方案！！