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

中點畫線演算法同屬增量掃描轉換法，適用於斜率 |k| ≤ 1 的線段，透過判別式符號決定下一像素在 (x+1, y) 或 (x+1, y+1)。

數學推導

直線方程：F(x, y) = ax + by + c = 0
其中 a = y₀ - y₁, b = x₁ - x₀, c = x₀y₁ - x₁y₀

中點 M = (x_p+1, y_p+0.5) 代入：
d = F(M) = a(xp+1) + b(yp+0.5) + c

• d < 0 → M 在線下方 → 選 (x+1, y+1)
• d ≥ 0 → M 在線上方 → 選 (x+1, y)

增量推導：

• 選 (x+1, y)：dnew = d + a → Δ₁ = 2a（乘 2 整數化）
• 選 (x+1, y+1)：dnew = d + a + b → Δ₂ = 2(a+b)

初始值：d₀ = a + 0.5b → 整數化 2d₀ = 2a + b

完整實作碼

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;     // 選 (x+1, y) 的增量
    int delta2 = 2 * (a + b); // 選 (x+1, y+1) 的增量
    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);
    }
}

適用範圍與擴展

• 本範例假設 x0 < x1 且 |斜率| ≤ 1（即 |a| ≤ |b|）。
• 完整實作需處理八個象限：交換 x/y、正負號變換、端點排序。
• J2ME Graphics.drawLine 內部即使用類似演算法，自行實作可控制像素級效果（如虛線、漸層）。

掌握中點畫線是進一步實作多邊形填充、反鋸齒等進階圖形功能的基礎。