从矩形绘制椭圆

Question

我一直在网上寻找一种方法，可以从矩形坐标（即左上角（x，y）和大小（宽度和高度））绘制一个椭圆。到处都是基于Midpoint / Bresenham算法的方法，但我不能使用这些算法，因为在使用整数像素时，会因为这些算法使用中心点和半径而失去精度。

椭圆必须限制在矩形坐标内。因此，如果我提供一个宽度和高度均为4（或任何偶数）的矩形，则应该获得完全适合4x4矩形的椭圆，而不是5x5的椭圆(与那些算法给我的结果相反)。

有没有人知道如何完成这个任务呢？

谢谢！

- Alex Turpin

---

只是为了明确，给定一个边界框，您想要由该框限定的最大椭圆？ - John Feminella

Answer 1

您可以获取矩形的宽度和高度（除以2），并将其作为椭圆绘制例程的长轴、短轴和中心进行插入吗？我想我没有完全看到问题所在。

- Michael Dorgan

---

不行，因为对于宽高均为偶数的椭圆，其宽度和高度会比原始值增加一个像素，因为它在中心+轴和中心-轴处绘制像素。我需要它完全在范围内，我的“像素”大小为32x32，因此这非常明显。 - Alex Turpin

所以问题在于亚像素精度，而关于象限的反射会导致某些边缘上的覆盖。鉴于此，您应该能够存储非整数宽度高度（或至少具有1位小数的定点值）来处理这个问题。然后问题就是找到或编写一个适用于非整数宽度和高度的椭圆生成器。这应该不难找到，但我还没有找过，也许不是？ - Michael Dorgan

Answer 2

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

我基于麦克罗伊椭圆算法提出了解决方案，这是一种仅使用整数的算法。麦克罗伊在数学上证明了该算法精度可达半个像素，没有遗漏或多余的点，并且可以正确绘制退化情况，如直线和圆等。L. Patrick进一步分析了麦克罗伊的算法，包括优化方法以及如何将填充椭圆分解为矩形。

麦克罗伊的算法通过椭圆的一个象限追踪路径；其余象限通过对称性渲染。路径中的每一步需要三个比较。许多其他椭圆算法使用八分之一象限，每步只需要两个比较。然而，基于八分之一象限的方法在八分之一象限边界处的准确性极差。一次比较的微小节省并不值得使用八分之一象限方法的不准确性。

几乎所有整数椭圆算法都要求椭圆的中心坐标为整数，并且轴长a和b也必须是整数。然而，我们希望能够使用任意整数坐标绘制一个带有边界框的椭圆。当边界框的宽度或高度为偶数时，其中心将位于一个整数半坐标上，而a或b将是一个整数半加一。

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

以下是子程序/方法drawEllipse。您需要提供边界框的整数坐标(x0, y0)和(x1, y1)。它不关心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。

- DrSheldon

---

如果任何人在填充变量上得到奇怪的结果，您可能需要检查您的drawRow参数。如果您的水平线绘制函数中的第三个参数是线的长度，则需要将以下内容作为第三个参数的值提供：dx * 2 + (even_pixel_width ? 2 : 1)。最后，在函数开头创建一个bool even_pixel_width，初始化为false，然后在if(qx！=0)下添加even_pixel_width=true。 - deLock

@deLock：不需要这些。drawRow的第三个参数是行的y坐标，而不是它的宽度。甚至像素宽度的调整已经在代码中了；没有必要为此创建布尔标志。 - DrSheldon

DrSheldon，请仔细阅读我的评论。你错过了这一部分：“如果你的horizontal-line-draw函数的第三个参数是线条的长度”。在这种情况下，你的代码将无法正常工作。drawRow的形式参数在你的帖子中没有定义。我已经实际验证了以上所有内容，所以不用担心。 - deLock

顺便说一句，有点令人惊讶的是，我不得不在宽度上添加（even_pixel_width ? 2 : 1）个像素，以使填充和未填充的代码呈现相同的椭圆实际宽度。只是为了再次确认 - 当调用者指定偶数宽度与奇数宽度时，您是否比较了填充与未填充的渲染椭圆的宽度？您可能会发现与我一样的差异-填充的比未填充的窄1个像素。 - deLock

Answer 3

我找到的解决方法是绘制最接近的奇数尺寸较小椭圆，但在偶数长度维度上拉开一个像素，并重复中间像素。

当绘制每个像素时，可以通过使用不同的象限中点轻松完成此操作：

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的椭圆：

- Danik