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.

Answer 2

There are 2 different ways to implement a solution:

Scan-line

Starting at the coordinate that is at the top (smallest y value), continue to scan down line by line (incrementing y) and see which edges intersect the line.

• For convex polygons you find 2 points, (x1,y) and (x2,y). Simply draw a line between those on each scan-line.
• For concave polygons this can also be a multiple of 2. Simply draw lines between each pair. After one pair, go to the next 2 coordinates. This will create a filled/unfilled/filled/unfilled pattern on that scan line which resolves to the correct overall solution.

In case you have self-intersecting polygons, you would also find coordinates that are equal to some of the polygon points, and you have to filter them out. After that, you should be in one of the cases above.

If you filtered out the polygon points during scan-lining, don't forget to draw them as well.

Flood-fill

The other option is to use flood-filling. It has to perform more work evaluating the border cases at every step per pixel, so this tends to turn out as a slower version. The idea is to pick a seed point within the polygon, and basically recursively extend up/down/left/right pixel by pixel until you hit a border.

Picking a seed point Usually this is done by randomly selecting a coordinate more or less inside a bound around all corner vertices. No matter which point you select as seed point, first you have to check that the chosen point is either inside, outside or at the very edge of the polygon. You can do this by tracing an imaginary line from the seed point to the 'edge of the canvas' (or infinity). If that imaginary trace intersects with any of the polygon edges a total number of times that is odd, the point lies inside the polygon. If the trace runs exactly through one of the corner vertices, that counts as 2 intersections and won't contribute to 'becoming inside' (for concave polygons - otherwise you can count it as 1). In that case try a different coordinate as seed point. Sometimes it makes sense to evaluate which seed point tends to have a higher fill-ratio based on how far it is from the nearest edge / corner vertex, especially if your fill algorithm is biased to fill faster in a specific direction (e.g. horizontal lines). Usually the approach is to start with points near the center of the bounding box.

Performance The algorithm has to read and write the entire surface of the polygon, and does not cross self-intersection points. There can be considerable stack-buildup (for naive implementations at least) for large surfaces, and the reduced flexibility you have for the border condition is pixel-based (e.g. flooding into gaps when other things are drawn on top of the polygon). In this sense, this is not a mathematically correct solution, but it works well for many applications.

Answer 3

Anyway, it seems that I / solved / this myself again, when not relying on assistance (or any attempt for it)

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;

    while(Y-->0) {
    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);
        setpen(255, 0, 0, 0.0, 1); // just red

        moveto(offset + lastx, offset + lasty);
        lineto(offset + X, offset + Y);
    } }
}

As you can see, it isn't very complex, which means it might not be the most efficient solution either.. but it is close enough. It decrements radius and fills it by virtue of its smaller version with smaller radius. On that way, precision plays an important role and the higher n is the less accuracy it will be filled with.

Answer 4

The most efficient solution is by decomposing the regular polygon in trapezoids (and one or two triangles).

By symmetry, the vertexes are vertically aligned and it is an easy matter to find the limiting abscissas (X + R cos(2πn/N) and X + R cos(2π(+1)N)).

You also have the ordinates (Y + R sin(2πn/N) and Y + R sin(2π(+1)N)) and it suffices to interpolate linearly between two vertexes by Y = Y0 + (Y1 - Y0) (X - X0) / (X1 - X0).

Filling in horizontal runs is a little more complex, as the vertices may not be aligned horizontally and there are more trapezoids.