Detecting Regions Described By Lines On Html5 Canvas
Start with a 2d grid on an HTML5 canvas. The user creates lines by plotting points - up to 5 lines. Next, the user can select another arbitrary point on the grid, and the region
Solution 1:
You can use flood filling to color clicked areas bounded by your user-defined lines.
Let the user draw their lines on the canvas.
When the user clicks on a region bounded by lines, floodfill that region with a color.
Note: you must draw your gridlines underneath the canvas or else those gridlines will act as boundaries for the floodfill algorithm and you will just fill a grid cell. You can use CSS to layer an image under your canvas or use a separate canvas to draw the gridlines.
Here's starting example code and a Demo: http://jsfiddle.net/m1erickson/aY4Xs/
<!doctype html><html><head><linktype="text/css"media="all"href="css/reset.css" /><!-- reset css --><scripttype="text/javascript"src="http://code.jquery.com/jquery.min.js"></script><style>body{ background-color: ivory; }
#canvas{border:1px solid red;}
</style><script>
$(function(){
// canvas and mousedown related variablesvar canvas=document.getElementById("canvas");
var ctx=canvas.getContext("2d");
var $canvas=$("#canvas");
var canvasOffset=$canvas.offset();
var offsetX=canvasOffset.left;
var offsetY=canvasOffset.top;
var scrollX=$canvas.scrollLeft();
var scrollY=$canvas.scrollTop();
// save canvas size to vars b/ they're used oftenvar canvasWidth=canvas.width;
var canvasHeight=canvas.height;
// define the grid area// lines can extend beyond grid but// floodfill wont happen outside beyond the gridvar gridRect={x:50,y:50,width:200,height:200}
drawGridAndLines();
// draw some test gridlinesfunctiondrawGridAndLines(){
ctx.clearRect(0,0,canvas.width,canvas.height)
// Important: the lineWidth must be at least 5// or the floodfill algorithm will "jump" over lines
ctx.lineWidth=5;
ctx.strokeRect(gridRect.x,gridRect.y,gridRect.width,gridRect.height);
ctx.beginPath();
ctx.moveTo(75,25);
ctx.lineTo(175,275);
ctx.moveTo(25,100);
ctx.lineTo(275,175);
ctx.stroke();
}
// save the original (unfilled) canvas// so we can reference where the black bounding lines arevar strokeData = ctx.getImageData(0, 0, canvasWidth, canvasHeight);
// fillData contains the floodfilled canvas datavar fillData = ctx.getImageData(0, 0, canvasWidth, canvasHeight);
// Thank you William Malone for this great floodFill algorithm!// http://www.williammalone.com/articles/html5-canvas-javascript-paint-bucket-tool///////////////////////////////////////////////functionfloodFill(startX, startY, startR, startG, startB) {
var newPos;
var x;
var y;
var pixelPos;
var neighborLeft;
var neighborRight;
var pixelStack = [[startX, startY]];
while (pixelStack.length) {
newPos = pixelStack.pop();
x = newPos[0];
y = newPos[1];
// Get current pixel position
pixelPos = (y * canvasWidth + x) * 4;
// Go up as long as the color matches and are inside the canvaswhile (y >= 0 && matchStartColor(pixelPos, startR, startG, startB)) {
y -= 1;
pixelPos -= canvasWidth * 4;
}
pixelPos += canvasWidth * 4;
y += 1;
neighborLeft = false;
neighborRight = false;
// Go down as long as the color matches and in inside the canvaswhile (y <= (canvasHeight-1) && matchStartColor(pixelPos, startR, startG, startB)) {
y += 1;
fillData.data[pixelPos] = fillColor.r;
fillData.data[pixelPos + 1] = fillColor.g;
fillData.data[pixelPos + 2] = fillColor.b;
fillData.data[pixelPos + 3] = 255;
if (x > 0) {
if (matchStartColor(pixelPos - 4, startR, startG, startB)) {
if (!neighborLeft) {
// Add pixel to stack
pixelStack.push([x - 1, y]);
neighborLeft = true;
}
} elseif (neighborLeft) {
neighborLeft = false;
}
}
if (x < (canvasWidth-1)) {
if (matchStartColor(pixelPos + 4, startR, startG, startB)) {
if (!neighborRight) {
// Add pixel to stack
pixelStack.push([x + 1, y]);
neighborRight = true;
}
} elseif (neighborRight) {
neighborRight = false;
}
}
pixelPos += canvasWidth * 4;
}
}
}
functionmatchStartColor(pixelPos, startR, startG, startB) {
// get the color to be matchedvar r = strokeData.data[pixelPos],
g = strokeData.data[pixelPos + 1],
b = strokeData.data[pixelPos + 2],
a = strokeData.data[pixelPos + 3];
// If current pixel of the outline image is black-ishif (matchstrokeColor(r, g, b, a)) {
returnfalse;
}
// get the potential replacement color
r = fillData.data[pixelPos];
g = fillData.data[pixelPos + 1];
b = fillData.data[pixelPos + 2];
// If the current pixel matches the clicked colorif (r === startR && g === startG && b === startB) {
returntrue;
}
// If current pixel matches the new colorif (r === fillColor.r && g === fillColor.g && b === fillColor.b) {
returnfalse;
}
returntrue;
}
functionmatchstrokeColor(r, g, b, a) {
// never recolor the initial black divider strokes// must check for near black because of anti-aliasingreturn (r + g + b < 100 && a === 255);
}
// Start a floodfill// 1. Get the color under the mouseclick// 2. Replace all of that color with the new color// 3. But respect bounding areas! Replace only contiguous color.functionpaintAt(startX, startY) {
// get the clicked pixel's [r,g,b,a] color datavar pixelPos = (startY * canvasWidth + startX) * 4,
r = fillData.data[pixelPos],
g = fillData.data[pixelPos + 1],
b = fillData.data[pixelPos + 2],
a = fillData.data[pixelPos + 3];
// this pixel's already filledif (r === fillColor.r && g === fillColor.g && b === fillColor.b) {
return;
}
// this pixel is part of the original black image--don't fillif (matchstrokeColor(r, g, b, a)) {
return;
}
// execute the floodfillfloodFill(startX, startY, r, g, b);
// put the colorized data back on the canvas
ctx.putImageData(fillData, 0, 0);
}
// end floodFill algorithm//////////////////////////////////////////////// get the pixel colors under x,yfunctiongetColors(x,y){
var data=ctx.getImageData(x,y,1,1).data;
return({r:data[0], g:data[1], b:data[2], a:data[3] });
}
// create a random color object {red,green,blue}functionrandomColorRGB(){
var hex=Math.floor(Math.random()*16777215).toString(16);
var r=parseInt(hex.substring(0,2),16);
var g=parseInt(hex.substring(2,4),16);
var b=parseInt(hex.substring(4,6),16);
return({r:r,g:g,b:b});
}
functionhandleMouseDown(e){
e.preventDefault();
// get the mouse position
x=parseInt(e.clientX-offsetX);
y=parseInt(e.clientY-offsetY);
// don't floodfill outside the gridRectif(
x<gridRect.x+5 ||
x>gridRect.x+gridRect.width ||
y<gridRect.y+5 ||
y>gridRect.y+gridRect.height
){return;}
// get the pixel color under the mousevar px=getColors(x,y);
// get a random color to fill the region with
fillColor=randomColorRGB();
// floodfill the region bounded by black linespaintAt(x,y,px.r,px.g,px.b);
}
$("#canvas").mousedown(function(e){handleMouseDown(e);});
}); // end $(function(){});</script></head><body><h4>Click in a region within the grid square.</h4><canvasid="canvas"width=300height=300></canvas></body></html>[ Info about getImageData and the pixel array ]
context.getImageData().data gets an array representing r,g,b & a values of the specified area of the canvas (in our case we selected the whole canvas). The top-left pixel (0,0) is the first element(s) in the array.
Each pixel is represented by 4 sequential elements in the array.
The first array element holds the red component (0-255), the next element holds blue, the next holds green and the next holds the alpha (opacity).
// pixel 0,0
red00=data[0];
green00=data[1];
blue00=data[2];
alpha00=data[3];
// pixel 1,0
red10=data[4];
green10=data[5];
blue10=data[6];
alpha10=data[7];
Therefore, you jump to the red element of any pixel under the mouse like this:
// pixelPos is the position in the array of the first of 4 elements for pixel (mouseX,mouseY)var pixelPos = (mouseY * canvasWidth + mouseX) * 4And you can get all 4 r,g,b,a values by getting the next 4 pixel array elements
var r = fillData.data[pixelPos];
var g = fillData.data[pixelPos + 1];
var b = fillData.data[pixelPos + 2];
var a = fillData.data[pixelPos + 3];
Solution 2:
Here is a complete working solution you can see it running at http://jsfiddle.net/SalixAlba/PhE26/2/ It uses pretty much the algorithm in my first answer.
// canvas and mousedown related variablesvar canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
var $canvas = $("#canvas");
var canvasOffset = $canvas.offset();
var offsetX = canvasOffset.left;
var offsetY = canvasOffset.top;
var scrollX = $canvas.scrollLeft();
var scrollY = $canvas.scrollTop();
// save canvas size to vars b/ they're used oftenvar canvasWidth = canvas.width;
var canvasHeight = canvas.height;
// list of lines createdvar lines = new Array();
// list of all solutions var allSolutions = new Array();
// solutions round bounding rectvar refinedSols = new Array();
// ordered solutions for polygonvar polySols = new Array();
/////////// The line type// A line defined by a x + b y + c = 0
function Line(a,b,c) {
this.a = a;
this.b = b;
this.c = c;
}
// given two points create the line
function makeLine(x0,y0,x1,y1) {
// Line is defined by // (x - x0) * ( y1 - y0) = ( y - y0) * ( x1 - x0)// (y1-y0)*x - (x1-x0)* y + x0*(y1-y0)+y0*(x1-x0) = 0return new Line( (y1-y0), (x0-x1), -x0*(y1-y0)+y0*(x1-x0));
};
Line.prototype.toString = function () {
var s = "" + this.a + " x ";
s += (this.b >= 0 ? "+ "+this.b : "- "+ (-this.b) );
s += " y ";
s += (this.c >= 0 ? "+ "+this.c : "- "+ (-this.c) );
return s + " = 0";
};
Line.prototype.draw = function() {
var points = new Array();
// find the intersecetions with the boinding box// lhs : a * 0 + b * y + c = 0 if( this.b != 0 ) {
var y = -this.c / this.b;
if( y >= 0 && y <= canvasHeight )
points.push([0,y]);
}
// rhs : a * canvasWidth + b * y + c = 0 if( this.b != 0 ) {
var y = ( - this.a * canvasWidth - this.c )/ this.b;
if( y >= 0 && y <= canvasHeight )
points.push([canvasWidth,y]);
}
// top : a * x + b * 0 + c = 0 if( this.a != 0 ) {
var x = -this.c / this.a;
if( x > 0 && x < canvasWidth )
points.push([x,0]);
}
// bottom : a * x + b * canvasHeight + c = 0 if( this.a != 0 ) {
var x = ( - this.b * canvasHeight - this.c )/ this.a;
if( x > 0 && x < canvasWidth )
points.push([x,canvasHeight]);
}
if(points.length == 2) {
ctx.moveTo(points[0][0], points[0][1]);
ctx.lineTo(points[1][0], points[1][1]);
}
else
console.log(points.toString());
}
// Evalute the defining function for a line
Line.prototype.test = function(x,y) {
returnthis.a * x + this.b * y + this.c;
}
// Find the intersection of two lines
Line.prototype.intersect = function(line2) {
// need to solve// a1 x + b1 y + c1 = 0// a2 x + b2 y + c2 = 0var det = this.a * line2.b - this.b * line2.a;
if(Math.abs(det) < 1e-6) returnnull;
// (x) = 1 ( b2 -b1 ) ( -c1 )// ( ) = --- ( ) ( )// (y) det ( -a2 a1 ) ( -c2 )var x = ( - line2.b * this.c + this.b * line2.c ) / det;
var y = ( line2.a * this.c - this.a * line2.c ) / det;
var sol = { x: x, y: y, line1: this, line2: line2 };
return sol;
}
//// General methods // Find all the solutions of every pair of lines
function findAllIntersections() {
allSolutions.splice(0); // emptyfor(var i=0;i<lines.length;++i) {
for(var j=i+1;j<lines.length;++j) {
var sol = lines[i].intersect(lines[j]);
if(sol!=null)
allSolutions.push(sol);
}
}
}
// refine solutions so we only have ones inside the feasible region
function filterSols(targetX,targetY) {
refinedSols.splice(0);
// get the sign on the test point for each linevar signs = lines.map(function(line){
return line.test(targetX,targetY);});
for(var i=0;i<allSolutions.length;++i) {
var sol = allSolutions[i];
var flag = true;
for(var j=0;j<lines.length;++j) {
var l=lines[j];
if(l==sol.line1 || l==sol.line2) continue;
var s = l.test(sol.x,sol.y);
if( (s * signs[j] ) < 0 )
flag = false;
}
if(flag)
refinedSols.push(sol);
}
}
// build a polygon from the refined solutions
function buildPoly() {
polySols.splice(0);
var tempSols = refinedSols.map(function(x){return x});
if(tempSols.length<3) returnnull;
var curSol = tempSols.shift();
var curLine = curSol.line1;
polySols.push(curSol);
while(tempSols.length>0) {
var found=false;
for(var i=0;i<tempSols.length;++i) {
var sol=tempSols[i];
if(sol.line1 == curLine) {
curSol = sol;
curLine = sol.line2;
polySols.push(curSol);
tempSols.splice(i,1);
found=true;
break;
}
if(sol.line2 == curLine) {
curSol = sol;
curLine = sol.line1;
polySols.push(curSol);
tempSols.splice(i,1);
found=true;
break;
}
}
if(!found) break;
}
}
// draw
function draw() {
console.log("drawlines");
ctx.clearRect(0, 0, canvas.width, canvas.height)
if(polySols.length>2) {
ctx.fillStyle = "Orange";
ctx.beginPath();
ctx.moveTo(polySols[0].x,polySols[0].y);
for(var i=1;i<polySols.length;++i)
ctx.lineTo(polySols[i].x,polySols[i].y);
ctx.closePath();
ctx.fill();
}
ctx.lineWidth = 5;
ctx.beginPath();
lines.forEach(function(line, index, array) {console.log(line.toString()); line.draw();});
ctx.fillStyle = "Blue";
ctx.fillRect(x0-4,y0-4,8,8);
ctx.fillRect(x1-4,y1-4,8,8);
ctx.stroke();
ctx.beginPath();
ctx.fillStyle = "Red";
allSolutions.forEach(function(s,i,a){ctx.fillRect(s.x-5,s.y-5,10,10);});
ctx.fillStyle = "Green";
refinedSols.forEach(function(s,i,a){ctx.fillRect(s.x-5,s.y-5,10,10);});
ctx.stroke();
}
var x0 = -10;
var y0 = -10;
var x1 = -10;
var y1 = -10;
var clickCount = 0; // hold the number of clicks// Handle mouse clicks
function handleMouseDown(e) {
e.preventDefault();
// get the mouse positionvar x = parseInt(e.clientX - offsetX);
var y = parseInt(e.clientY - offsetY);
if(clickCount++ % 2 == 0) {
// store the position
x0 = x;
y0 = y;
x1 = -10;
y1 = -10;
filterSols(x,y);
buildPoly();
draw();
}
else {
x1 = x;
y1 = y;
var line = makeLine(x0,y0,x,y);
lines.push(line);
findAllIntersections();
draw();
}
}
$("#canvas").mousedown(function (e) {
handleMouseDown(e);
});
// add the lines for the bounding rectangle
lines.push(
new Line( 1, 0, -50 ), // first line is x - 50 >= 0
new Line(-1, 0, 250 ), // first line is -x + 250 >= 0
new Line( 0, 1, -50 ), // first line is y - 50 >= 0
new Line( 0,-1, 250 ) ); // first line is -y + 250 >= 0
findAllIntersections();
draw();
Solution 3:
Your first step is to find the two lines. There are various way of describing the lines: the traditional y=m x + c, a implicit form a x+b y+c=0, a parametric form (x,y) = (x0,y0) + t(dx,dy). Probably the most useful is the implicit form, as this can describe vertical lines.
If you have two points (x1,y1) and (x2,y2) the line can be given as y=y1 + (x-x1) (y2-y1)/(x2-x1). or (y-y1) * (x2-x1) = (x-x1)*(y2-y1).
You can do this for the two lines defined by the four points.
To actually draw the regions you will need to find the point where the lines intersect, this is standard solving two linear equation problem, which you probably did at high school. You will also need to find the points where the lines cross the boundary of your region. This is easier to find as you can just put the x or y values for the boundary into the equations and find the other coordinate. You probably also need to add a point at the corner of the box.
There will need to be some logic to work out which of the four possible segments you want.
For multiple lines you could treat it as a set of inequalities. You need to work out the equations of the lines say a1 * x + b1 * y + c1 >= 0, a2 * x + b2 * y + c2 <= 0 ... Call these E1, E2, ... The inequality will depend on which side of the line you want to be on. (Its not clear from the original question how your going to work this out.)
The simplest method uses a pixel based technique. Loop through the pixels in an image and set the pixel if all the inequalities are satisfied.
var myImageData = context.createImageData(width, height);
for(var x=xmin;i<xmax;++i) {
for(var y=ymin;j<ymax;++j) {
if( (a1 * x + b1 * y + c1 >= 0 ) &&
(a2 * x + b2 * y + c2 >= 0 ) &&
...
(a9 * x + b9 * y + c9 >= 0 ) )
{
var index = ((y-ymin)*width + (x-xmin))*4; // index of first byte of pixel
myImageData.data[index] = redValInside;
myImageData.data[index+1] = greenValInside;
myImageData.data[index+2] = blueValInside;
myImageData.data[index+3] = alphaValInside;
} else {
var index = ((y-ymin)*width + (x-xmin))*4; // index of first byte of pixel
myImageData.data[index] = redValOutside;
myImageData.data[index+1] = greenValOutside;
myImageData.data[index+2] = blueValOutside;
myImageData.data[index+3] = alphaValOutside;
}
}
}
If you want to actually get a polygon that becomes quite hard. You want to find the Feasible region defined by your inequalities. This is a classic problem in Linear_programming their might be a library out there which solves this.
A sketch algorithm for this might be. Assume lines are in form 'a x + b y + c >= 0'
// find all solutions for intersections of the linesvarposibleSols=newArray();
for(var line1 : all lines) {
for(var line2 : all lines) {
varpoint= point of intersection of line1 and line2
point.lineA = line1; // store the two lines for later use
point.lineB = line2;
}
}
// refine solutions so we only have ones inside the feasible regionvarrefinedSols=newArray();
for(var i=0;i<posibleSols.length;++i) {
varsoln= possibleSols[i];
varflag=true; // flag to tell if the line passesfor(var line : all lines) {
if( line == soln.line1 || line == soln.line2 ) continue; // don't test on lines for this pointif( line.a * point.x + line.b * point.b + line.c < 0 ) {
flag = false; // failed the test
}
}
if(flag)
refinedSols.push(sol); // if it passed all tests add it to the solutions
}
// final step is to go through the refinedSols and find the vertices in ordervarresult=newArray();
varcurrentSol= refinedSols[0];
result.push(currentSol);
varcurrentLine= startingSol.lineA;
refinedSols.splice(0,1); // remove soln from arraywhile(refinedSols.length>0) {
// fine a solution on the other end of currentLinevar nextSol;
for(var i=0;i< refinedSols.length;++i) {
nextSol = refinedSols[i];
if(nextSol.lineA == currentLine ) {
currentSol = nextSol;
currentLine = nextSol.lineA;
result.push(currentSol);
refinedSols.splice(i,1); // remove this from listbreak;
}
elseif( nextSol.lineB == currentLine ) {
currentSol = nextSol;
currentLine = nextSol.lineB;
result.push(currentSol);
refinedSols.splice(i,1); // remove this from listbreak;
}
}
// done you can now make a polygon from the points in result
Post a Comment for "Detecting Regions Described By Lines On Html5 Canvas"