像素多邊形

如果要繪製任意多邊形，可以基於〈像素直線〉來繪製多邊形邊緣，例如，修改一下〈像素直線〉的 beginPxPolyline 等函式為 beginPxShape：

在上面的範例中，可以基於是否指定 CLOSE，決定要繪製多邊形或是折線，現在問題來了，若想填滿多邊形的內部呢？

方式之一是找出繪製範圍內全部的座標，逐一拿來判斷是否在多邊形之中，若是就畫出，不過怎麼判斷座標是否在多邊形之中？

可以從座標點任意方向畫一直線，看看會穿過幾個邊，若穿過奇數個邊，表示座標點在多邊形內部，例如往右畫線：

依上圖實作出以下的 inShape 函式：

function inShape(shape, x, y) {
    let c = false;
    for(let i = shape.length - 1, j = 0; j < shape.length; i = j++) {
        const v1 = createVector(shape[i][0], shape[i][1]);
        const v2 = createVector(shape[j][0], shape[j][1]);
        if((v1.y > y) !== (v2.y > y)          // 兩個座標形成的水平帶狀之間
           && x < interpolateX(y, v1, v2)) {  // 兩個座標的左邊
            c = !c;
        }
    }
    return c;
}

function interpolateX(y, v1, v2) {
    if(v1.y === v2.y) {
        return v1.x;
    }
    return p5.Vector.lerp(v1, v2, (y - v1.y) / (v2.y - v1.y)).x;
}

那麼如何找出繪製範圍內全部的座標？p5.js 可以 translate，單純使用 (0, 0) 到 (x, y) 而 x、y 為大於等於 0 的方式行不通，不過，因為方才畫多邊形邊緣時，其實已經找出了邊緣的像素，只要收集這些像素，並從中找出同列最左與最右的座標就可以了。

掃描法看來不太有效率，然而足以應付像素不多的情況，只是有沒有更好的方法呢？想想繪圖軟體中倒油漆填滿的方式，可以在多邊形中找一點，然後上下左右探訪鄰居，若有就填滿，直到碰到邊緣為止。

來修改一下以上的範例，以便使用油漆填滿的方式，首先，因為不使用掃描法了，收集邊緣像素時，不用以列為單位：

// 收集邊緣像素
function shapeEdge(x1, y1, x2, y2, s, edgeCollector) {
    const v1 = createVector(round(x1), round(y1));
    const v2 = createVector(round(x2), round(y2));
    const diff = max(abs(v2.x - v1.x), abs(v2.y - v1.y));
    for(let d = 0; d <= diff; d++) {
        const v = p5.Vector.lerp(v1, v2, d / diff);
        const coord = {x: round(v.x), y: round(v.y)};
        // 用 JSON 字串直接作為鍵
        edgeCollector[JSON.stringify(coord)] = coord;
    }
}

原本的 endPxShape 就可以修改為：

function endPxShape(s, mode) {
    const edgeCollector = {};

    for(let i = 0; i < _pxPolyline.length - 1; i++) {
        const [x1, y1] = _pxPolyline[i];
        const [x2, y2] = _pxPolyline[i + 1];
        shapeEdge(x1, y1, x2, y2, s, edgeCollector);
    }

    if(mode === CLOSE) {
        const [x1, y1] = _pxPolyline[_pxPolyline.length - 1];
        const [x2, y2] = _pxPolyline[0];
        shapeEdge(x1, y1, x2, y2, s, edgeCollector);
    }

    // 邊緣
    Object.values(edgeCollector).forEach(coord => {
        square(coord.x * s, coord.y * s, s);
    });  

    // 填滿
    if(!_pxNoFilled) {
        …倒油漆
    }
}

現在，要來從已知的邊緣像素尋找多邊形中的一點：

function onePointInShape(edgeCollector) {
    const dirs = [[0, -1], [0, 1], [-1, 0], [1, 0]];

    const coords = Object.values(edgeCollector);
    let start;
    for(let i = 0; i < coords.length; i++) {
        const coord = coords[i];
        for(let j = 0; j < dirs.length; j++) {
            const x = coord.x + dirs[j][0];
            const y = coord.y + dirs[j][1];
            if(notIn(edgeCollector, x, y) && inShape(_pxPolyline, x, y)) {
                return {x, y};
            }
        }
    }
    return start;
}

function notIn(edgeCollector, x, y) {
    return edgeCollector[JSON.stringify({x, y})] === undefined;
}

倒油漆填滿可以用遞迴實作：

function flood(x, y, edgeCollector, floodCollector = {}) {
    const dirs = [[0, -1], [0, 1], [-1, 0], [1, 0]];

    const coord = {x, y};
    const key = JSON.stringify(coord);

    if(edgeCollector[key] === undefined) {     // 未超出邊界
        if(floodCollector[key] === undefined) {// 未填
            floodCollector[key] = coord;       // 填入
            // 上下左右四個方向
            dirs.forEach(dir => {
                flood(x + dir[0], y + dir[1], edgeCollector, floodCollector);
            });
        }
    }
    else {
        for(let i = 0; i < dirs.length; i++) {
            const nx = x + dirs[i][0];
            const ny = y + dirs[i][1];
            // 不是邊界而且是在多邊形內
            if(notIn(edgeCollector, nx, ny) && inShape(_pxPolyline, nx, ny)) {
                flood(nx, ny, edgeCollector, floodCollector);
                break;
            }
        }
    }

    return floodCollector;
}

注意，有可能某個內部座標四個方向正好被邊界夾住，然而它與其他內部座標是連通的，文件開頭第一個範例就示範了這種情況，單純地判斷不超出邊界部份來填滿，就會像在繪圖軟體中倒油漆填滿一樣，某些被封閉的地方沒填到。例如：

在繪圖軟體中，使用者可以在該處再倒一次油漆，不過這邊要自動找出這種封閉區域，因此上頭的 flood 中 else 的部份是必要的。

最後來畫個星星吧！