从矩形绘制椭圆

你不能得到矩形的宽度和高度(除以2)和中心,然后把它作为它的长轴、短轴和中心插入任何椭圆绘制程序中吗?我想我一路都没看到问题。

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

这可以通过在绘制每个像素时为象限使用不同的中间点很容易做到:

drawPixel(midx_high+x,midy_high+y);
DrawPixel(midx_low-x,midy_high+y);
DrawPixel(midx_高+x,midy_低-y);
DrawPixel(中低-X,中低-Y);
< /代码> 

高值是天花板中点,低值是地板中点。


要演示的图像,宽度为15和16的椭圆:


等长尺寸,重复中间像素。


这可以通过在绘制每个像素时为象限使用不同的中间点轻松实现:

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

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

我的解决方案基于mcilroy Ellipse Algorithm mcilroy Ellipse Algorithm ,这是一种仅整数的算法,Mcilroy在数学上证明该算法精确到半像素,没有丢失或额外的点,并且正确地绘制退化情况,如线和圆。 l.patrick 进一步分析了McIlroy的算法,包括优化它的方法以及如何将填充的椭圆分解成矩形。

McIlroy的算法通过椭圆的一个象限跟踪路径;其余象限通过对称进行渲染。路径中的每个步骤都需要进行三次比较。许多其他的椭圆算法使用的是八分法,每一步只需要两个比较。然而,基于八分之一的方法在八分之一的边界上是众所周知的不准确。一次比较的轻微节省不值得八分法的不准确。

就像几乎所有其他的整数椭圆算法一样,McIlroy希望在整数坐标处的中心和轴的长度也为整数。但是,我们希望能够使用任何整数坐标绘制带有边界框的椭圆。具有均匀宽度或均匀高度的边界框将在一个整数和半坐标上有一个中心,并且 a 或 b 将是一个整数和-a-half.

我的解决方案是使用需要的整数进行计算。从 q开始的任何变量都是从双像素值计算得出的。偶数 q variable位于整数坐标上,奇数 q variable位于整数和半坐标处。然后,我重新计算了McIroy的数学公式,得到了正确的数学表达式和这些新的双值。这包括在边界框的宽度或高度相等时修改起始值。

注意,子程序/方法 drawEllipse given below.您为它提供边界框的整数坐标( x0>, y0 )和( x1 , y1 )。它不关心是否需要交换它们。如果您提供 x0->code>= x1->code>,您将得到一条垂直线。同样适用于 y0 和 y1 坐标。还提供布尔值 fill parameter,如果为false,则仅绘制椭圆轮廓;如果为true,则绘制填充椭圆。您还必须提供子例程 drawpoint(x,y) which drawings a single point and drawrow(xleft,xright,y) which drawings a horizontal line from xleft to xright inclusively.

McIlroy和Patrick优化了他们的代码以折叠常量、重用公共子表达式等。为了清晰起见,我没有这样做。不管怎样,大多数编译器今天都会自动执行此操作。

void drawEllipse(int x0,int y0,int x1,int y1,boolean fill)
{
国际XB、YB、XC、YC;


//计算高度
Yb=yc=(y0+y1)/2;
int qb=(y0<y1)?(y1-y0):(y0-y1);
INQY=QB;
int dy=qb/2;
如果(QB % 2!= 0)
//边界框具有均匀的像素高度
YC++;

//计算宽度
xb=xc=(x0+x1)/2;
int qa=(x0<x1)?(x1-x0):(x0-x1);
int qx=质量保证%2;
int dx=0;
长qt=(长)qa*qa+(长)qb*qb-2l*qa*qa*qb;
如果(QX)!= 0){
//边界框具有偶数像素宽度
XC++;
QT+= 3L*QB*QB;
}

//从(dx,dy)=(0,b)开始,迭代到(a,0)
而(qy>=0&qx<=qa){
//绘制新点
如果(!)填充)
牵引点(XB Dx,YB Dy);
如果(DX)!= 0×xb!= xc){
牵引点(xc+dx,yb dy);
如果(DY)!0=yb!= YC)
牵引点(xc+dx,yc+dy);
}
如果(DY)!0=yb!= YC)
牵引点(xb dx,yc+dy);
}

//如果一个(+1,0)步骤保持在椭圆内,则执行该操作
如果(qt+2l*qb*qb*qx+3l*qb*qb<=0l||
qt+2l*qa*qa*qy-(长)qa*qa<=0l){
qt+=8L*qb*qb+4L*qb*qb*qx;
DX++;
qx+=2;
//如果(0,-1)步保持在椭圆之外,则执行该操作
}否则,如果(qt-2l*qa*qa*qy+3l*qa*qa>0l){
如果(填充){
抽屉(xb dx,xc+dx,yc+dy);
如果(DY)!0=yb!= YC)
抽屉(xb-dx,xc+dx,yb-dy);
}
qt+=8L*qa*qa-4L*qa*qa*qy;
DY-;
QY-=2;
//其他步骤(+1,-1)
}否则{
如果(填充){
抽屉(xb dx,xc+dx,yc+dy);
如果(DY)!0=yb!= YC)
抽屉(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;
}
}//while循环结束
返回;
}
< /代码> 

上图显示了10x10大小的所有边界框的输出。我还运行了100x100大小的所有椭圆的算法。这在第一象限中产生了384614点。计算了这些点的绘制位置和实际椭圆位置之间的误差。最大误差为0.500000(半像素),所有点之间的平均误差为0.216597。



我的解决方案基于McIlroy ellipse algorithm,这是一种仅整数的算法,McIlroy在数学上证明它精确到半像素,没有遗漏或额外的点,并且能够正确地绘制退化情况,如直线和圆。L. Patrick进一步分析了McIlroy的算法,包括优化算法的方法,以及如何将填充椭圆分解为矩形。

McIlroy的算法通过椭圆的一个象限跟踪路径;其余象限通过对称进行渲染。路径中的每个步骤都需要进行三次比较。许多其他的椭圆算法使用的是八分法,每一步只需要两个比较。然而,基于八分之一的方法在八分之一的边界上是众所周知的不准确。一个比较的微小节省不值得八分法的不准确。

就像其他整数椭圆算法一样,McIlroy希望中心在整数坐标和轴的长度a和b也是整数。但是,我们希望能够使用任何整数坐标绘制带有边界框的椭圆。具有均匀宽度或均匀高度的边界框将在一个整数和半坐标上有一个中心,以及一或乙将是一个整数半。

我的解决方案是使用双重的需要什么。以开头的任何变量q从双像素值计算。偶数Q变量在整数坐标上,奇数Q变量的坐标为整数和半。然后,我重新计算了McIroy的数学公式,得到了正确的数学表达式和这些新的双值。这包括在边界框的宽度或高度相等时修改起始值。

看,子程序/方法drawEllipse下面给出的。提供整数坐标(x0,y0)和(x1,y1)边界框的。它不在乎X0&;X1对战X0gt;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。