填充三角形算法

Question

我目前正在尝试完成填充绘制三角形的算法。我一直这样做的方式是遍历形状并绘制单线。我有一个几乎完美的算法，除了一个小问题。当我有水平边时，填充失败。

这是我目前的填充算法。我应该注意到，称为 origin、coor2 和 coor3 的多维数组表示为我的三角形的顶点（origin[0][0] = x of origin，origin[0][1]= y of origin）。坐标是典型的 window，(0,0) 位于左上角。此外，gc 只是我需要在 window.

中绘制的内容

void triangle::drawFilled(GraphicsContext* gc)
{
// color
gc->setColor(colorRGB);
// algorithm variables
double ax = origin[0][0];
double bx = coor2[0][0];
double cx = coor3[0][0];
double ay = origin[1][0];
double by = coor2[1][0];
double cy = coor3[1][0];

// sort vertices by y
if (ay > by)
{
    std::swap(ay, by);
    std::swap(ax, bx);
}
if (ay > cy)
{
    std::swap(ay, cy);
    std::swap(ax, cx);
}
if (by > cy)
{
    std::swap(by, cy);
    std::swap(bx, cx);
}

// define more algorithm variables
double dx1 = (cx-ax)/(cy-ay);
double dx2 = (bx-ax)/(by-ay);
double dx3 = (cx-bx)/(cy-by);
double x1 = ax;
double x2 = ax;

// loop through coordinates
for(int y = ay; y < by; y++)
{
    gc->drawLine(x1,y,x2,y);
    x1 += dx1;
    x2 += dx2;
}

// loop through coordinates
for(int y = by; y < cy; y++)
{
    gc->drawLine(x1,y,x2,y);
    x1 += dx1;
    x2 += dx3;
}
}

Here's an example of my results when there are not horizontal sides

And here's when there is a horizontal side

请注意轮廓和填充如何不对齐。

我意识到问题可能出在 y 顶点的排序上，因此没有考虑 x。我可以强行使用我的方法来处理水平和垂直边缘的所有情况，但这似乎效率很低。我宁愿学习如何解决我的困境，也不愿尝试解决它。

Answer 1

问题是您的代码取决于第一个循环设置 x2 到 bx 的副作用。当 dx2 是无穷大时无论如何都行不通，甚至不尝试。

所以在第一个循环之后，只需设置 x2=bx;

大多数时候，额外的步骤是多余的，但它是微不足道的，当顶面是水平的时候，这是必要的。

填充三角形算法

Filling a Triangle Algorithm

c++

algorithm

graphics

2d

c++11