Detecting Regions Described by Lines on HTML5 Canvas

Question

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 is highlighted. I need to take that point and define a polygon to fill the region described by the lines created by the user.

So my thought is, I need to detect the lines and canvas edges that surround the arbitrary point, and then draw a polygon.

Here is an image to help understand what I mean (where the system is functioning with two lines):

All the state is managed by using jCanvas and custom Javascript.

Thanks!

---

Wow... I just woke up and found these incredible answers. Love SO. Thanks guys.

Answer 1

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 variables
var 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 often
var canvasWidth = canvas.width;
var canvasHeight = canvas.height;

// list of lines created
var lines = new Array();

// list of all solutions 
var allSolutions = new Array();
// solutions round bounding rect
var refinedSols = new Array();
// ordered solutions for polygon
var 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) = 0
    return 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) {
    return this.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 = 0
    var det = this.a * line2.b - this.b * line2.a;
    if(Math.abs(det) < 1e-6) return null;
    // (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); // empty
    for(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 line
    var 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) return null;
    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 position
    var 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();