【计算机图形学】2-4 多边形的绘制与填充

　　当我们用顶点记录多边形时，对于直线的绘制和前面的图形无异，但当填充颜色的时候，我们并不能直接获得要填充的区域的起点和终点，这时通常采用扫描线算法。

　　多边形区域填充的时候，每一行与多边形边的交点很容易获得，问题在于当在一行获得多个交点时，如果判断相邻点对是在多边形内还是多边形外。对于每一行，我们在多边形外引一条水平的射线，这条射线必然与多边形有偶数个交点，因为多边形的大小是有限的，射线进入多边形内部后必然还要再出多边形，进和出的次数一定相等，这样，对所有交点排序后，每两个相邻的点对都对应多边形内部要填充的一段区域。

　　接下来要考虑的是边界条件。我们引出的是水平的射线，当多边形的一条边水平时，我们要考虑它两侧不水平的边的位置。如果两侧的不水平边分居水平边的两侧，则射线有进或出的过程，随便记录水平边的一个端点即可；如果两侧的不水平边在水平边的同侧，则射线不会进出多边形，无需记录端点。

　 　当射线的交点是多边形的顶点时，同样考虑顶点两侧的边是否在同一侧，如果不在同一侧则记录，在同一侧则不记录。由于顶点和水平线可能重复，要注意考虑判断条件，不能重复记录。

基本代码：

draw_polygon.h

#ifndef DRAW_POLYGON_H_INCLUDED
#define DRAW_POLYGON_H_INCLUDED

#include "define.h"
#include "draw_point.h"
#include "draw_line.h"
#define POLYGON_MAX_POINT 100

typedef struct Polygon_xi
{
    int32 x[POLYGON_MAX_POINT];
    int32 y[POLYGON_MAX_POINT];
    int32 pointNumber;
    int32 isFinished;
}Polygon_xi;

void draw_polygon_T_xi(Polygon_xi polygon);

#endif // DRAW_POLYGON_H_INCLUDED

draw_polygon.c

#include "draw_polygon.h"

void draw_polygon_T_xi(Polygon_xi polygon)
{
    int32 i, j, k, a, b;
    int32 max_x, min_x;
    int32 max_y, min_y;
    int32 temp;
    int32 set[1024];
    int32 setNumber;
    int16 isHorizon[POLYGON_MAX_POINT];
    if(polygon.isFinished)
    {
        max_x = max_y = - (1 << 30);
        min_x = min_y = 1 << 30;
        for(i=0;i<polygon.pointNumber;++i)
        {
            max_x = max(max_x, polygon.x[i]);
            min_x = min(min_x, polygon.x[i]);
            max_y = max(max_y, polygon.y[i]);
            min_y = min(min_y, polygon.y[i]);
        }
        polygon.x[polygon.pointNumber] = polygon.x[0];
        polygon.y[polygon.pointNumber] = polygon.y[0];
        polygon.x[polygon.pointNumber+1] = polygon.x[1];
        polygon.y[polygon.pointNumber+1] = polygon.y[1];
        for(i=1;i<=polygon.pointNumber+1;++i)
        {
            isHorizon[i] = (polygon.y[i] == polygon.y[i-1]);
        }
        isHorizon[0] = (polygon.y[0] == polygon.y[polygon.pointNumber - 1]);
        for(i=min_y;i<max_y;++i)
        {
            setNumber = 0;
            for(j=1;j<=polygon.pointNumber;++j)
            {
                if(i == polygon.y[j] && isHorizon[j])
                {
                    temp = 1;
                    k = j + 1;
                    while(polygon.y[k] == polygon.y[j])
                    {
                        if(++k == j)
                        {
                            temp = 0;
                            break;
                        }
                        if(k >= polygon.pointNumber)
                        {
                            k -= polygon.pointNumber;
                        }
                    }
                    a = k;
                    b = j - 2;
                    if(b <= 0)
                    {
                        b += polygon.pointNumber;
                    }
                    if(((polygon.y[a] > polygon.y[j] && polygon.y[b] < polygon.y[j]) ||
                       (polygon.y[a] < polygon.y[j] && polygon.y[b] > polygon.y[j])) && temp)
                    {
                        set[setNumber++] = polygon.x[j];
                    }
                }
            }
            for(j=1;j<=polygon.pointNumber;++j)
            {
                if(i == polygon.y[j])
                {
                    if(isHorizon[j] || isHorizon[j+1])
                    {
                        continue;
                    }
                    if((polygon.y[j-1] > polygon.y[j] && polygon.y[j+1] < polygon.y[j]) ||
                       (polygon.y[j-1] < polygon.y[j] && polygon.y[j+1] > polygon.y[j]))
                    {
                        set[setNumber++] = polygon.x[j];
                    }
                }
            }
            for(j=1;j<=polygon.pointNumber;++j)
            {
                if(i > min(polygon.y[j], polygon.y[j-1]) &&
                   i < max(polygon.y[j], polygon.y[j-1]))
                {
                    temp = 1.0 * (i - polygon.y[j-1]) / (polygon.y[j] - polygon.y[j-1]) *
                           (polygon.x[j] - polygon.x[j-1]) + polygon.x[j-1];
                    if(temp >= min(polygon.x[j], polygon.x[j-1]) &&
                       temp <= max(polygon.x[j], polygon.x[j-1]))
                    {
                        set[setNumber++] = temp;
                    }
                }
            }
            for(j=0;j<setNumber;++j)
            {
                for(k=j+1;k<setNumber;++k)
                {
                    if(set[j] > set[k])
                    {
                        swap(set[j], set[k]);
                    }
                }
            }
            for(j=0;j<setNumber-1;j+=2)
            {
                for(k=set[j];k<=set[j+1];++k)
                {
                    draw_point_brush_2i(k, i);
                }
            }
        }
        for(i=1;i<=polygon.pointNumber;++i)
        {
            draw_line_4i(polygon.x[i-1], polygon.y[i-1], polygon.x[i], polygon.y[i]);
        }
    }
    else
    {
        for(i=1;i<polygon.pointNumber;++i)
        {
            draw_line_4i(polygon.x[i-1], polygon.y[i-1], polygon.x[i], polygon.y[i]);
        }
        draw_line_4i(polygon.x[polygon.pointNumber],
                     polygon.y[polygon.pointNumber],
                     polygon.x[polygon.pointNumber - 1],
                     polygon.y[polygon.pointNumber - 1]);
    }
}