Hi guys, I have an image with a polygon border marked by black pixels and the background marked as white. Now the polygon is only defined by its border pixels, which is a line starting at the top most pixel, which is also the most left on its height, and ending back where it started. The problem is that the border can have a case where two lines of the polygon lie on top of eachother, i.e. a line of pixels is traversed one way then some loop is done and then the line is traversed back again. The question I now have is: How can I efficiently fill the content of the polygon with black pixels. Im pretty sure an approach which checks if border pixels have top and bottom neighbors correctly would work except in the case of the multiply traversed line. I could remove these lines but Id like to avoid it since removing them could result in a polygon being split into two polygons. This wouldnt be too bad however. So any ideas on how to achieve this efficiently are welcome. -CProgrammer

Hey thanks for responding, heres the ascii art of an example problematic polygon:

ooooooooooooooooooooooooooooooooooooooooooooooooooooxxxxxxxxooooooooooxxxxxxxoooooooooooooooooooxoooooooxooooooooxooooooxoooooooooooooooooooxooooooooxxxxxxxxoooooooxoooooooooooooooooooxoooooooxooooooooxooooooxoooooooooooooooooooxxxxxxxxooooooooooxxxxxxxooooooooooooooooooooooooooooooooooooooooooooooooooooooo

The middle section is traversed twice.
If I use a scan line algorithm that goes top to bottom then the program would wrongly think that after the middle section a 'inside' region starts. Counting how many intersections there are wont work either since two such doubleed lines could be in parallel.
Scanning left to right would also cause problems.
I could remove the doubled lines by traversing the border once appropriately but then Im left with two polys. Not too big of a deal but Im still hoping there is a cleaner solution.

I have been considering flood filling the outside area and then just inverting. This has two problems:
1. Its not all that efficient, although not bad either, I have the bounding box of the polygon.
2. I would need to backup all the other data I have in the image outside of the polygon. Basically each pixel can have one flag, so for every flag id need to create a temporary flag and then reset it once Im done. I suppose I could reserve one bit as being a mark bit, sadly in my current design this gets a little ugly and Id like to avoid it.

Thanks for your input I was fearing that I missed something. That example is very clear on the problem. I guess its a choice between the above or removing the overlapping lines altogether and hence splitting polygons.

EDIT: Ive decided to implement the flood filling technique. Lets see how that works, I found a way to mark pixels elegantly.


[Edited by - CProgrammer on January 19, 2009 2:01:20 PM]