scan line algorithm
Javascript implementation of scanline polygon fill
<canvas id="myCanvas"></canvas>
<canvas id="myCanvas"></canvas>
x
var 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 canvas
var canvas = document.getElementById('myCanvas');
canvas.width = window.innerWidth - 50;
canvas.height = window.innerHeight - 50;
var ctx = canvas.getContext('2d');
//end init
//generate line
var lines = [];
for (var i = 1; i < points.length; i++) {
lines.push(new Line(points[i - 1], points[i]));
}
//draw polygon
ctx.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 max
var 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 line
ctx.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 line
function 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));
}
}
//sort
for (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;
}
}