当前位置：文江博客话题详情

从矩形绘制椭圆

发布于 2024-09-03 01:35:58 字数 270 浏览 2 评论 0原文

我一直在网上寻找一种从矩形坐标（即左上角（x，y）和大小（宽度和高度））绘制椭圆的方法。我到处都能找到的唯一算法是基于中点/布雷森汉姆算法，但我无法使用它，因为在处理整数像素时，我会失去精度，因为这些算法使用中心点和径向线。

椭圆必须限于矩形的坐标，因此，如果我向其提供一个宽度和高度为 4（或任何偶数）的矩形，我应该得到一个完全适合 4x4 矩形的椭圆，而不是一个完全适合 4x4 矩形的椭圆。 5x5（就像那些算法给我的结果）。

有谁知道有什么方法可以实现这一目标？

谢谢！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

肤浅与狂妄 2024-09-10 01:35:58

您能否获取矩形的宽度和高度（除以 2）和中心，然后将其插入任何椭圆绘图例程作为其长轴、短轴和中心？我想我在这里并没有看到问题所在。

回复收藏 0 原文

﹂绝世的画 2024-09-10 01:35:58

我有同样的需要。这是我的解决方案和代码。误差最多为半个像素。

我的解决方案基于 McIlroy 椭圆算法< /a>，一种纯整数算法，麦克罗伊在数学上证明其精确到半像素，没有丢失或多余的点，并且可以正确绘制直线和圆等简并情况。 L. Patrick 进一步分析了 McIlroy 的算法，包括优化算法的方法以及如何将填充的椭圆分解为矩形。

麦克罗伊的算法追踪一条穿过椭圆象限的路径；其余象限通过对称性呈现。路径中的每个步骤都需要进行三次比较。许多其他椭圆算法使用八分圆，每步只需要进行两次比较。然而，基于八分圆的方法在八分圆边界上是出了名的不准确。一次比较所节省的一点点代价并不值得八分圆法的不准确性。

与几乎所有其他整数椭圆算法一样，McIlroy 希望中心位于整数坐标，并且轴 a 和 b 的长度为整数，如下所示出色地。但是，我们希望能够使用任何整数坐标绘制带有边界框的椭圆。具有偶数宽度或偶数高度的边界框将在整数半坐标上具有中心，并且 a 或 b 将是整数和-半。

我的解决方案是使用所需整数的双整数来执行计算。任何以 q 开头的变量都是根据双像素值计算的。偶数 q 变量位于整数坐标上，奇数 q 变量位于整数半坐标上。然后我重新计算了 McIroy 的数学，用这些新的双倍值得到正确的数学表达式。这包括当边界框具有均匀宽度或高度时修改起始值。

看哪，下面给出了子例程/方法drawEllipse。您为其提供边界框的整数坐标 (x0,y0) 和 (x1,y1) 。它不关心 x0 是否 x0 x0 x0 x0 < x1 与 x0 > x1；它会根据需要交换它们。如果您提供 x0 == x1，您将得到一条垂直线。对于 y0 和 y1 坐标也是如此。您还提供布尔值 fill 参数，如果为 false，则仅绘制椭圆轮廓；如果为 true，则绘制填充的椭圆。您还必须提供绘制单个点的子例程 drawPoint(x, y) 和从 绘制水平线的 drawRow(xleft, xright, y) xleft 到 xright（包含在内）。

McIlroy 和 Patrick 优化了他们的代码以折叠常量、重用公共子表达式等。为了清楚起见，我没有这样做。无论如何，现在大多数编译器都会自动执行此操作。

