c - 用多边形算法中的点填充C中的多边形

Question

我正在致力于实现一种填充多边形的算法。我使用本教程作为引用:http://alienryderflex.com/polygon_fill/

这是我的代码:

//point in polygon algorithm for filling polyons

void fill_polygon(Array *vx,Array *vy){
    int  nodes, nodeX[1000], pixelX, pixelY, i, j, swap,top,bot,right,left,polyCorners ;
    polyCorners = vx->used;
    if(polyCorners<=2){
        return;
    }

    bot = maximum(vy);
    top = minimum(vy);
    right = maximum(vx);
    left = minimum(vx);
    /*printf("Top %d  - Bot %d - Left %d - Right %d \n",top,bot,left,right);
    wait(40);*/
    for (pixelY=top; pixelY<bot; pixelY++) {

        //  building list of nodes
        nodes=0; j=polyCorners-1;
        for (i=0; i<polyCorners; i++) {
            if (vy->array[i]< pixelY && vy->array[j]>=pixelY
                ||  vy->array[j]< pixelY && vy->array[i]>= pixelY) {

                nodeX[nodes++]=(int) (vx->array[i]+(pixelY-vy->array[i])/(vy->array[j]-vy->array[i])*(vx->array[j]-vx->array[i])); 

            }
            j=i; 
        }   
        //   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++; 
            }
        }
     // filling pixels between nodes
        for (i=0; i<nodes; i+=2) {
            if   (nodeX[i  ]>=right) break;

            if   (nodeX[i+1]> left ) {
                if (nodeX[i  ]< left ) nodeX[i  ]=left ;
                if (nodeX[i+1]> right) nodeX[i+1]=right;
                for (pixelX=nodeX[i]; pixelX<nodeX[i+1]; pixelX++){

                    plot_pixel(pixelX,pixelY,current_color);
                }  
            }
        }       

    }
}

vx 和 vy 变量是包含多边形每个顶点的 x 和 y 坐标的数组。我已经检查这段代码很长时间了，但我仍然不知道我做错了什么。

这是我绘制一个简单的 4 边形多边形时得到的结果: 前: 图 I 正在绘制(这与下图不完全相同，但它也是一个 4 边形多边形)

之后:

如果有帮助，不知何故，当我绘制一个正方形时，算法会正确填充它:

你能帮我找出代码中的错误吗？

Answer 1

vx->array[i]+(pixelY-vy->array[i])/(vy->array[j]-vy->array[i])*(vx->array[j]-vx->array[i])

假设这些都是整数，这将进行整数除法。也就是说，它会丢弃除法后的小数部分。

您可以先将涉及的数字之一转换为 double，以进行 double 除法:

vx->array[i]+(pixelY-vy->array[i])/(double)(vy->array[j]-vy->array[i])*(vx->array[j]-vx->array[i])
                                   ^^^^^^^^

或者您可以交换运算顺序，以便首先进行乘法。 (但是，如果数字足够大，这可能会导致溢出)

vx->array[i]+(pixelY-vy->array[i])*(vx->array[j]-vx->array[i])/(vy->array[j]-vy->array[i])