algorithm - 栅格化椭圆

Question

是否有一种有效的算法可以找到一般椭圆中像素的指标？

本质上，我想要做的是在二维数组中找到对应于跨越可能数组索引的“二维表面”的参数化椭圆的索引。就像我上面的第一个问题一样，这个问题可以比作椭圆的光栅化。

我发现了一些扫描线算法可以满足我对轴对齐椭圆的要求，但现在我想知道是否有任何类似的算法适用于倾斜和旋转的椭圆。必须有，因为那里的矢量图形软件设法填充倾斜和/或旋转的椭圆。

为了阐明我的意思，我最近在这里解决了一个类似的问题:Special polygonial for loop in two dimensional array

/尼克

Answer 1

您可以采用您找到的用于光栅化椭圆的算法，并在测试坐标是在椭圆内部还是外部之前，简单地对坐标应用旋转或倾斜变换。例如，如果你想测试旋转 45 度的椭圆，你可以这样做:

for (x = 0; x < maxX; x++)
{
    for (y = 0; y < maxY; y++)
    {
        double newX, newY;
        Transform (x, y, rotationMatrix, &newX, &newY);
        if (PointInEllipse (newX, newY, ellipse))
        {
            ...do whatever here....
        }
    }
}

其中，Transform 只是将 2x2 旋转矩阵应用于 x 和 y，并将结果放入 newX、newY。