6

Possible Duplicate:
Rasterizing a 2D polygon

I need to raster a polygon including its inner area (determine all tiles of a grid that lie inside the polygon). Currently I determine the boundary tiles by using a simple Bresenham but I have no efficient way up to now to raster the "inside" of the polygon (which might be concave as well). My approach so far is to limit the tile range to the rectangle including the polygon an then determine for every tile center whether it lies inside or outside using the polygon winding algorithm. This is quit inefficient since it involves checking every polygon boundary segment for every tile. From a first view there should definitely be a faster approach e.g. sth. like winding using the rastered boundary. Is there a standard algorithm which tackles this problem and perhaps even a library implementation in C++ ?

Community
  • 1
  • 1
Martin
  • 4,738
  • 4
  • 28
  • 57
  • 2
    There are quite a few resources on the net. Here are the first two I found using a Google search: http://alienryderflex.com/polygon_fill/ and http://ezekiel.vancouver.wsu.edu/~cs442/lectures/raster/polyfill/poly.pdf – NPE Dec 12 '12 at 10:26
  • 1
    @Potatoswatter: Thanks for the link. As I said I need the innards as well and know the winding rule, so I think it is not a duplicate, but triangulization and the rastering the triangles might be the way to go. – Martin Dec 12 '12 at 10:45
  • @NPE: Cool, the first link is exactly what I was looking for. If you make it an answer I can accept it right away – Martin Dec 12 '12 at 10:46
  • @Martin All the answers I saw at that page were for filled polygons, and I didn't notice anything about triangles… I haven't implemented it but my understanding is you want to find the intercepts and use the even/odd rule: every time the raster crosses a polygon line, it alternates between being inside and outside. – Potatoswatter Dec 12 '12 at 11:40
  • @Potatoswatter: The first answer to the referred question points to winding and odd-even fill. As as the link NPE pointed me to clearly shows: This is *not* a performant way to fill (in the sense of color pixels) the innards of a polyon. You need to use an additional scan line for the filling to be efficient – Martin Dec 14 '12 at 12:48

1 Answers1

8

There are quite a few resources on the net, for example:

Community
  • 1
  • 1
NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • 1
    That algorithm won't work with some of the polygons that have axis-parallel edges with whole coordinates (y coordinate if the scanline is horizontal, x coordinate if the scanline is vertical). For example, this will fail on a polygon of axis-parallel segments that bounds a letter T or П. – gvlasov Nov 07 '14 at 15:28