How to determine the points (pixels) that are within a given polygon inscribed in an image

Question

Please consider the following scenario:

• a component that holds an image;
• a list of polygons, defined by the user, to create areas within the image;
• each polygon consists of a list of at least 3 points (their sequence determines the polygon shape);
• each point consists of a (x, y) value pair;
• each value in an (x, y) pair is between 0 and 1, and represents where the point is in % (width, height) to the image;

What I need then is to execute some process to all of the areas of the polygons, one pixel at a time. In my particular scenario, to 'sweep' the whole image pixel by pixel and verify if it's within any polygon, is not acceptable. Bonus: if a pixel has already been processed, but it's part of more than one polygon, do not process it again.

I was thinking that maybe I could, given any polygon and an image (arbitrary width x height), generate a list of pixels that are within the polygon's area. The problem then would be more of a math question, but I'm stuck. Other approaches are welcome too! Any ideas? Thanks a lot!

Answer 1

See Rasterizing a 2D polygon. In this case, instead of setting each pixel to particular color, you can execute your process on the specific pixel.

Answer 2

What you need is a polygon rasterizer, that gives all the pixels inside a polygon, e.g. http://alienryderflex.com/polygon_fill/

If you want to combine the polygons to factor out double pixels, then I'd suggest http://www.angusj.com/delphi/clipper.php

Compute the union of all the polygons and add them as positive and with non-zero-winding rule, or any other rule you want to post on your polygons (only relevant if they are self-overlapping).