计算和存储像素化椭圆

Question

我想知道是否可以创建一个输入宽度和高度的函数（任意语言）。

然后此函数将计算适合给定尺寸的最大椭圆，并将其存储在矩阵中，例如这两个示例；

左边的例子，宽为14，高为27，白色部分为椭圆。

右边的例子，宽是38，高是21，白色部分还是椭圆。

当然，黑色和白色部分是不是椭圆都可以看作true/false值

Answer 1

是的，这是可能的。该过程称为椭圆光栅化。这里有几种方法：

让我们的图像具有 xs,ys 分辨率，因此中心 (x0,y0) 和半轴 a,b 是：

x0=xs/2
y0=y2/2
a =x0-1
b =y0-1

使用椭圆方程

所以 2 个嵌套 for 循环 + if 决定你是在椭圆内还是在椭圆外的条件。
```
for (y=0;y<ys;y++)
 for (x=0;x<xs;x++)
  if (((x-x0)*(x-x0)/(a*a))+((y-y0)*(y-y0)/(b*b))<=1.0) pixel[y][x]=color_inside;
   else pixel[y][x]=color_outside;
```
你可以通过 pre-computing 等式的部分进行很多优化，只有当你改变时，一些方程在每个 x 迭代中只计算一次，其余的在每个 [=19] 中计算一次=] 迭代。还有乘法比除法好。
使用参数椭圆方程
```
x(t) = x0 + a*cos(t)
y(t) = y0 + b*sin(t)
t = <0,2.0*M_PI>  // for whole ellipse
```
所以一个 for 循环仅使用水平线或垂直线为象限的 3 个镜子创建象限坐标和内外填充线。但是这种方法需要一个缓冲区来存储一个象限的圆周点。
使用Bresenham椭圆算法
使用任何圆形算法并拉伸为椭圆

因此只需使用 xs,ys 渲染圆圈中较小分辨率的正方形区域，然后再拉伸回 xs,ys。如果您在光栅化过程中不进行拉伸，那么您可能会创建伪像。在这种情况下，最好使用更大的分辨率并向下拉伸，但这样会较慢。

Answer 2

绘制椭圆并将其存储在矩阵中可以使用两种不同的方法来完成：栅格化（推荐方式）或pixel-by-pixel渲染。根据@Spektre 的评论，我想知道这两种方法是否都称为“光栅化”，因为它们都将椭圆渲染为光栅图像。不管怎样，我将解释如何在 C++ 中使用这两种方法来绘制椭圆并将其存储在矩阵中。

注意： 这里我假设矩阵的原点 matrix[0][0] 指的是图像的 upper-left 角。所以矩阵上的点由 x- 和 y-coordinate 对描述，这样 x-coordinates 向右增加； y-coordinates 从上到下递增。

Pixel-by-pixel椭圆渲染

使用此方法，您可以遍历矩阵中的所有像素以确定每个像素是在椭圆内部还是外部。如果像素在内部，则将其设为白色，否则将其设为黑色。

在下面的示例代码中，isPointOnEllipse 函数确定点相对于椭圆的状态。它以点的坐标、椭圆中心的坐标以及semi-major和semi-minor轴的长度为参数。然后 returns 值 PS_OUTSIDE、PS_ONPERIM 或 PS_INSIDE 之一，表示该点位于椭圆之外，该点正好位于椭圆的周长上, 或者该点分别位于椭圆内部。

显然，如果点状态是PS_ONPERIM，那么点也是椭圆的一部分，必须做成白色；因为除了内部区域之外，椭圆的轮廓还必须着色。

你必须调用ellipseInMatrixPBP函数来绘制一个椭圆，传递给它一个指向你的矩阵的指针，以及你的矩阵的宽度和高度。这个函数循环遍历矩阵中的每个像素，然后为每个像素调用 isPointOnEllipse 以查看它是在椭圆内部还是外部。最后，它相应地修改像素。

#include <math.h>

// Indicates the point lies outside of the ellipse.
#define PS_OUTSIDE  (0)
// Indicates the point lies exactly on the perimeter of the ellipse.
#define PS_ONPERIM  (1)
// Indicates the point lies inside of the ellipse.
#define PS_INSIDE   (2)

