Hit detection on Beziercurves with tolerance?

Question

I have some quadratic bezier curves in a Canvas. How could I best go for hit detection on them, if they are only 1-2 px wide, and I want to provide some kind of tolerance, so that the user does not have to click exactly on the line.

Is there something to eg calculate the smallest distance from a bezier, and if that distance is small enough, select the bezier?

Answer 1

I can think of at least 3 ways of broadening the hit area of a quadratic bezier curve

I wouldn’t recommend this first solution, but here it is anyway!

Solution#1--Manually test your clickPoint against various points calculated on your bezier curve

Here is a function to calculate an XY which is n% of the way along your bezier and a function to test whether your clickPoint is within range of that bezier point.

var startPt=makePt(10,100);
var controlPt=makePt(50,30);
var endPt=makePt(90,100);

function makePt(X,Y){ return( { x:X, y:Y } ) }

// find points at various percent along bezier path
// (where percent is a decimal from 0 to 1)
function getQuadraticBezierXY(percent,startPt,controlPt,endPt) {
    var x = Math.pow(1-percent,2) * startPt.x + 2 * (1-percent) * percent * controlPt.x + Math.pow(percent,2) * endPt.x; 
    var y = Math.pow(1-percent,2) * startPt.y + 2 * (1-percent) * percent * controlPt.y + Math.pow(percent,2) * endPt.y; 
    return( makePt(x,y) );
}

// find whether 2 points are close to each other
// range is your pixel tolerance
function arePointsInRange(bezPt,testPt,range){
    var dx=testPt.x-bezPt.x;
    var dy=testPt.y-bezPt.y;
    return( dx*dx+dy*dy <= range*range )
}

Solution#2—Hit-test against a closed path which “widens” your curve

Note: isPointInPath() used below is available on modern browsers, but not on legacy browsers

Note: You don't have to actually display the widened curve to your user--you can draw the widened curve but not context.stroke(). (be sure the check out the docs for isPointInPath).

Note: Be sure to adjust your offsets for the slope of the line between your start and end points. My illustration below uses 0 slope for simplicity.

Here is code and a Fiddle: http://jsfiddle.net/m1erickson/4GEeu/

    var canvas=document.getElementById("canvas");
    var ctx=canvas.getContext("2d");

    ctx.lineWidth=2;
    ctx.strokeStyle="red";


    var startX=10;
    var startY=100;
    var controlX=50;
    var controlY=50;
    var endX=90;
    var endY=100;
    var offset=20;

    ctx.beginPath();
    ctx.moveTo(startX,startY-offset);
    ctx.quadraticCurveTo(controlX,controlY-offset,endX,endY-offset);
    ctx.lineTo(endX,endY+offset);
    ctx.quadraticCurveTo(controlX,controlY+offset,startX,startY+offset);
    ctx.closePath();
    ctx.stroke();

    // hitTest point [15,110] which is known to be inside
    // the widened curve path
    if(ctx.isPointInPath(15,110)){
        alert("Point [15,110] is in the closed quadratic curve path");
    }

Solution#3—Hit-test against a widened curve on an offscreen canvas

Note: my illustration just draws the onscreen curve wider. You might test on an offscreen canvas.

Here is code and a Fiddle: http://jsfiddle.net/m1erickson/MJfZt/

    var canvas=document.getElementById("canvas");
    var ctx=canvas.getContext("2d");

    ctx.lineWidth=20;
    ctx.strokeStyle="red";

    var startX=10;
    var startY=100;
    var controlX=50;
    var controlY=50;
    var endX=90;
    var endY=100;
    var offset=20;

    ctx.beginPath();
    ctx.moveTo(startX,startY);
    ctx.quadraticCurveTo(controlX,controlY,endX,endY);
    ctx.stroke();

    // hitTest point [10,100] which is known to be inside
    // the widened curve path
    if(hittestByColor(10,100,255,0,0)){
          alert("Pixel [10,100] is inside the widened curve");       
    }

    function hittestByColor(x,y,red,green,blue){
        var pxData = ctx.getImageData(x,y,1,1);
        return(pxData.data[0]==red 
            && pxData.data[1]==green 
            && pxData.data[2]==blue);
    }