Efficient Polygon Fill Algorithm With C Code Sample

Efficient Polygon Fill Algorithm With C Code Sample
© 2007 Darel Rex Finley. This complete article, unmodified, may be freely distributed for educational purposes.

Before reading this page, you should thoroughly familiarize yourself with the point-in-polygon algorithm.

While the point-in-polygon algorithm is useful for determining whether a few points are inside a polygon, it is woefully inefficient for filling a polygon, because it requires checking every side of the polygon for every pixel in the image. To speed things up tremendously, we will check each side of the polygon only once per pixel row. It works like this:

Figure 1

Figure 1 shows a polygon. We are about to render one row of pixels. All the pixels on that row have the same Y coordinate, which is represented by the red line in the figure. Loop through the polygon and find the threshold-crossing nodes, just as in the point-in-polygon algorithm — but instead of comparing them with an X coordinate, store them all in a list. Figure 1 shows the indices (0 through 5) of the nodes. In this example, the polygon starts at the blue corner, and is traced counter-clockwise, which generates a fairly random horizontal order for the nodes.

Figure 2

Next, sort the node list so that it proceeds from left-to-right, as shown in Figure 2. This takes a little time, but we have to do it only once per pixel row.

Figure 3

Now, as shown in Figure 3, it is a simple matter to fill all the pixels between each pair of nodes — from node 0 to 1, node 2 to 3, and node 4 to 5.

Q: What happens if my program is filling a row of pixels that falls exactly on one of the corners of the polygon? Will the algorithm fail?

No, it will work just fine — see the point-in-polygon page for a discussion (starting at Figure 4) of what happens in such cases.

C Code Sample

//  public-domain code by Darel Rex Finley, 2007





int  nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ;



//  Loop through the rows of the image.

for (pixelY=IMAGE_TOP; pixelY<IMAGE_BOT; pixelY++) {



  //  Build a list of nodes.

  nodes=0; j=polyCorners-1;

  for (i=0; i<polyCorners; i++) {

    if (polyY[i]<(double) pixelY && polyY[j]>=(double) pixelY

    ||  polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) {

      nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])

      *(polyX[j]-polyX[i])); }

    j=i; }



  //  Sort the nodes, via a simple “Bubble” sort.

  i=0;

  while (i<nodes-1) {

    if (nodeX[i]>nodeX[i+1]) {

      swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }

    else {

      i++; }}



  //  Fill the pixels between node pairs.

  for (i=0; i<nodes; i+=2) {

    if   (nodeX[i  ]>=IMAGE_RIGHT) break;

    if   (nodeX[i+1]> IMAGE_LEFT ) {

      if (nodeX[i  ]< IMAGE_LEFT ) nodeX[i  ]=IMAGE_LEFT ;

      if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT;

      for (pixelX=nodeX[i]; pixelX<nodeX[i+1]; pixelX++) fillPixel(pixelX,pixelY); }}}

(Bug fix by Gilbert Maréchal.)

Send me an e-mail!

Does the brace style in the above code sample freak you out? Click here to see it explained in a new window.