What is a way to fill a closed irregular shape with a color?

Question

I am currently making a pixel art program designed to let people create pixel art.

The individual pixels are actually 8x8 rectangles that are created when the user clicks on the screen.

What I'm trying to make here is similar to the "fill" option in Microsoft Paint. A user draws some shape and when he clicks inside it using the "fill" tool, the shape's inside is filled with the selected color whilst the outside is intact.

I tried creating my own algorithm but the greatest obstacle that I've faced is knowing whether or not the pixels that I'm testing are inside the shape or not. I finally gave up and decided to Google it but came up empty handed.

I'm programming this in Python 2.7 but the question isn't really language specific. I just need to understand the algorithm.

Answer 1

You need to use a flood fill algorithm. Here is a good article on Wikipedia: http://en.wikipedia.org/wiki/Flood_fill

This link discusses Python implementation: Flood Fill Algorithm Python