填充多边形

Question

我创建了这个函数，它绘制一个具有 n 个顶点的简单多边形：

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
    }
}

---

如何用纯色填充它？ 我不知道如何修改我的代码才能将其填充。

Answer 1

填充形状的常见方法是找到多边形边缘与每个 x 或每个 y 坐标相交的位置。通常使用y坐标，这样就可以使用水平线进行填充。 （在 VGA 等帧缓冲设备上，水平线比垂直线更快，因为它们使用连续的内存/帧缓冲地址。）

本着这种精神，

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));
        }
    }
}

请注意，我仅使用简单的 SVG 生成器测试了上述内容，并将绘制的线条与多边形进行了比较。看起来工作正常，但使用风险自负；没有任何保证。

对于一般形状，请使用您最喜欢的搜索引擎查找“多边形填充”算法。例如，这个、这个、这个和这个。

Answer 2

有两种不同的方法来实施解决方案：

扫描线

从顶部坐标（最小 y 值）开始，继续逐行向下扫描（递增 y）并查看哪些边与该线相交。

• 对于凸多边形，您可以找到 2 个点：(x1,y) 和 (x2,y)。只需在每条扫描线上的线之间画一条线即可。
• 对于凹多边形，这也可以是 2 的倍数。只需在每对之间画线即可。一对之后，转到接下来的 2 个坐标。这将在该扫描线上创建一个填充/未填充/填充/未填充图案，解析为正确的整体解决方案。

如果你有自相交的多边形，你还会发现坐标等于某些多边形点，你必须将它们过滤掉。之后，您应该处于上述情况之一。

如果您在扫描衬里期间过滤掉了多边形点，请不要忘记也绘制它们。

洪水填满

另一种选择是使用洪水填充。它必须执行更多的工作来评估每个像素的每个步骤的边界情况，因此这往往会成为一个较慢的版本。这个想法是在多边形内选择一个种子点，并且基本上逐个像素地递归地向上/向下/向左/向右延伸，直到到达边界。

选择种子点 通常，这是通过随机选择一个或多或少在所有角顶点周围的边界内的坐标来完成的。无论选择哪个点作为种子点，首先必须检查所选点是否位于多边形的内部、外部或边缘。有时，根据距最近的边/角顶点的距离来评估哪个种子点往往具有更高的填充率是有意义的，特别是如果您的填充算法偏向于在特定方向（例如水平线）上填充得更快.

性能 该算法必须读写多边形的整个表面，并且不跨越自交点。对于大表面，可能会有相当大的堆栈堆积（至少对于幼稚的实现而言），并且边界条件的灵活性降低是基于像素的（例如，当在多边形顶部绘制其他东西时，会涌入间隙）。从这个意义上说，这不是一个数学上正确的解决方案，但它适用于许多应用程序。

Answer 3

无论如何，在不依赖帮助（或任何尝试）的情况下，我似乎再次自己/解决了/这个问题

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);
    } }
}

正如您所看到的，它并不是很复杂，这意味着它可能也不是最有效的解决方案..但它已经足够接近了。 它减少半径并凭借其较小半径的较小版本来填充它。 这样，精度起着重要作用，n越高，填充的精度就越低。

Answer 4

最有效的解决方案是将正多边形分解为梯形（以及一两个三角形）。

通过对称性，顶点垂直对齐，很容易找到极限横坐标（

X + R cos(2πn/N)

和

X + R cos(2π(+1)N))

。

您还拥有坐标（

Y + R sin(2πn/N)

和

Y + R sin(2π(+1)N)

），并且足以在两个顶点之间通过

Y = Y0 + (Y1 - Y0) (X - X0) / (X1 - X0)

进行线性插值。

水平线的填充稍微复杂一些，因为顶点可能未水平对齐，并且有更多的梯形。