0

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!

Takeshi
  • 150
  • 1
  • 10
  • Someone already solved this problem in order to draw polygons. So why not draw them and see which pixels are set? If your polygons are sparse you can partition the image space to avoid iterating over all the pixels. – Zong Sep 09 '15 at 00:06

2 Answers2

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).

azt
  • 2,100
  • 16
  • 25
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.

Community
  • 1
  • 1
rodamn
  • 2,191
  • 19
  • 24