高效多边形填充算法及其C例程

英文原文：http://alienryderflex.com/polygon_fill/

在阅读本页之前你应该彻底熟悉（point-in-polygon）“点在多边形内”算法。

“点在多边形内”算法用于判断一些点是否在多边形内是非常有用的，可悲的是如果用于填充多边形的话，是非常低效的，因为图像中的每一个像素都要使用多边形的所有边来判断其是否在多边形内。为了大幅地加快处理速度，我们只需要为每个像素行使用一次多边形的所有边。其工作原理如下图所示：

图 1

图1显示了一个多边形。我们想填充多边形内的一行像素。同一行的像素的Y坐标值都相同，如上图中红线所示。循环多边形的每一条边并找到与当前行的交叉点，就像“点在多边形内”的算法一样——但是之比较它们的x坐标，将这些交叉点存成一个列表。如上图所示包含6个点（从0到5）。在这个例子中多边形是从蓝色的角点开始并按逆时针画成的，所以使得最后得到的交叉点的顺序看起来是随机的一样。

图 2

接下来我们要将这些点按X坐标值从小到大排序，如图2所示。这需要费一点时间，但是每一行只需要排序一次。

图 3

现在，如图3所示，我们只要简单地将每一对点中间的点填充起来即可（从0到1,2到3,4到5）。

问题：如果我的程序要填充的像素行正好只包含了多边形的一个角点会发生什么？算法会失效吗？

答案是：不会，算法任然能正常工作。如果想知道遇到这种情况会出现什么，请参见“点在多边形内”的页面的讨论（从图4开始）。

C代码的例子：

//  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 (j=nodeX[i]; j<nodeX[i+1]; j++) fillPixel(j,pixelY); }}}