使用Scanline Loop绘制一个填充的多边形 [英] Draw a Filled Polygon using Scanline Loop

问题描述

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

I'm trying to draw a filled polygon using individual pixels in a scanline loop (so no lineTo or fill Canvas methods).

我可以通过这种方法实现三角形(下面的示例)，但是我不确定从哪里开始使用更复杂的多边形(例如星形★).任何人都可以就如何处理Java或现有形状算法示例提供任何建议吗?画布?

I was able to achieve a triangle in this method (example below), but I'm not sure where to begin with a more complex polygon (such as a star shape ★). Can anyone give any advice on how to approach this or existing shape algorithm examples for Javascript & Canvas?

我已经研究了Bresenham的算法，但是由于对它的了解有限，因此未能成功将其用于多边形.如果我解释不清楚的话，请告诉我.

I have researched Bresenham’s Algorithm but was unsuccessful implementing it for polygons because of my limited understanding of it. Please let me know if anything I've explained is unclear.

谢谢！

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>

推荐答案

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

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

Scanline for non self intersecting polygons.

Draw any concave or convex polygon with 3 or more sides using scanline method.

• 最简单，也最慢.
• 多边形是一组具有起点和终点的线.
• 多边形线可以无序
• 多边形必须关闭
• 任何多边形线都不能与其他任何多边形线交叉.

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 创建的，它是具有辅助功能的线阵列，用于添加线，查找线，对线进行排序并获得边界.

An implementation.

Function scanlinePoly(lines, col) draw the pixels. lines is create with createLines which is an array of lines with helper functions to add lines, find lines, sort lines, and get bounds.

助手功能

• createStar(x，y，r1，r2，points)将为星星， x ，创建一个 lines 数组y 星心， r1 半径， r2 第二半径，点点数
• P2(x，y)返回2D点
• L2(p1，p2)返回包含该线的斜率的2D线. p1 ， p2 是由 P2
创建的点如果行与 y 处的扫描线交叉，则
• atLineLevelY(y)返回true

• createStar(x, y, r1, r2, points) will create a lines array for a star, x, y center of star, r1 radius, r2 second radius, points number of points
• P2(x, y) returns 2D point
• L2(p1, p2) returns 2D line that includes the slope of the line. p1, p2 are points as created by P2
• atLineLevelY(y) returns true if line crosses scan line at 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)替换，以大大提高性能.

Can be replaced with ctx.fillRect(xS, y, xE - xS, 1) to greatly improve performance.

再次查看我的答案以查看是否可以改进它，我注意到一个问题，该错误导致线条渲染错误.

Looking at my answer again to see if it could be improved I noticed a problem that resulted in lines incorrectly rendered.

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

To fix the the first line inside the outer loop of function scanlinePoly needs to be changed from.

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

收件人

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

这篇关于使用Scanline Loop绘制一个填充的多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！