您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> J2ME

J2ME 圖形學算法實現：中點畫線、中點畫圓與 Bresenham 算法

編輯：J2ME

前言

在無 GPU 加速的 J2ME 環境下，高效的軟件光柵化算法至關重要。本文記錄三大經典算法的數學推導與 Java ME 完整實現代碼，均已編譯驗證。

一、中點畫線算法

1.1 數學原理

直線方程：F(x,y) = ax + by + c = 0
系數：a = y0 - y1、b = x1 - x0、c = x0*y1 - x1*y0
中點判別：d = F(xp+1, yp+0.5)
- d < 0：中點在線下方 → 選擇右上像素
- d >= 0：中點在線上方 → 選擇右像素
增量更新：
- 選右像素：d += a
- 選右上像素：d += a + b
初值：d0 = a + 0.5b → 為避免浮點，使用 2*d 整數運算

1.2 代碼實現

public void MidpointLine(Graphics g, int x0, int y0, int x1, int y1, int color) {
    int a = y0 - y1;
    int b = x1 - x0;
    int d = 2*a + b;        // 2*d0
    int delta1 = 2*a;       // 選右像素增量
    int delta2 = 2*(a+b);   // 選右上像素增量
    int x = x0, y = y0;
    g.setColor(color);
    g.drawLine(x, y, x, y); // 畫起點
    while (x < x1) {
        if (d < 0) {        // 選右上
            x++; y++;
            d += delta2;
        } else {            // 選右
            x++;
            d += delta1;
        }
        g.drawLine(x, y, x, y);
    }
}

二、中點畫圓算法

2.1 數學原理

圓方程：F(x,y) = x² + y² - R²
中點 M = (xp+1, yp-0.5) 判別：
- F(M) < 0：內部 → 選 p1 (xp+1, yp)
- F(M) >= 0：外部 → 選 p2 (xp+1, yp-1)
增量：
- 選 p1：d += 2*xp + 3
- 選 p2：d += 2*(xp - yp) + 5
初值：d0 = 1.25 - R → 令 e = d - 0.25，得 e0 = 1 - R
八分對稱性：計算 1/8 圓弧，鏡像生成其餘 7 段

2.2 代碼實現

public void MidpointCircle(Graphics g, int r, int color) {
    int x = 0, y = r, d = 1 - r; // e0
    g.setColor(color);
    draw8Points(g, x, y); // 畫八個對稱點
    while (x < y) {
        if (d < 0) {
            d += 2*x + 3;
            x++;
        } else {
            d += 2*(x - y) + 5;
            x++; y--;
        }
        draw8Points(g, x, y);
    }
}

private void draw8Points(Graphics g, int x, int y) {
    g.drawLine(x, y, x, y);
    g.drawLine(y, x, y, x);
    g.drawLine(-x, y, -x, y);
    g.drawLine(-y, x, -y, x);
    g.drawLine(-x, -y, -x, -y);
    g.drawLine(-y, -x, -y, -x);
    g.drawLine(x, -y, x, -y);
    g.drawLine(y, -x, y, -x);
}

三、Bresenham 畫線算法

3.1 數學原理

假設斜率 0 < k < 1（其他象限對稱處理）
誤差項 e 表示理論 y 與當前像素 y 的偏差
每步 x+1，e += k；e >= 0.5 時 y+1，e -= 1
整數化：e' = 2*e*dx，初值 -dx，增量 2*dy，閾值 0

3.2 代碼實現

public void BresenHam_Line(Graphics g, int x0, int y0, int x1, int y1, int color) {
    int dx = x1 - x0;
    int dy = y1 - y0;
    int e = -dx;
    int x = x0, y = y0;
    for (int i = 0; i <= dx; i++) {
        g.setColor(color);
        g.drawLine(x, y, x, y);
        x++;
        e += 2*dy;
        if (e >= 0) {
            y++;
            e -= 2*dx;
        }
    }
}