When I look at polyfill algorithm tutorials/articles or examples, nothing mentioned about how to handle horizontal lines. Does anyone have any idea how horizontal lines should be handled?

For instance, consider the following image:

example lines

For intersection I wrote if the line on the scan line count it as 1 point, even I count as 2 point or no point, wont help. Any idea how should I handle the horizontal line?

Edit: here a complex example of horizontal line intersection, let's take a look at line 3: enter image description here

Alright, if we take a look at next point and previous point of the intersection of both end of horizontal line, if those point are in same side, means I can count them in or out, doesn't effect the whole calculation.
But if they are are opposite side, I have to count them in and count one side extra.

What do I mean?
Take InterS1 and InterS2 as an example, so when I get this I have count that horizontal line as 3 points:

point1 = InterS1
point2 = InterS2
point3 = InterS2

Why I need to do that?

  1. When next point and previous point are in different direction, is letting us know that our intersection line crossing outside and passing through inside of shape.
  2. Also because line can be created when there is start point and end point, so I need to have even number to draw lines.

So now I have no idea base on what I need to add the extra point to one side.
Do I make sense?

  • $\begingroup$ What are you doing when you have a V shaped corner? Either you have to ignore it or consider it as two vertices, right!! $\endgroup$
    – Shreesh
    Feb 18 '16 at 7:24
  • $\begingroup$ @Shreesh in that case i will look at next and previous vertex, is they are not on the same side, i will count it as intersection, if they are on same side, i will just ignore it, like this: drive.google.com/file/d/0BwoMn9VKDw-taXlNendza09BQXM/… $\endgroup$
    – Bear
    Feb 18 '16 at 7:38
  • $\begingroup$ Do the same for horizontal line. $\endgroup$
    – Shreesh
    Feb 18 '16 at 10:16
  • $\begingroup$ yeah, i did that, this is what i get:drive.google.com/file/d/0BwoMn9VKDw-tRElHSElrejcwd0k/… haven't apply ignore the horizontal yet. $\endgroup$
    – Bear
    Feb 18 '16 at 10:44
  • $\begingroup$ @Shreesh nah, not really, okay here what i did, for horizontal lines, if the previous point and next point are in same direction, means they are in the shape, but for those horizontal that next and previous points going different direction, i have to count those 2 points as 3 point, but i have no idea base on what i need to add the extra one to which side, okay let me draw it. maybe it's more clear what i mean. $\endgroup$
    – Bear
    Feb 22 '16 at 1:34

See Polygon Filling. It gives one method to deal with edges parallel to scanline. It says that it is imperfect, but you can ignore the horizontal edges. Other solution is to take either left or right endpoint of horizontal edge (any one point only). Yet another solution is to take right or left endpoint depending on the situation, so that whole edge is filled.

If you ignore horizontal lines you should get something like the following:

enter image description here

  • $\begingroup$ i see... i might work on my current problem, but i afraid it's not a permanent solution, by removing the point on right or left or even removing the horizontal, look at this [Image][1] [1]: drive.google.com/file/d/0BwoMn9VKDw-tdWJEenFZMm0xeHM/… $\endgroup$
    – Bear
    Feb 18 '16 at 7:00
  • $\begingroup$ but how are intersection 5 and intersection 6 are not on horizontal? if i ignore horizontal i have to ignore intersection, 2, 3, 4, 5 ,6 and 7? $\endgroup$
    – Bear
    Feb 18 '16 at 7:14
  • $\begingroup$ You need to check if the polygon crosses at scan line. If it does not cross (eg comes from below and goes back) you may ignore it. But if it, say, comes from below and goes above, you need to consider it. $\endgroup$
    – Shreesh
    Feb 18 '16 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.