void drawEllipse(int x0, int y0, int x1, int y1, boolean fill)
{
    int xb, yb, xc, yc;


    // Calculate height
    yb = yc = (y0 + y1) / 2;
    int qb = (y0 < y1) ? (y1 - y0) : (y0 - y1);
    int qy = qb;
    int dy = qb / 2;
    if (qb % 2 != 0)
        // Bounding box has even pixel height
        yc++;

    // Calculate width
    xb = xc = (x0 + x1) / 2;
    int qa = (x0 < x1) ? (x1 - x0) : (x0 - x1);
    int qx = qa % 2;
    int dx = 0;
    long qt = (long)qa*qa + (long)qb*qb -2L*qa*qa*qb;
    if (qx != 0) {
        // Bounding box has even pixel width
        xc++;
        qt += 3L*qb*qb;
    }

    // Start at (dx, dy) = (0, b) and iterate until (a, 0) is reached
    while (qy >= 0 && qx <= qa) {
        // Draw the new points
        if (!fill) {
        drawPoint(xb-dx, yb-dy);
        if (dx != 0 || xb != xc) {
            drawPoint(xc+dx, yb-dy);
            if (dy != 0 || yb != yc)
            drawPoint(xc+dx, yc+dy);
        }
        if (dy != 0 || yb != yc)
            drawPoint(xb-dx, yc+dy);
        }

        // If a (+1, 0) step stays inside the ellipse, do it
        if (qt + 2L*qb*qb*qx + 3L*qb*qb <= 0L || 
            qt + 2L*qa*qa*qy - (long)qa*qa <= 0L) {
            qt += 8L*qb*qb + 4L*qb*qb*qx;
            dx++;
            qx += 2;
        // If a (0, -1) step stays outside the ellipse, do it
        } else if (qt - 2L*qa*qa*qy + 3L*qa*qa > 0L) {
            if (fill) {
                drawRow(xb-dx, xc+dx, yc+dy);
                if (dy != 0 || yb != yc)
                    drawRow(xb-dx, xc+dx, yb-dy);
            }
            qt += 8L*qa*qa - 4L*qa*qa*qy;
            dy--;
            qy -= 2;
        // Else step (+1, -1)
        } else {
            if (fill) {
                drawRow(xb-dx, xc+dx, yc+dy);
                if (dy != 0 || yb != yc)
                    drawRow(xb-dx, xc+dx, yb-dy);
            }
            qt += 8L*qb*qb + 4L*qb*qb*qx + 8L*qa*qa - 4L*qa*qa*qy;
            dx++;
            qx += 2;
            dy--;
            qy -= 2;
        }
    }   // End of while loop
    return;
}

上图显示了尺寸最大为 10x10 的所有边界框的输出。我还对尺寸最大为 100x100 的所有椭圆运行了该算法。这在第一象限产生了 384614 点。计算绘制每个点的位置与实际椭圆出现的位置之间的误差。最大误差为 0.500000（半个像素），所有点的平均误差为 0.216597。

I had the same need. Here is my solution with code. The error is at most half a pixel.

I based my solution on the McIlroy ellipse algorithm, an integer-only algorithm which McIlroy mathematically proved to be accurate to a half-pixel, without missing or extra points, and correctly drawing degenerate cases such as lines and circles. L. Patrick further analyzed McIlroy's algorithm, including ways to optimize it and how a filled ellipse can be broken up into rectangles.

McIlroy's algorithm traces a path through one quadrant of the ellipse; the remaining quadrants are rendered through symmetry. Each step in the path requires three comparisons. Many of the other ellipse algorithms use octants instead, which require only two comparisons per step. However, octant-based methods have are notoriously inaccurate at the octant boundaries. The slight savings of one comparison is not worth the inaccuracy of the octant methods.

Like virtually every other integer ellipse algorithm, McIlroy's wants the center at integer coordinates, and the lengths of the axes a and b to be integers as well. However, we want to be able to draw an ellipse with a bounding box using any integer coordinates. A bounding box with an even width or even height will have a center on an integer-and-a-half coordinate, and a or b will be an integer-and-a-half.

My solution was to perform calculations using integers that are double of what is needed. Any variable starting with q is calculated from double pixel values. An even q variable is on an integer coordinate, and an odd q variable is at an integer-and-a-half coordinate. I then re-worked McIroy's math to get the correct mathematical expressions with these new doubled values. This includes modifying starting values when the bounding box has even width or height.

Behold, the subroutine/method drawEllipse given below. You provide it with the integer coordinates (x0,y0) and (x1,y1) of the bounding box. It doesn't care if x0 < x1 versus x0 > x1; it will swap them as needed. If you provide x0 == x1, your will get a vertical line. Similarly for the y0 and y1 coordinates. You also provide the boolean fill parameter, which draws only the ellipse outline if false, and draws a filled ellipse if true. You also have to provide the subroutines drawPoint(x, y) which draws a single point and drawRow(xleft, xright, y) which draws a horizontal line from xleft to xright inclusively.

