如何处理 Polyfill 算法中的水平？

Question

我有一个形状，它看起来像这样：
好吧，根据polyfill algorithm在我需要通过扫描线的区域填充颜色
我提供了6条扫描线。

扫描 1：从 y=-1 开始，像这样：
你知道如果前面的vertex/point和后面的vertex/point在同一边，它不会被认为是交集。

#list of lines that each line contain [(startpoint, endpoint)]
listLines = [[(4,-1),(4,-2)]]

扫描2：从y=-2开始，像这样：
同样的事情发生在这里，因为 Point13 和 Point15 在同一侧 Point14 不被视为交集，以及 Point9（因为 Point10 和 Point8 在同一侧）。

#list of lines that each line contain [(startpoint, endpoint)]
listLines = [[(1.7,-2),(6.5,-2)]]

扫描3：从y=-3开始，像这样：
但这是混乱的部分，现在我没有得到水平线。

#list of lines that each line contain [(startpoint, endpoint)]
listLines = [[(2.4,-3),(7,-3)],[(9,-3),(10.5,-3)]]

扫描4：从y=-4开始，像这样：
而且在这里我只得到水平线！！

#list of lines that each line contain [(startpoint, endpoint)]
listLines = [[(2,-4),(3,-4)],[(5,-4),(8,-4)]]

扫描5：从y=-5开始，像这样：

这里一切正常。

#list of lines that each line contain [(startpoint, endpoint)]
listLines = [[(3.5,-5),(5,-5)],[(6,-5),(9.5,-5)]]

扫描6：从y=-6开始，像这样：
在这里也工作得很好，我没有交集。

#list of lines that each line contain [(startpoint, endpoint)]
listLines = []

当我查看 polyfill 算法 tutorials/articles 或示例时，没有提到如何处理水平线。有人知道应该如何处理水平线吗？

注：所以据我了解：
如果下一行和上一行在同一侧，则不要像这样计算任何交叉点：

但是如果下一行和上一行像这样在对面：

我必须查看到目前为止我收集的顶点总数。

1- 如果偶数，我必须添加第一个交集。
2- 如果是奇数，我必须添加最后一个交叉点。

但是如果在扫描线上铺线就不行了！！.看看这个例子：

所以为了解决这个问题，我想出了一个解决方案，我需要运行优化并重建形状，只需找到每个线方程，对于那些具有相同方程的方程，删除共享顶点，这将使形状简单，因此任何线上都不会有任何额外的顶点。

奇怪的是，到目前为止，他们只讨论了扫描线算法，却没有提到任何关于重叠线方程的内容。不是吗？

Answer 1

让我们做一些低效但正确的事情。

对于每条扫描线，我们将从 Point0 开始穿过整个多边形并返回到 point0。

在扫描线 3

Edge (0,1) , point (2.4, -3) -> down-down   (keep the intersection)
Edge (1,2)
Edge (2,3)
Edge (3,4)
Edge (4.5)
Edge (5.6)
Edge (6,7)
Edge (7,8)
Edge (8,9) , point (10.5, -3) -> up-up (keep the intersection)
Edge (9,10), point (9, -3) -> down-left (uh-oh)
Edge (10, 11), points (9, -3) to (7, -3) -> down->left->up (no need to keep any intersection)
Edge (11, 12), point (7, -3) -> left-up (uh-oh)
Edge (12,13)
Edge (13,14)
Edge (14,15)

虽然您有算法可以在 O(n) 时间内对点进行排序，但现在不要担心效率，只需应用我们最喜欢的快速排序并沿 x 轴对点进行排序。

所以我们只有两分正确。

在扫描线 4

Edge (0,1), point (3, -4) -> down-left (uh-oh)
Edge (1,2), points (3,-4) to (2,-4) -> down-left-down (keep point (2,-4))
Edge (2,3), point (2,-4) -> left-down -> (uh-oh)
Edge (3,4), point (5,-4) -> up-right (uh-oh)
Edge (4,5), points (5,-4) to (8,-4) -> up-right-down (ignore)
Edge (5,6), point (8,-4) -> right-down (uh-oh)
Edge (7,8), point (11, -4) -> up-up -> however at top point, (keep point (11,-4).
Edge (8,9), point (11, -4) -> up-up -> however at bottom point, already kept it (ignore)
Edge (9,10)
Edge (10,11)
Edge (11,12)
Edge (12,13)
Edge (13,14)
Edge (14,15)

在最坏的情况下，多边形可能有很多绕组。任何算法都应该正确地工作。例如见下：

有几种方法可以做到这一点。本地信息足够的一个如下：根据转弯和内部位于哪一侧，我们可以决定取哪个点。

如何处理 Polyfill 算法中的水平？

how to handle Horizantal in Polyfill Algorithm?

python

computer-science

python-2.7