how to handle Horizantal in Polyfill Algorithm?

Question

I have a shape, it's look alike this:
alright, according to polyfill algorithm to fill the color in the area i need to pass scan lines.
I've provided 6 scan lines.

Scan 1: start from y=-1 like so:
you know if the previous vertex/point and next vertex/point are on same side, it will not consider as intersection.

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

Scan 2: start from y=-2 like so:
same thing happen in here since Point13 and Point15 are in same sides Point14 is not consider as intersection, as well as Point9 (cause Point10 and Point8 are in same side).

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

Scan 3: start from y=-3 like so:
but here is the confusion part, now i don't get the Horizontal line.

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

Scan 4: start from y=-4 like so:
and also in here i only get the horizontal lines!!

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

Scan 5: start from y=-5 like so:

in here everything work perfectly.

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

Scan 6: start from y=-6 like so:
in here also work perfectly and i get no intersection.

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

when i look at polyfill algorithm tutorials/articles or examples, nothing mentioned about how to handle Horizontal lines. anyone has any idea how horizontal lines should be handled?

Note: so from my understanding:
if next and previous lines are in same side, Don't count any intersection like so:

but if next and previous lines are in opposite side like so:

I have to look at my total number of vertex so far that i collected.

1- If Even, I've to add the first intersection.
2- If Odd, I've to add the last intersection.

but it wont work if lines are laid on the scan line!!. take a look at this example:

so in order to solve this problem, i come up with a solution that i need to run an optimization and rebuild the shape, simply by finding every line equation and for those that having same equation, remove the share vertex, which would make the shape simple so there wont be any extra vertex on any lines.

that's just do strange that they come so far about scan line algorithm but didn't mention anything about overlapping line equations. isn't it?

Answer 1

Let us do something inefficiently but correctly.

For every scan line we will start from Point0 go through whole polygon and come back to point0.

At scan line 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)

Though you have algorithms to sort the points in O(n) time don't worry about efficiency for now, just apply our favorite quicksort and sort the points along x-axis.

So we get only two points correctly.

At scan line 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)

In the worst case the polygon may have lots of windings. Any algorithm should correctly work for it. For example see below:

There are several way to do this. One for which local information is enough is following: Depending on the turn and which side the interior lies, we can decide which point to take.