McIlroy and Patrick optimize their code to fold constants, reuse common subexpressions, etc. For clarity, I didn't do that. Most compilers do this automatically today anyway.

void drawEllipse(int x0, int y0, int x1, int y1, boolean fill)
{
    int xb, yb, xc, yc;


    // Calculate height
    yb = yc = (y0 + y1) / 2;
    int qb = (y0 < y1) ? (y1 - y0) : (y0 - y1);
    int qy = qb;
    int dy = qb / 2;
    if (qb % 2 != 0)
        // Bounding box has even pixel height
        yc++;

    // Calculate width
    xb = xc = (x0 + x1) / 2;
    int qa = (x0 < x1) ? (x1 - x0) : (x0 - x1);
    int qx = qa % 2;
    int dx = 0;
    long qt = (long)qa*qa + (long)qb*qb -2L*qa*qa*qb;
    if (qx != 0) {
        // Bounding box has even pixel width
        xc++;
        qt += 3L*qb*qb;
    }

    // Start at (dx, dy) = (0, b) and iterate until (a, 0) is reached
    while (qy >= 0 && qx <= qa) {
        // Draw the new points
        if (!fill) {
        drawPoint(xb-dx, yb-dy);
        if (dx != 0 || xb != xc) {
            drawPoint(xc+dx, yb-dy);
            if (dy != 0 || yb != yc)
            drawPoint(xc+dx, yc+dy);
        }
        if (dy != 0 || yb != yc)
            drawPoint(xb-dx, yc+dy);
        }

        // If a (+1, 0) step stays inside the ellipse, do it
        if (qt + 2L*qb*qb*qx + 3L*qb*qb <= 0L || 
            qt + 2L*qa*qa*qy - (long)qa*qa <= 0L) {
            qt += 8L*qb*qb + 4L*qb*qb*qx;
            dx++;
            qx += 2;
        // If a (0, -1) step stays outside the ellipse, do it
        } else if (qt - 2L*qa*qa*qy + 3L*qa*qa > 0L) {
            if (fill) {
                drawRow(xb-dx, xc+dx, yc+dy);
                if (dy != 0 || yb != yc)
                    drawRow(xb-dx, xc+dx, yb-dy);
            }
            qt += 8L*qa*qa - 4L*qa*qa*qy;
            dy--;
            qy -= 2;
        // Else step (+1, -1)
        } else {
            if (fill) {
                drawRow(xb-dx, xc+dx, yc+dy);
                if (dy != 0 || yb != yc)
                    drawRow(xb-dx, xc+dx, yb-dy);
            }
            qt += 8L*qb*qb + 4L*qb*qb*qx + 8L*qa*qa - 4L*qa*qa*qy;
            dx++;
            qx += 2;
            dy--;
            qy -= 2;
        }
    }   // End of while loop
    return;
}

The image above shows the output for all bounding boxes up to size 10x10. I also ran the algorithm for all ellipses up to size 100x100. This produced 384614 points in the first quadrant. The error between where each of these points were plotted and where the actual ellipse occurs was calculated. The maximum error was 0.500000 (half a pixel) and the average error among all of the points was 0.216597.

回复收藏 0 原文

笑叹一世浮沉 2024-09-10 01:35:58

我发现这个问题的解决方案是绘制最接近的奇数尺寸的较小椭圆，但沿偶数长度尺寸被像素拉开，重复中间像素。

这可以通过在绘制每个像素时使用不同的象限中点来轻松完成：

DrawPixel(midX_high + x, midY_high + y);
DrawPixel(midX_low  - x, midY_high + y);
DrawPixel(midX_high + x, midY_low  - y);
DrawPixel(midX_low  - x, midY_low  - y);

高值是上限中点，低值是下限中点。

用于说明的图像，宽度为 15 和 16 的椭圆：

The solution I found to this problem was to draw the closest smaller ellipse with odd dimensions, but pulled apart by a pixel along the even length dimension, repeating the middle pixels.

This can be done easily by using different middle points for the quadrants when plotting each pixel:

DrawPixel(midX_high + x, midY_high + y);
DrawPixel(midX_low  - x, midY_high + y);
DrawPixel(midX_high + x, midY_low  - y);
DrawPixel(midX_low  - x, midY_low  - y);

The high values are the ceil'ed midpoint, and the low values are the floored midpoint.

An image to illustrate, ellipses with width 15 and 16: