椭圆中点算法

2023-12-29 11:30:57

原理

椭圆的扫描转换与圆的扫描转换有相似之处,但也有不同,主要区别是椭圆弧上存在改变主位移方向的临界点。瞬时针绘制四分椭圆弧的中点算法,根据对称性可以绘制完整的椭圆。

四分椭圆弧

中心在原点,长半轴为 a a a、短半轴为 b b b 的椭圆隐函数方程为

F ( x , y ) = b 2 x 2 + a 2 y 2 ? a 2 b 2 = 0 F(x, y) = b^2 x^2 + a^2 y^2 -a^2 b^2 = 0 F(x,y)=b2x2+a2y2?a2b2=0

四分法画椭圆算法:已知第一象限内的一点 ( x , y ) (x, y) (x,y), 可以顺时针确定另外 3 个对称点 ( x , ? y ) (x, -y) (x,?y) ( ? x , ? y ) (-x, -y) (?x,?y) ( ? x , y ) (-x, y) (?x,y)

在这里插入图片描述

临界分析

在临界点处,曲线的斜率为 ? 1 -1 ?1

在这里插入图片描述
N ( x , y ) = N x i + N y j = ? F ? x i + ? F ? y j = 2 b 2 x i + 2 a 2 y j N(x, y) = N_{x_i} +N_{y_j} = \frac{\partial F}{\partial x}i + \frac{\partial F}{\partial y}j = 2b^2 x_i + 2 a^2y_j N(x,y)=Nxi??+Nyj??=?x?F?i+?y?F?j=2b2xi?+2a2yj?

法矢量的 x x x 方向的分量为 N x = 2 b 2 x N_x = 2b^2x Nx?=2b2x, 法矢量的 y y y 方向为 N y Ny Ny = 2a^2y.从曲线上一点的法矢量角度看,在区域 I \bm{I} I 内, N x < N y N_x < N_y Nx?<Ny? 在临界点处, N x = N y N_x = N_y Nx?=Ny? 在区域 Ⅱ \bm{Ⅱ} 内, N x > N y N_x > N_y Nx?>Ny?。显然,在临界点处,法矢量分量的大小发生了变化。

在这里插入图片描述
从曲线上的斜率角度来看,在临界点处,斜率为 ? 1 -1 ?1, 区域内 Ⅰ \bm{Ⅰ} 内, d x > d y dx > dy dx>dy, 所以 x x x 方向为主位移方向,在临界点处,有 d x = d y dx= dy dx=dy, 在区域内 Ⅱ Ⅱ 内, d y > d x dy > dx dy>dx, 所以 y y y 方向为主位移方向。在临界点处,主位移方向发生了改变。

在区域 Ⅰ Ⅰ x x x 方向上每次递增一个单位, y y y 方向上减 1 或 减 0, 取决于中点误差项的值,在区域 Ⅱ Ⅱ y y y 方向上每次递增一个单位, x x x 方向上加 1 或 加 0 取决于中点误差项的值。

在这里插入图片描述

构造区域 I I I 的中点误差项

从当前点 P i P_i Pi? 出发选取一个像素点时,需将 P u P_u Pu? P d P_d Pd? 两个候选像素连线的网格中点 M M M ( x i + 1 , y i ? 0.5 ) (x_i + 1, y_i -0.5) (xi?+1,yi??0.5) 代入隐函数的方程,构造中点误差项 d 1 i d_{1i} d1i?

d 1 i = F ( x i + 1 , y i ? 0.5 ) = b 2 ( x i + 1 ) 2 + a 2 ( y i ? 0.5 ) 2 ? a 2 b 2 d_{1i} = F(x_i + 1, y_i-0.5) = b^2 (x_i + 1)^2 + a^2 (y_i -0.5)^2 - a^2b^2 d1i?=F(xi?+1,yi??0.5)=b2(xi?+1)2+a2(yi??0.5)2?a2b2
在这里插入图片描述

y i + 1 = { y i d 1 i < 0 y i ? 1 d 1 i ≥ 0 y_{i+1} = \begin{cases} y_i & d_{1i} < 0\\ yi - 1 & d_1i \geq 0 \end{cases} yi+1?={yi?yi?1?d1i?<0d1?i0?

中点误差项 d 1 i d_{1i} d1i? 的递推公式

在这里插入图片描述
d 1 i < 0 d_1i < 0 d1?i<0 区域内 Ⅰ Ⅰ 内中点的递推

d 1 i + 1 = d 1 i + b 2 ( x i + 3 ) d_{1i+1} = d_{1i} + b^2(x_i + 3) d1i+1?=d1i?+b2(xi?+3)
在这里插入图片描述
d 1 i ≥ 0 d_1i \geq 0 d1?i0 区域内 Ⅰ Ⅰ 内中点的递推

d 1 i + 1 = d 1 i + b 2 ( x i + 3 ) + a 2 ( ? 2 y i + 2 ) d_{1i+1} = d_{1i} + b^2(x_i + 3) + a^2(-2y_i+ 2) d1i+1?=d1i?+b2(xi?+3)+a2(?2yi?+2)

中点误差项 d 1 i d_1i d1?i 的初值

在区域 Ⅰ Ⅰ 内,椭圆弧的起点扫描转换后的像素点为 P 0 ( a , b ) P_0(a, b) P0?(a,b) 沿着主位移 x x x 的方向递增一个单位,第一个参与判断的中点是 M ( 1 , b ? 0.5 ) M(1,b-0.5) M(1b?0.5), 响应的中点误差项 d 1 i d_{1i} d1i?

d 10 = b 2 + a 2 ( ? b + 0.25 ) d_{10} = b^2 + a^2(-b + 0.25) d10?=b2+a2(?b+0.25)

构造区域 Ⅱ Ⅱ 的中点误差项

在区域 Ⅱ Ⅱ 内,主位移方向发生变化,由 x x x 方向转变为 y y y 方向,从区域 Ⅰ Ⅰ 椭圆弧的终点, P i ( x i , y i ) P_i(x_i, y_i) Pi?(xi?,yi?) 出发选取下一像素时,需将 P 1 ( x i , y i ? 1 ) P_1(x_i, y_i-1) P1?(xi?yi??1) P r ( x I + 1 , y i + 1 ) P_r(x_I +1, y_i +1) Pr?(xI?+1,yi?+1)
的中点, M ( x i + 0.5 , y i ? 1 ) M(x_i + 0.5, y_i-1) M(xi?+0.5,yi??1) 代入隐函数方程,构造中点误差项 d 2 i d_{2i} d2i?

d 2 i = F ( x i + 0.5 , y i ? 1 ) = b 2 ( x i + 0.5 ) 2 + a 2 ( y i ? 1 ) 2 ? a 2 b 2 d_{2i} = F(x_i + 0.5, y_i-1) = b^2(x_i + 0.5)^2 + a ^2(y_i -1)^2 -a^2b^2 d2i?=F(xi?+0.5,yi??1)=b2(xi?+0.5)2+a2(yi??1)2?a2b2

在这里插入图片描述

x i + 1 = { x i + 1 d 2 i < 0 x i d 2 i ≥ 0 x_{i+1} = \begin{cases} x_i + 1& d_{2i} < 0\\ xi & d_{2i} \geq 0 \end{cases} xi+1?={xi?+1xi?d2i?<0d2i?0?

中点误差项 d 2 i d_{2i} d2i? 的递推公式

在这里插入图片描述

d 2 i < 0 d_{2i} < 0 d2i?<0 区域 Ⅰ Ⅰ 内中的递推
d 2 ( i + 1 ) = d 2 i + b 2 ( 2 x i + 2 ) + a 2 ( ? 2 y i + 3 ) d_{2(i+1)} = d_{2i} + b^2 (2x_i+2) + a^2(-2y_i +3) d2(i+1)?=d2i?+b2(2xi?+2)+a2(?2yi?+3)

在这里插入图片描述
d 2 i ≥ 0 d_{2i} \geq 0 d2i?0 区域 Ⅰ Ⅰ 内中的递推

d 2 ( i + 1 ) = d 2 i + a 2 ( ? 2 y i + 3 ) d_{2(i+1)} = d_{2i} + a^2(-2y_i + 3) d2(i+1)?=d2i?+a2(?2yi?+3)

中点误差项 d 2 i d_{2i} d2i? 的初始值

假定 P i ( x i , y i ) P_i(x_i, y_i) Pi?(xi?,yi?) 点为区域 Ⅰ Ⅰ 内椭圆弧上的最后一个像素, M I ( x i + 1 , y i ? 0.5 ) M_I(xi+1, y_{i-0.5}) MI?(xi+1,yi?0.5?) p u p_u pu? p d p_d pd? 像素的中点,满足 x x x 方向分量小于 y y y 方向分量

b 2 ( x i + 1 ) < a 2 ( y i ? 0.5 ) b^2(x_i +1) < a^2(y_i -0.5) b2(xi?+1)<a2(yi??0.5)

在这里插入图片描述

而在下一个中点处,不等号改变方向,则说明椭圆弧从区域 Ⅰ Ⅰ 转入了区域 Ⅱ Ⅱ 。 在区域 Ⅱ Ⅱ 内,中点转换为 M Ⅱ ( x i + 0.5 , y i ? 1 ) M_Ⅱ (x_i + 0.5, y_i -1) M?(xi?+0.5,yi??1), 用于判断选取 P 1 P1 P1 P r P_r Pr? 像素,所以区域 Ⅱ Ⅱ 内椭圆弧中电误差项 d d d 的初始值为

d 2 , 0 = b 2 ( x + 0.5 ) 2 + a 2 ( y ? 1 ) 2 ? a 2 b 2 d_{2, 0} = b^2(x+0.5)^2 + a^2(y-1)^2 - a^2b^2 d2,0?=b2(x+0.5)2+a2(y?1)2?a2b2

算法

  1. 读入椭圆的长半轴 a a a 和短半轴 b b b
  2. 定义椭圆当前坐标 x x x y y y 定义中点误差项 d 1 d_1 d1? d 2 d_2 d2? 定义像素颜色 cColoer
  3. 计算 d 10 = b 2 + a 2 ( ? b + 0.25 ) d_{10} = b^2 + a^2(-b+0.25) d10?=b2+a2(?b+0.25) x = 0 x=0 x=0, y = 0 y=0 y=0cColor=RGB(0, 0, 255)
  4. 绘制点 $(x, y) $及其在四分椭圆中的另外 3个对称点
  5. 判断 d 1 d_1 d1? 的符号,若 d 1 < 0 d_1<0 d1?<0 ( x , y ) 更新为 (x, y) 更新为 (x,y)更新为 ( x i + 1 , y ) (xi+1, y) (xi+1,y), d 1 d_1 d1? 更新为 d 1 + b 2 ( 2 x + 3 ) d_1+b^2(2x+3) d1?+b2(2x+3); 否则 ( x , y ) 更新为 (x, y) 更新为 (x,y)更新为 ( x i + 1 , y ? 1 ) (xi+1, y-1) (xi+1,y?1), d 1 d_1 d1? 更新为 d 1 + b 2 ( 2 x + 3 ) + a 2 ( ? 2 y + 2 ) d_1+b^2(2x+3) + a^2(-2y+2) d1?+b2(2x+3)+a2(?2y+2)
  6. b 2 ( x i + 1 ) < a 2 ( y i ? 0.5 ) b^2(x_i+1)<a^2(y_i-0.5) b2(xi?+1)<a2(yi??0.5) 时,重复 (4) 与 (5) 否则转到步骤 (7)
  7. 计算下半部分 d 2 d_2 d2? 的初值, d 20 = b 2 ( x + 0.5 ) 2 + a 2 ( y ? 1 ) 2 ? a 2 b 2 d_{20} = b^2(x+0.5)^2 + a^2(y-1)^2 - a^2 b^2 d20?=b2(x+0.5)2+a2(y?1)2?a2b2
  8. 绘制点 ( x , y ) (x, y) (x,y) 及其在四分椭圆中的另外 3 个对称点
  9. 判断 d 2 d_2 d2? 的符号,若 d 2 < 0 d_2 <0 d2?<0 ( x , y ) 更新为 (x, y) 更新为 (x,y)更新为 ( x i + 1 , y ? 1 ) (xi+1, y-1) (xi+1,y?1) d 2 d_2 d2? 更新为 d 2 + b 2 2 ( 2 x + 2 ) + a 2 ( ? 2 y + 3 ) d_2+b_2^2(2x+2) + a^2(-2y+3) d2?+b22?(2x+2)+a2(?2y+3) 否则 ( x , y ) 更新为 (x, y) 更新为 (x,y)更新为 ( x i + 1 , y ) (xi+1, y) (xi+1,y), d 2 d_2 d2? 更新为 d 2 + a 2 ( 2 y + 3 ) d_2+a^2(2y+3) d2?+a2(2y+3)
    10.如果 y ≥ 0 y \geq 0 y0 重复步骤 (8) 和 (9)
#include <QApplication>
#include <QPainter>
#include <QWidget>

void EllipsePoint(QPainter * painter, int x, int y) {
    QColor color(255, 0, 0);  // 设置为红色

    // 平移到正确的位置
    int centerX = 400;  // 窗口宽度的一半
    int centerY = 300;  // 窗口高度的一半

    painter->setPen(color);
    painter->drawPoint(centerX+x, centerY+y);
    painter->drawPoint(centerX+x, centerY-y);
    painter->drawPoint(centerX-x, centerY-y);
    painter->drawPoint(centerX-x, centerY+y);


}


void MidPointEllipse(QPainter* painter, int a, int b) {
    int x, y;
    x = 0, y = b;
    double d1 = b * b + a * a * (-b + 0.25);

    EllipsePoint(painter, x, y);

    while (b * b * (x+1) < a * a * (y-0.5)) {

        if (d1 < 0) {
            d1 += b * b * (2*x + 3);
        } else {
            d1 += b*b * (2*x + 3) + a* a*(-2*y +2);
            y--;
        }
        x++;
        EllipsePoint(painter, x, y);
    }
    double d2 = b * b * (x + 0.5) * (x + 0.5) + a * a * (y - 1) * (y -1) - a * a * b *b;
    while (y > 0) {
        if (d2 < 0) {
            d2 += b * b * (2*x + 2) + a * a * (-2*y + 3);
            x++;
        }else {
            d2 += a* a * (-2*y + 3);
        }
        y--;
        EllipsePoint(painter, x, y);
    }

}





class MyWidget : public QWidget {
public:
    MyWidget(QWidget* parent = nullptr) : QWidget(parent) {
        setFixedSize(800, 600);
    }

protected:
    void paintEvent(QPaintEvent* event) override {
        Q_UNUSED(event);

        QPainter painter(this);
        painter.setRenderHint(QPainter::Antialiasing, true);

//        int radius = 50;  // 圆的半径

        int a = 200;
        int b = 100;
//        MidPointCircle(&painter, radius);
        MidPointEllipse(&painter, a, b);

    }
};


int main(int argc, char* argv[]) {
    QApplication app(argc, argv);

    MyWidget widget;
    widget.show();

    return app.exec();
}

在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_43862398/article/details/135197190
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。