Sign in to follow this  
CProgrammer

image polygon filling

Recommended Posts

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

Share this post


Link to post
Share on other sites
Hey thanks for responding, heres the ascii art of an example problematic polygon:


oooooooooooooooooooooooooooooooooooooooooooo
ooooooooxxxxxxxxooooooooooxxxxxxxooooooooooo
ooooooooxoooooooxooooooooxooooooxooooooooooo
ooooooooxooooooooxxxxxxxxoooooooxooooooooooo
ooooooooxoooooooxooooooooxooooooxooooooooooo
ooooooooxxxxxxxxooooooooooxxxxxxxooooooooooo
oooooooooooooooooooooooooooooooooooooooooooo


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.

Share this post


Link to post
Share on other sites
This is a tricky problem. It's definitely not possible to do it with a pure scan line algorithm, due to nasty cases such as these:


oooxxxxoooooooooxxxxooo
oooxoooxxxoooxxxoooxooo
oooxooooooxxxooooooxooo
oooxoooooooooooooooxooo
oooxxxxxxxxxxxxxxxxxooo



oooxxxxoooxxxoooxxxxooo
oooxoooxxxoooxxxoooxooo
oooxxxxoooxxxoooxxxxooo
ooooooooooooooooooooooo
ooooooooooooooooooooooo


In the first example, the second scan line should turn into two filled segments. However, in the second example an identical second scan line should become three filled segments.

It would be much easier if you still had the original data (points) from which the polygon was made. Failing that, we might have to keep some state from the scan line above, or perhaps use a different algorithm entirely? (perhaps based on flood fill???)

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this