logo标签列表

填充多边形

cgraphicsgeometrydrawingtrigonometry
3
我创建了一个函数，它可以绘制一个有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
    }
}

如何用纯色填充它？ 我不知道如何修改我的代码以便绘制填充图形。

你在使用哪个库进行绘图？那不是标准的C语言。猜测可能是 fill(x,y,color)，但是如果不知道具体使用的库，这只是一个百分之百的猜测。 - John3136
@John3136 不，这完全是标准的C语言，并没有涉及任何库。我正在使用标准、简单、基本、已知的绘图函数进行VGA编程。 - Imobilis
2
@Olaf 增强功能?? 这已经是你第二次出现高度不可能的情况了。无法填充图形是一个需要严肃解决的问题。如果不是正确填充的方法，这个函数将无法按预期工作。这被认为是非工作代码，绝对不适合进行代码审查。 - Imobilis
1
您正在询问如何扩展您的代码以填充创建的多边形。这是一个扩展（“增强”是错误的术语-已确认）。看了一下您过去的帖子，您似乎将其用作教程网站，而不是自己进行一些研究。我会称之为“社交黑客”。（哦，显然，我非常“可靠”）。 - too honest for this site
好的，那么你自己为了找到解决方案已经做了些什么呢？我非常确定你在网上能够找到一个合适的算法（这正是你实际上正在寻找的）。 - too honest for this site
显示剩余6条评论
4个回答
3
有两种不同的方法来实现一个解决方案：
扫描线法
从位于顶部的坐标（最小的y值）开始，逐行向下扫描（增加y），看哪些边与该线相交。
对于凸多边形，找到2个点，(x1,y)和(x2,y)。只需在每条扫描线上画一条连接它们的线。
对于凹多边形，这也可以是2的倍数。只需在每对坐标之间画线。完成一对后，转到下面的2个坐标。这将在该扫描线上创建一个填充/未填充/填充/未填充的模式，从而得出正确的整体解决方案。
如果您有自相交的多边形，您还会找到与某些多边形点相等的坐标，并且您必须将它们过滤掉。之后，您应该处于上述情况之一。
如果在扫描线处理过程中过滤掉了多边形点，请不要忘记也将它们画出来。
泛洪填充法
另一个选择是使用泛洪填充。它需要在每个像素的每一步中执行更多工作来评估边界情况，因此这往往会变成一个较慢的版本。其思想是在多边形内选择一个种子点，并逐像素地向上/向下/向左/向右递归扩展，直到遇到边界为止。
选择种子点 通常情况下，这是通过随机选择一个位于所有角顶点周围边界内的坐标来完成的。无论选择哪个点作为种子点，首先必须检查所选择的点是在多边形内部、外部还是位于多边形的边缘上。可以通过从种子点向“画布的边缘”（或无限远处）追踪一条虚拟线来实现这一点。如果这条虚拟线与多边形的任何边相交的次数总数是奇数，那么该点位于多边形内部。如果追踪的线恰好通过其中一个角顶点，那么计为2次相交，并不会对“变为内部”有贡献（对于凹多边形而言，否则计为1次）。在这种情况下，请尝试选择不同的坐标作为种子点。有时候，根据种子点离最近的边缘/角顶点的距离来评估哪个种子点趋向于具有更高的填充比例是有意义的，特别是如果您的填充算法在特定方向上（例如水平线）更快地填充。通常的方法是从接近边界框中心的点开始。

性能 该算法必须读取和写入多边形的整个表面，并且不会穿过自交点。对于大型表面而言，可能会有相当大的堆栈积累（至少对于简单实现而言），并且边界条件的灵活性减少到基于像素（例如，在绘制在多边形之上的其他内容时填充进间隙）。从这个意义上说，这不是一个数学上正确的解决方案，但对许多应用来说效果很好。

如果多边形存在水平边，您如何处理它们？例如，如果我的多边形是一个矩形，在顶部线上有3条边。 - 0xAA55
好问题。你实际上可以“选择”最合适的方法。一种选择是保留“交叉点”的奇偶方案，并简单地绘制任何斜率为0的边（即水平边）- 另一种选择是在列表中最多只存储给定的交叉点一次，以避免重复出现，这样应该能获得你期望的模式结果。使用一个好的（散列）列表/集合，你不应该看到显著的性能下降。 - StarShine
实际上，只需记住最后存储的交叉点，就只需要一个额外的比较来防止重复出现，无需使用昂贵的集合。 - StarShine
3
常见的填充形状方法是找到多边形边缘与每个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生成器进行了上述测试，并将绘制的线条与多边形进行了比较。似乎正常工作，但使用时需自行承担风险，不提供任何保证。
对于一般形状，请使用您喜欢的搜索引擎搜索“多边形填充”算法。例如，this, this, this 和 this。
它对我也起作用。现在我将测量哪个更快并使用它。此外，是的，水平赋值应该稍微快一些，尽管我总是使用table[yOffset + iterator][xOffset]来访问要在垂直方向上分配的每个像素。这比光栅扫描更快。 - Imobilis
你的方法像我预料的那样更快。 - Imobilis
@Malina：请注意，要将其转换为填充的圆，您可以使用例如 const int x =（int）（0.5 + sqrt（（double）（radius*radius）-（double）（y*y）））; 并省略px，py，nx，ny及其相关代码。这是因为 y（x）= ±sqrt(r*r-x*x) 和 x（y）= ±sqrt(r*r-y*y) 描述了与 x=r*cos(t)，y=r*sin(t) 相同的圆。或者只需循环 x=-radius..radius，y=-radius..radius，并且仅当 x*x+y*y <= radius*radius 时才填充像素 x+center_x，y+center_y。 - Nominal Animal
0

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

由于对称性，顶点垂直对齐，很容易找到极限横坐标（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) 在两个顶点之间进行线性插值即可。

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

@malina：这也是梯形分解。 - user1196549
准确地说，这意味着您的答案更适合作为对他的回答的评论。 - Imobilis
0

无论如何，当我不依赖任何帮助（或尝试）时，似乎我又自己解决了这个问题。

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越高，填充的准确性就越低。

不够健壮，从编码角度来看也不是最好的例子。随着形状在不同比例下重新绘制，算法未能考虑到混叠现象：一个坐标可能落在两个像素之间并被舍入，导致像素被覆盖两次和像素未被覆盖，即会出现空洞。此外，角数和整体“面积”定义了它的性能，而不是屏幕分辨率上实际占用的空间。如果需要绘制许多重叠的实例，则任何分辨率相关的替代方案都将无法胜任。 - StarShine
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接