Filling a polygon

Question

I created this function that draws a simple polygon with n number of vertexes:

void polygon (int n)
{
    double pI = 3.141592653589;
    double area = min(width / 2, height / 2);
    int X = 0, Y = area - 1;
    double offset = Y;
    int lastx, lasty;

    double radius = sqrt(X * X + Y * Y);
    double quadrant = atan2(Y, X);

    int i;

    for (i = 1; i <= n; i++)
    {
        lastx = X; lasty = Y;
        quadrant = quadrant + pI * 2.0 / n;

        X = round((double)radius * cos(quadrant));
        Y = round((double)radius * sin(quadrant));

        setpen((i * 255) / n, 0, 0, 0.0, 1); // r(interval) g b, a, size

        moveto(offset + lastx, offset + lasty); // Moves line offset
        lineto(offset + X, offset + Y); // Draws a line from offset
    }
}

---

How can I fill it with a solid color? I have no idea how can I modify my code in order to draw it filled.

Answer 1

The common approach to fill shapes is to find where the edges of the polygon cross either each x or each y coordinate. Usually, y coordinates are used, so that the filling can be done using horizontal lines. (On framebuffer devices like VGA, horizontal lines are faster than vertical lines, because they use consecutive memory/framebuffer addresses.)

In that vein,

void fill_regular_polygon(int center_x, int center_y, int vertices, int radius)
{
    const double a = 2.0 * 3.14159265358979323846 / (double)vertices;
    int i = 1;
    int y, px, py, nx, ny;

    if (vertices < 3 || radius < 1)
        return;

    px = 0;
    py = -radius;
    nx = (int)(0.5 + radius * sin(a));
    ny = (int)(0.5 - radius * cos(a));
    y  = -radius;

    while (y <= ny || ny > py) {
        const int x = px + (nx - px) * (y - py) / (ny - py);
        if (center_y + y >= 0 && center_y + y < height) {
            if (center_x - x >= 0)
                moveto(center_x - x, center_y + y);
            else
                moveto(0, center_y + y);
            if (center_x + x < width)
                lineto(center_x + x, center_y + y);
            else
                lineto(width - 1, center_y + y);
        }
        y++;
        while (y > ny) {
            if (nx < 0)
                return;
            i++;
            px = nx;
            py = ny;
            nx = (int)(0.5 + radius * sin(a * (double)i));
            ny = (int)(0.5 - radius * cos(a * (double)i));
        }
    }
}

Note that I only tested the above with a simple SVG generator, and compared the drawn lines to the polygon. Seems to work correctly, but use at your own risk; no guarantees.

For general shapes, use your favourite search engine to look for "polygon filling" algorithms. For example, this, this, this, and this.