使用扫描线循环绘制填充多边形

Question

我正在尝试使用扫描线循环中的单个像素绘制填充多边形（因此没有 lineTo 或 fill Canvas 方法）。

我能够用这种方法实现三角形（下面的示例），但我不确定从哪里开始使用更复杂的多边形（例如星形★）。任何人都可以就如何处理 Javascript 和 Canvas 的这个或现有形状算法示例提出任何建议吗？

我研究了 Bresenham 的算法，但由于我对它的理解有限，所以未能成功地将其应用于多边形。如果我解释的任何内容不清楚，请告诉我。

谢谢！

var canvas = document.querySelector('#canvas')
var ctx = canvas.getContext('2d');
var widthRange = document.querySelector('#widthRange')
var heightRange = document.querySelector('#heightRange')
ctx.fillStyle = 'blue';

var DrawPixel = function (x, y) {
  ctx.fillRect(x, y, 1, 1);
}

var x = 100;
var y = 100;
var width = widthRange.value;
var height = heightRange.value;

const draw = () =>
{
  ctx.clearRect(0,0,canvas.width,canvas.height); 
  wHRatio = width/height;
  for (var j=0; j<height; j++)
  {
    w = width-j*wHRatio;
    for (var i=0; i<w; i++)
    {
      DrawPixel(Math.floor(i+(j*(wHRatio/2))),height-j);
    }
  }
}

draw();

widthRange.addEventListener("input", function(e){
  width = e.currentTarget.value;
  draw();
})

heightRange.addEventListener("input", function(e){
  height = e.currentTarget.value;
  draw();
})

#canvas {
  outline: 1px solid grey;
}

.slidecontainer
{
  display: inline-block;
}

<div class="slidecontainer">
  <label for="widthRange">Width</label>
  <input type="range" min="1" max="300" value="100" class="slider" id="widthRange">
</div>
<div class="slidecontainer">
  <label for="heightRange">Height</label>
  <input type="range" min="1" max="150" value="100" class="slider" id="heightRange">
</div>
<canvas width=300 height=150 id="canvas"></canvas>

Answer 1

非自相交多边形的扫描线。

使用扫描线方法绘制任何具有 3 个或更多边的凹或凸多边形。

是最简单的，也是最慢的。
多边形是一组具有起点和终点的线。
多边形线可以是无序的
多边形必须闭合
None 条多边形线可以与任何其他多边形线交叉。

步骤

Find bounding box of lines. top, left, right, bottom.
Set x, y to  top left of bounding box.
while y is less than bottom.
    Find all lines that will cross the line from left, y to right, y
    Sort lines in distance from x to point where above line crossed
    while there are sorted lines
        shift two lines from sorted lines and scan the pixels between
    add 1 to y

一个实现。

函数scanlinePoly(lines, col)绘制像素。 lines 是用 createLines 创建的，它是一个包含辅助函数的行数组，用于添加行、查找行、排序行和获取边界。

辅助函数

createStar(x, y, r1, r2, points) 将为星星创建一个 lines 数组，x，y 星星中心，r1 半径，r2第二个半径，points 点数
P2(x, y) returns 二维点
L2(p1, p2) returns 包含直线斜率的二维直线。 p1、p2 是由 P2
atLineLevelY(y) returns 如果线在 y

const scanlinePoly = (lines, col) => {
    const b = lines.getBounds();
    var x, y, xx;
    ctx.fillStyle = col;
    b.left = Math.floor(b.left);
    b.top = Math.floor(b.top);
    for (y = b.top; y <= b.bottom; y ++) {
        // update 
        // old line was const ly = lines.getLinesAtY(y).sortLeftToRightAtY(y);
        // changed to
        const ly = lines.getLinesAtY(y + 0.5).sortLeftToRightAtY(y + 0.5);
        x = b.left - 1; 
        while(x <= b.right) {
            const nx1 = ly.nextLineFromX(x);
            if (nx1 !== undefined) {
                const nx2 = ly.nextLineFromX(nx1);
                if (nx2 !== undefined) {
                    const xS = Math.floor(nx1); 
                    const xE = Math.floor(nx2); 
                    for (xx = xS; xx < xE; xx++) {
                        ctx.fillRect(xx, y, 1, 1);
                    }
                    x = nx2;
                } else { break }
            } else { break }
        }
    }
}

function createLines(linesArray = []) {
     return   Object.assign(linesArray, {
        addLine(l) { this.push(l) },
        getLinesAtY(y) { return createLines(this.filter(l => atLineLevelY(y, l))) },
        sortLeftToRightAtY(y) {
            for (const l of this) { l.dist = l.p1.x + l.slope * (y - l.p1.y) }
            this.sort((a,b) => a.dist - b.dist);
            return this;
        },
        nextLineFromX(x) { // only when sorted
            const line = this.find(l => l.dist > x);
            return line ? line.dist : undefined;
        },
        getBounds() {
            var top = Infinity, left = Infinity;
            var right = -Infinity,  bottom = -Infinity;
            for (const l of this) {
                top = Math.min(top, l.p1.y, l.p2.y);
                left = Math.min(left, l.p1.x, l.p2.x);
                right = Math.max(right, l.p1.x, l.p2.x);
                bottom = Math.max(bottom, l.p1.y, l.p2.y);
            }
            return {top, left, right, bottom};
        },
    });
}

const createStar = (x, y, r1, r2, points) => {
    var i = 0, pFirst, p1, p2;
    const lines = createLines()
    while (i < points * 2) {
        const r = i % 2 ? r1 : r2;
        const ang = (i / (points * 2)) * Math.PI * 2;
        p2 = P2(Math.cos(ang) * r + x, Math.sin(ang) * r + y);
        if (pFirst === undefined) { pFirst = p2 };
        if (p1 !== undefined) { lines.addLine(L2(p1, p2)) }
        p1 = p2;
        i++;
    }
    lines.addLine(L2(p2, pFirst));    
    return lines;
}
const ctx = canvas.getContext("2d");

const P2 = (x = 0,y = 0) => ({x, y});
const L2 = (p1 = P2(), p2 = P2()) => ({p1, p2, slope: (p2.x - p1.x) / (p2.y - p1.y)});
const atLineLevelY = (y, l) => l.p1.y < l.p2.y && (y >= l.p1.y && y <= l.p2.y) || (y >= l.p2.y && y <= l.p1.y);

canvas.addEventListener("click", () => {
    ctx.clearRect(0,0,200,200);
    const star = createStar(
        100, 90, 
        Math.random() * 80 + 10,
        Math.random() * 80 + 10,
        Math.random() * 20 + 2 | 0
    );
    scanlinePoly(star, "#F00")


})


const star = createStar(100, 90, 90, 40, 10);
scanlinePoly(star, "#F00")

canvas {border: 1px solid black;}

<canvas id="canvas" width="200" height="180"></canvas>Click for rand star

注意那个内循环

for (xx = xS; xx < xE; xx++) {
    ctx.fillRect(xx, y, 1, 1);
}

可以替换成ctx.fillRect(xS, y, xE - xS, 1)，大大提高性能。

更新

再次查看我的答案以查看是否可以改进我注意到一个导致线条渲染不正确的问题。

修复函数外循环内的第一行scanlinePoly 需要改自.

const ly = lines.getLinesAtY(y).sortLeftToRightAtY(y);

到

const ly = lines.getLinesAtY(y + 0.5).sortLeftToRightAtY(y + 0.5);

使用扫描线循环绘制填充多边形

Draw a Filled Polygon using Scanline Loop

javascript

geometry

canvas

polygon

html5-canvas

非自相交多边形的扫描线。

步骤

一个实现。

更新