10

I need to create a binary bitmap from a closed 2D polygon represented as a list of points. Could you please point me to efficient and sufficiently simple algorithms to do that, or, even better, some C++ code?

Thanks a lot!

PS: I would like to avoid adding a dependency to my project. However if you suggest an open-source library, I can always look at the code, so it can be useful too.

Tim Gee
  • 1,062
  • 7
  • 9
static_rtti
  • 53,760
  • 47
  • 136
  • 192

5 Answers5

13

The magic google phrase you want is either "non-zero winding rule" or "even odd polygon fill".

See the wikipedia entries for:

Both are very easy to implement and sufficiently fast for most purposes. With some cleverness, they can be made antialiased as well.

ideasman42
  • 42,413
  • 44
  • 197
  • 320
plinth
  • 48,267
  • 11
  • 78
  • 120
  • 1
    @plinth: isn't that over-kill for simple polygons? – yairchu Aug 27 '09 at 14:27
  • 5
    What's a simple polygon? @static_rtti doesn't specify how many points or if the polygons will always be convex, therefore a general solution is the correct answer. NZW and EO are butt-simple and lend themselves to scanline oriented solutions, etc, etc, etc. – plinth Aug 27 '09 at 14:31
  • 1
    @plinth: Thanks, this is exactly what I was looking for! Googling stuff can be tricky when you don't have that magic phrase :-) – static_rtti Aug 27 '09 at 15:01
  • 3
    @plinth: a simple polygon is one whose segments do not cross each other. see http://en.wikipedia.org/wiki/Simple_polygon – yairchu Aug 27 '09 at 16:31
  • This answer contains links that describe a way to determine for each sample if it's within the polygon or not. Even though possible to implement this way, it's highly inefficient, so it's never done like that in practice (except for rasterizing a simple triangle on the GPU, even that with a stretch...). Actual polygon rasterization algorithms, almost universally, involve sorting the vertices, following the edges, and filling the inside spans. None of it is mentioned in this answer. – Yakov Galka May 27 '23 at 21:04
6

You can check out the polygon fill routine in Pygame. Look at the draw_fillpoly function.

The algorithm is pretty simple. It finds all the positions that each segment intersects along the Y axis. These intersections are sorted, and then horizontally fills each pair of intersections.

This will handle complex and intersecting shapes, but obviously you could crush this algorithm with large amounts of segments.

jhabbott
  • 18,461
  • 9
  • 58
  • 95
Peter Shinners
  • 3,686
  • 24
  • 24
5

For a robust implimentation of the "even-odd rule"

See Darel Rex Finley's Efficient Polygon Fill, or Blender's version of it.

This is an odd/even filling method which supports self intersecting lines, without needing complex code to detect such situations, and doesn't depend on winding (the polygon can be reversed and yield the same results).

Update, I made an optimized version of Darel Rex's method that avoids looping over all coordinates for each y-pixel.

Stand alone implementations:

While speedup will likely be exponential, From a quick test, its around 7.5x faster (11x when removing round call), using an arbitrary hand drawn scribble over a 2540x1600 region, YMMV.

ideasman42
  • 42,413
  • 44
  • 197
  • 320
3
  • Triangulate your polygon
  • Raster each of the triangles (if you are using a GPU then it can do it for you instead, it's a primitive operation of GPUs)
    • If the triangle doesn't have a segment that is parallel to the x axis, then break it into two triangles with a line that is parallel to the x axis and goes through it's point with the median-y
    • Now the remaining task is to draw a triangle which has a segment that is parallel to the x axis. Such a triangle has a left-side segment and a right-side segment
    • Iterate the triangle's scan-lines (min-y to max-y). For each y calculate the left and right segments' points in that scanlines. Fill the scanline segment these two points (a simple memset).

Complexity is O(Area in pixels)

yairchu
  • 23,680
  • 7
  • 69
  • 109
  • 1
    How would you rasterize the resulting triangles? One by one by traversing the whole image each time? Isn't that likely to be very slow? – static_rtti Aug 27 '09 at 14:35
  • @static_rtti: what do you mean traversing the whole image each time? – yairchu Aug 27 '09 at 16:32
  • @static_rtti: I added an explanation of how to rasterize a triangle – yairchu Aug 27 '09 at 17:11
  • The crucial point here is "calculate the left and right segments". Doing it separately for each scanline is prohibitively slow; a better way is to calculate the increment, and apply it to the starting value. – Pavel Minaev Aug 27 '09 at 23:05
  • 1
    I think this answer glosses over the complexity involved with triangulating the polygon. For simple polygons its not so bad. But for self intersecting polygons this is rather involved. - See http://www.angusj.com/delphi/clipper.php as an example. – ideasman42 Aug 05 '15 at 02:23
2

In addition to scanline algorithms mentioned by others, there's a sufficiently different approach described in the paper Wavelet Rasterization by J. Manson and S. Schaefer.

Loosely speaking, the algorithm splats every edge onto the wavelet domain, then takes the inverse wavelet transform to reconstruct the image.

The advantage is that the algorithm is able to calculate exact coverage (i.e. anti-aliasing), which is extremely hard to achieve with scanline algorithms. It's also tolerant to broken polygons; i.e. polygons with a discontinuous contour.

Yakov Galka
  • 70,775
  • 16
  • 139
  • 220