short isPointOnEllipse(int cx, int cy, int rx, int ry, int x, int y)
{
    double m = (x - cx) * ((double) ry) / ((double) rx);
    double n = y - cy;
    double h = sqrt(m * m + n * n);

    if (h == ry)
        return PS_ONPERIM;
    else if (h < ry)
        return PS_INSIDE;
    else
        return PS_OUTSIDE;
}

void ellipseInMatrixPBP(bool **matrix, int width, int height)
{
    // So the ellipse shall be stretched to the whole matrix
    // with a one-pixel margin.
    int cx = width / 2;
    int cy = height / 2;
    int rx = cx - 1;
    int ry = cy - 1;

    int x, y;
    short pointStatus;
    // Loop through all the pixels in the matrix.
    for (x = 0;x < width;x++)
    {
        for (y = 0;y < height;y++)
        {
            pointStatus = isPointOnEllipse(cx, cy, rx, ry, x, y);
            // If the current pixel is outside of the ellipse,
            // make it black (false).
            // Else if the pixel is inside of the ellipse or on its perimeter,
            // make it white (true).
            if (pointStatus == PS_OUTSIDE)
                matrix[x][y] = false;
            else
                matrix[x][y] = true;
        }
    }
}

椭圆光栅化

如果pixel-by-pixel渲染方法太慢，则使用光栅化方法。在这里，您确定椭圆影响矩阵中的哪些像素，然后修改这些像素（例如，将它们变成白色）。与 pixel-by-pixel 渲染不同，光栅化不必通过椭圆形外部的像素，这就是为什么这种方法如此快。

要栅格化椭圆，建议您使用so-called Mid-point Ellipse algorithm，它是Bresenham 圆算法的扩展形式。

但是，我发现了一个 ellipse-drawing 算法，它可能 足够复杂 （除了它的性能）可以与 Bresenham 的算法竞争！所以我会 post 你想要的函数 - 用 C++ 编写。

下面的代码定义了一个名为 ellipseInMatrix 的函数，它用 one-pixel 笔划绘制一个椭圆，但不填充该椭圆。您需要向此函数传递一个指向矩阵的指针，该矩阵已分配 初始化为 false 值，加上矩阵的维度作为整数。请注意 ellipseInMatrix 在内部调用 rasterizeEllipse 函数执行主要的光栅化操作。每当此函数找到椭圆的一个点时，它会将矩阵中的相应像素设置为 true，从而使该像素变为白色。

#define pi (2 * acos(0.0))
#define coord_nil (-1)

struct point
{
    int x;
    int y;
};

double getEllipsePerimeter(int rx, int ry)
{
    return pi * sqrt(2 * (rx * rx + ry * ry));
}

void getPointOnEllipse(int cx, int cy, int rx, int ry, double d, struct point *pp)
{
    double theta = d * sqrt(2.0 / (rx * rx + ry * ry));
    // double theta = 2 * pi * d / getEllipsePerimeter(rx, ry);

    pp->x = (int) floor(cx + cos(theta) * rx);
    pp->y = (int) floor(cy - sin(theta) * ry);
}

void rasterizeEllipse(bool **matrix, int cx, int cy, int rx, int ry)
{
    struct point currentPoint, midPoint;
    struct point previousPoint = {coord_nil, coord_nil};
    double perimeter = floor(getEllipsePerimeter(rx, ry));
    double i;
    
    // Loop over the perimeter of the ellipse to determine all points on the ellipse path.
    for (i = 0.0;i < perimeter;i++)
    {
        // Find the current point and determine its coordinates.
        getPointOnEllipse(cx, cy, rx, ry, i, &currentPoint);
        // So color the current point.
        matrix[currentPoint.x][currentPoint.y] = true;

        // So check if the previous point exists. Please note that if the current
        // point is the first point (i = 0), then there will be no previous point.
        if (previousPoint.x != coord_nil)
        {
            // Now check if there is a gap between the current point and the previous
            // point. We know it's not OK to have gaps along the ellipse path!
            if (!((currentPoint.x - 1 <= previousPoint.x) && (previousPoint.x <= currentPoint.x + 1) && 
            (currentPoint.y - 1 <= previousPoint.y) && (previousPoint.y <= currentPoint.y + 1)))
            {
                // Find the missing point by defining its offset as a fraction
                // between the current point offset and the previous point offset.
                getPointOnEllipse(cx, cy, rx, ry, i - 0.5, &midPoint);
                matrix[midPoint.x][midPoint.y] = true;
            }
        }

        previousPoint.x = currentPoint.x;
        previousPoint.y = currentPoint.y;
    }
}

