scan line algorithm
Javascript implementation of scanline polygon fill
<canvas id="myCanvas"></canvas>
<canvas id="myCanvas"></canvas>
xvar points = [
{x: 100, y: 50}, {x: 120, y: 100 }, {x: 160, y: 50 }, {x: 200, y: 100 }, {x: 300, y: 50}, {x: 350, y: 350}, {x: 300, y: 250}, {x: 50, y: 150}, {x: 100, y: 50}];
//init canvasvar canvas = document.getElementById('myCanvas');
canvas.width = window.innerWidth - 50;
canvas.height = window.innerHeight - 50;
var ctx = canvas.getContext('2d');
//end init//generate linevar lines = [];
for (var i = 1; i < points.length; i++) {
lines.push(new Line(points[i - 1], points[i]));
}
//draw polygonctx.strokeStyle = "#00a";
ctx.beginPath();
ctx.moveTo(points[0].x, points[0].y);
for (var j = 1; j < points.length; j++) {
p = points[j];
ctx.lineTo(p.x, p.y);
}
ctx.closePath();
ctx.stroke();
// find min and maxvar minY = points[0].y;
var maxY = points[0].y;
for (var i = 0; i < points.length; i++) {
var temp = points[i].y;
if (temp < minY)
minY = temp;
else if (temp > maxY)
maxY = temp;
}
// end find//draw fill linectx.strokeStyle = "#0af";
ctx.beginPath();
for (var y = minY; y < maxY; y++) {
var meetPoint = getMeetPoint(y);
for (var i = 1; i < meetPoint.length; i += 2) {
ctx.moveTo(meetPoint[i - 1], y);
ctx.lineTo(meetPoint[i], y);
}
}
ctx.stroke();
//end fill linefunction getMeetPoint(y) {
var meet = [];
for (var i = 0; i < lines.length; i++) {
var l = lines[i];
if (l.isValidY(y)) {
meet.push(l.getX(y));
}
}
//sortfor (var i = 0; i < meet.length; i++)
for (var j = i; j < meet.length; j++) {
if (meet[i]>meet[j]) {
var temp =meet[i];
meet[i]=meet[j];
meet[j]=temp;
}
}
return meet;
}
function Line(start, end) {
this.x0 = start.x;
this.x1 = end.x;
this.y0 = start.y;
this.y1 = end.y;
this.m = (this.y1 - this.y0) / (this.x1 - this.x0);
this.getX = function (y) {
if (!this.isValidY(y))
throw new RangeError();
return 1 / this.m * (y - this.y0) + this.x0;
}
this.isValidY = function (y) {
if (y >= this.y0 && y < this.y1) {
return true;
}
if (y >= this.y1 && y < this.y0) {
return true;
}
return false;
}
}