J2ME 多邊形填充算法：掃描線轉換與像素級裁剪實現

從頂點數組到填充多邊形：純 Java 實現掃描線種子填充

J2ME Graphics.fillPolygon() 僅支持凸多邊形，且部分實現有 Bug。對於凹多邊形、複雜幾何體，需自行實現掃描線算法。本文提供一個完整的 Canvas 子類，演示如何將任意多邊形轉換為水平掃描線段並填充，最後支持裁剪輸出為新 Image。

核心算法：掃描線求交點

1. 遍歷每條掃描線 Y (0 ~ height-1)。
2. 對每條多邊形邊 (x0,y0)-(x1,y1)，判斷掃描線是否與該邊相交（不含水平邊端點重複計數）。
3. 計算交點 X = x0 + (x1-x0)*(Y-y0)/(y1-y0)。
4. 將所有交點 X 入堆，按從大到小排序（冒泡排序足夠，點數少）。
5. 兩兩配對 (X_2k, X_2k+1) 畫水平線段 drawLine(Xstart, Y, Xend, Y)。

關鍵代碼片段

// 檢查掃描線 y 是否與線段 (y0,y1) 相交
private boolean checkForCut(int y, int y0, int y1) {
    return (y0 >= y && y1 <= y) || (y0 <= y && y1 >= y);
}

// 獲取第 y 行所有交點 X，存入堆棧
private void getCut(int[][] nodes, int y) {
    int n = nodes.length;
    for (int i = 0; i < n - 1; i++) {
        int x0 = nodes[i][0], y0 = nodes[i][1];
        int x1 = nodes[i+1][0], y1 = nodes[i+1][1];
        if (y0 == y1 && y0 == y) { push(x0); push(x1); continue; }
        if (checkForCut(y, y0, y1)) {
            int tx = (x1 - x0) * (y - y0) / (y1 - y0) + x0;
            push(tx);
        }
    }
    // 首尾閉合邊
    if (nodes[0][1] == nodes[n-1][1] && nodes[0][1] == y) {
        push(nodes[0][0]); push(nodes[n-1][0]);
    } else if (checkForCut(y, nodes[n-1][1], nodes[0][1])) {
        int tx = (nodes[0][0] - nodes[n-1][0]) * (y - nodes[n-1][1])
               / (nodes[0][1] - nodes[n-1][1]) + nodes[n-1][0];
        push(tx);
    }
    sortHeapDesc(); // 冒泡降序
}

// 填充主循環
private void fillPolygon(int[][] nodes) {
    gb.setColor(0xFF0000);
    for (int y = 0; y < nHeight; y++) {
        getCut(nodes, y);
        if (heap == null) continue;
        int j = 0, startX = 0;
        while (heap != null) {
            int x = pop();
            if ((j % 2) == 0) startX = x;
            else gb.drawLine(startX, y, x, y);
            j++;
        }
    }
}

堆棧實現細節

為避免 Vector 開銷，採用動態數組模擬堆棧：

• push()：數組擴容 +1，複製舊數據，存入新元素，System.gc()。
• pop()：取尾元素，數組縮容 -1，複製數據，System.gc()。
• sortHeapDesc()：簡單冒泡排序，點數通常 < 20，性能可接受。

圖片裁剪輸出

填充繪製在離屏 bufImg 上，需裁剪某矩形區域時：

private Image theCutImg;
private void cutGraphics(int x, int y, int w, int h) {
    theCutImg = Image.createImage(w, h);
    Graphics tg = theCutImg.getGraphics();
    tg.drawImage(bufImg, -x, -y, 0); // 負座標偏移實現裁剪
}

完整測試類結構

class PolygonFillCanvas extends Canvas implements Runnable {
    int[][] nodes = {{20,100},{100,40},{170,80},{150,110},{170,170},{160,150},{110,110},{50,130}};
    Image bufImg; Graphics gb;
    // ... 構造函數創建 bufImg/gb
    public void run() {
        gb.setColor(0xFFFFFF); gb.fillRect(0,0,getWidth(),getHeight());
        fillPolygon(nodes);
        drawPolygonOutline(nodes); // 綠色描邊
        repaint();
    }
    public void paint(Graphics g) { g.drawImage(bufImg,0,0,0); }
}

應用場景與優化建議

• 遊戲地形遮罩、非矩形按鈕熱區、特效遮罩生成。
• 實時填充較慢，建議**預計算**生成掩碼圖片緩存，運行時直接 drawImage。
• 大多邊形可考慮定點數學優化除法，或改用中點圓/貝塞爾曲線近似。