void ellipseInMatrix(bool **matrix, int width, int height)
{
    // So the ellipse shall be stretched to the whole matrix
    // with a one-pixel margin.
    int cx = width / 2;
    int cy = height / 2;
    int rx = cx - 1;
    int ry = cy - 1;

    // Call the general-purpose ellipse rasterizing function.
    rasterizeEllipse(matrix, cx, cy, rx, ry);
}

如果您需要像您提供的示例一样用白色像素填充椭圆，则可以使用以下代码来栅格化填充的椭圆。使用与上一个函数类似的语法调用 filledEllipseInMatrix 函数。

#define pi (2 * acos(0.0))
#define coord_nil (-1)

struct point
{
    int x;
    int y;
};

double getEllipsePerimeter(int rx, int ry)
{
    return pi * sqrt(2 * (rx * rx + ry * ry));
}

void getPointOnEllipse(int cx, int cy, int rx, int ry, double d, struct point *pp)
{
    double theta = d * sqrt(2.0 / (rx * rx + ry * ry));
    // double theta = 2 * pi * d / getEllipsePerimeter(rx, ry);

    pp->x = (int) floor(cx + cos(theta) * rx);
    pp->y = (int) floor(cy - sin(theta) * ry);
}

void fillBar(struct point seed, bool **matrix, int cx)
{
    int bx;
    if (seed.x > cx)
    {
        for (bx = seed.x;bx >= cx;bx--)
            matrix[bx][seed.y] = true;
    }
    else
    {
        for (bx = seed.x;bx <= cx;bx++)
            matrix[bx][seed.y] = true;
    }
}

void rasterizeFilledEllipse(bool **matrix, int cx, int cy, int rx, int ry)
{
    struct point currentPoint, midPoint;
    struct point previousPoint = {coord_nil, coord_nil};
    double perimeter = floor(getEllipsePerimeter(rx, ry));
    double i;
    
    // Loop over the perimeter of the ellipse to determine all points on the ellipse path.
    for (i = 0.0;i < perimeter;i++)
    {
        // Find the current point and determine its coordinates.
        getPointOnEllipse(cx, cy, rx, ry, i, &currentPoint);
        // So fill the bar (horizontal line) that leads from
        // the current point to the minor axis.
        fillBar(currentPoint, matrix, cx);

        // So check if the previous point exists. Please note that if the current
        // point is the first point (i = 0), then there will be no previous point.
        if (previousPoint.x != coord_nil)
        {
            // Now check if there is a gap between the current point and the previous
            // point. We know it's not OK to have gaps along the ellipse path!
            if (!((currentPoint.x - 1 <= previousPoint.x) && (previousPoint.x <= currentPoint.x + 1) && 
            (currentPoint.y - 1 <= previousPoint.y) && (previousPoint.y <= currentPoint.y + 1)))
            {
                // Find the missing point by defining its offset as a fraction
                // between the current point offset and the previous point offset.
                getPointOnEllipse(cx, cy, rx, ry, i - 0.5, &midPoint);
                fillBar(midPoint, matrix, cx);
            }
        }

        previousPoint.x = currentPoint.x;
        previousPoint.y = currentPoint.y;
    }
}

void filledEllipseInMatrix(bool **matrix, int width, int height)
{
    // So the ellipse shall be stretched to the whole matrix
    // with a one-pixel margin.
    int cx = width / 2;
    int cy = height / 2;
    int rx = cx - 1;
    int ry = cy - 1;

    // Call the general-purpose ellipse rasterizing function.
    rasterizeFilledEllipse(matrix, cx, cy, rx, ry);
}

计算和存储像素化椭圆

Calculating and storing pixelated ellipse

matrix

graphics

render

ellipse

Pixel-by-pixel椭圆渲染

椭圆光栅化