J2ME 圖形學實作：中點畫圓演算法詳解

中點畫圓演算法屬於增量掃描轉換法，利用判別式決定下一個像素位置，僅需整數運算，極適合資源受限的 J2ME 環境。

數學原理

圓方程：F(x, y) = x² + y² - r²

• 圓上點：F(x, y) = 0
• 圓外點：F(x, y) > 0
• 圓內點：F(x, y) < 0

取第八分圓弧（x 從 0 遞增至 y），中點 M = (x_p+1, y_p-0.5)

• F(M) < 0 → M 在圓內 → 選 P1 (x+1, y)
• F(M) ≥ 0 → M 在圓外 → 選 P2 (x+1, y-1)

判別式 d = F(M) 遞推公式：

• 選 P1：dnew = d + 2xp + 3
• 選 P2：dnew = d + 2(xp - yp) + 5

初始值：d₀ = 1 - r（經 e = d - 0.25 整數化）

完整實作碼

public void MidpointCircle(Graphics g, int r, int color) {
    int x = 0, y = r, d = 1 - r;
    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);
    }
}

// 輔助：利用八向對稱一次畫 8 點
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);
}

效能優化重點

1. 僅用整數運算：避免浮點數，符合 CLDC 1.0 無浮點運算限制。
2. 八向對稱：一次計算繪製 8 點，減少 7/8 迴圈次數。
3. 遞推增量：判別式以加法更新，無乘除指令。

此演算法為 J2ME 遊戲繪圖、儀表盤等圓形 UI 元件的基石，編譯通過於 MIDP 2.0/CLDC 1.1 環境。