如何在Polyfill算法中處理Horizantal？

Question

我有一個形狀，它看起來像這樣：
好的，根據polyfill algorithm來填補我需要通過掃描線的區域的顏色。
我提供了6條掃描線。

掃描1：從y=-1開始像這樣：
你知道，如果以前的頂點/點和一個頂點/點都在同一側，也不會考慮爲交集。

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

掃描2：從y=-2開始像這樣：在這裏
同樣的事情發生，因爲Point13和Point15都在同一側Point14沒有考慮作爲交集，以及作爲點9（原因點10和點8在同一側）。

#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算法教程/文章或示例時，沒有提及如何處理水平線。任何人有任何想法應該如何處理水平線？

注：所以從我的理解：
如果下一個和上線在同一側，別指望像這樣任何交集：

但如果下一個和上線在對面狀所以：

我必須看看我收集到的頂點總數。

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) 

在最壞的情況下，多邊形可以有很多繞組。任何算法都應該正確工作。例如見下：

有幾種方法可以做到這一點。本地信息就足夠了：根據轉彎和內部所在的位置，我們可以決定採取哪一點。