Algorithm to detect if a pixel is within a boundary

Question

Hi there. We're currently creating a simple application for image manipulation in Silverlight, and we've hit a bit of a snag. We want users to be able to select an area of an image (either by drawing a freehand line around their chosen area or by creating a polygon around it), and then be able to apply effects to the pixels within that selection.

Creating a selection of images is easy enough, but we want a really fast algorithm for deciding which pixels should be manipulated (ie. something to detect which pixels are within the user's selection).

We've thought of three possibilities so far, but we're sure that there must be a really efficient and quick way of doing this that's better than these.

1. Pixel by pixel. We just go through every pixel in an image and check whether it's within the user selection. Obviously this is far too slow!

2. Using a Line Crossing Algorithim. The type of thing seen here.

3. Flood Fill. Select the pixels along the path of the selection and then perform a flood fill within that selection. This might work fine.

This must a problem that's commonly solved, so we're guessing there's a ton more solutions that we've not even thought of.

What would you recommend?

Answer 1

You should be able to use your polygon to create a clipping path. The mini-language for describing polygons for Silverlight is quiet well documented.

Alter the pixels on a copy of your image (all pixels is usually easy to modify than some pixels), then use the clipping path to render only the desired area of the changes back to the original image (probably using an extra buffer bitmap for the result).

Hope this helps. Just throwing the ideas out and see if any stick :)

Answer 2

Flood fill algorithm is a good choice.

Take a look at this implementation:

Queue-Linear Flood Fill: A Fast Flood Fill Algorithm