Detect points of high curvature

This JavaScript program finds kinks, sharp bends, and corners, technically described as "points of high curvature", in a line. This implements the algorithm found at Detection of High Curvature Points in Planar Curves. This demo uses a <canvas> element for drawing. (Apologies but this may not work on some browsers, such as Internet Explorer.) Draw a line by pressing your mouse button in the green square and moving the mouse. When you release the mouse, the program will automatically compute the points of high curvature and add purple circles.

dmin
dmax
αmax

You can adjust the variables used to find the points of high curvature by typing values into the boxes. For example, to increase the sensitivity of the algorithm to bendiness, set αmax to 170° To reduce the sensitivity, set it to a low value like 120°. To make it find smaller kinks in the line, set dmax to a low value like 10. To make it less sensitive to kinks, set dmax to a high value like 30.

See Chetverikov's paper for full details about the variables.

To clear the drawing area, use the button marked "clear". Even after you clear the canvas, you can redraw the last-drawn line using the button marked "redraw". You can then re-find the points of high curvature using the "find" button.

This implementation of Chetverikov's corner finding algorithm in JavaScript follows the description in Chetverikov's online paper closely. The routine find_corners is called when the user releases the mouse button on the drawing area.

The drawing code for the <canvas> part is not included below. It is similar in principle to that at A simple scribbler using <canvas>. The source code for the canvas drawing part can be seen at the source code for the canvas drawing.

/* The line drawn by the user. */

var Line = new Array();

/* For each point on the line, measure the sharpness of the turn there. */

var sharpness = new Array();

/* The detected corners are stored in the following array. */

var corners = new Array();

/* Variables for the algorithm: see
http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/CHETVERIKOV2/node7.html
*/

var d_min = 10;
var d_min_sq = d_min*d_min;
var d_max = 2*d_min;
var d_max_sq = d_max*d_max;
var cos_min = -0.75;

/* Check whether "i" is a valid point on "Line". */

function check_line_bounds (i)
{
    if (i < 0 || i >= Line.length) {
        alert ("Bad point index "+i);
        exit;
    }
}

/* Return the square of the distance between point "i" and point "j"
 * on "Line". */

function distance_sq(i,j)
{
    check_line_bounds (i);
    check_line_bounds (j);
    var i=Line[i];
    var j=Line[j];
    var x_diff = j[0] - i[0];
    var y_diff = j[1] - i[1];
    return (x_diff * x_diff + y_diff * y_diff);
}

/*
   Calculate the sharpness at each point of the curve.
*/

function first_pass()
{
    var i;
    for (i=0;i<Line.length;i++) {
        /* Each element of the "sharpness" array contains the
        sharpness as the third value, and the offsets before and after
        the point where this sharpness maximum was obtained as the
        first and second value. The fourth value is a flag which
        indicates whether or not the sharpness has been calculated for
        this point. */
        sharpness[i] = [-1,-1,1000,"empty"];
        var cos_max = -1;
        var seen_one_upper=false;
        for (var plus = i + 1; plus < Line.length; plus++) {
            a_sq = distance_sq (i, plus);
            if (seen_one_upper && a_sq > d_max_sq) {
                if (sharpness[i][3] == "empty")
                    sharpness[i][3] = "fail upper";
                break;
            }
            if (a_sq < d_min_sq)
                continue;
            seen_one_upper = true;
            var seen_one_lower=false;
            for (minus = i - 1; minus >= 0; minus--) {
                b_sq = distance_sq (i, minus);
                if (seen_one_lower && b_sq > d_max_sq) {
                    if (sharpness[i][3] == "empty")
                        sharpness[i][3] = "fail lower";
                    break;
                }
                if (b_sq < d_min_sq)
                    continue;
                seen_one_lower = true;
                var c_sq = distance_sq (plus, minus);
                var top = a_sq + b_sq - c_sq;
                var bottom = 2.0*Math.sqrt (a_sq*b_sq);
                var cos = -2;
                if (bottom != 0.0) {
                    cos = top/bottom;
                }
                if (cos < cos_min) {
                    if (sharpness[i][3] == "empty") {
                        sharpness[i][2] = cos;
                        sharpness[i][3] = "angle fail";
                    }
                    break;
                }
                if (cos_max < cos) {
                    cos_max = cos;
                    sharpness[i] = [plus,minus,cos,"OK"];
                } else {
                    if (sharpness[i][3] == "empty") {
                        sharpness[i][2] = cos;
                        sharpness[i][3] = "angle fail";
                    }
                }
            }
        }
    }
}

/* Find maxima of the sharpnesses. */

function second_pass()
{
    corners.length = 0;
    var n_found = -1;
    var last_found = -1;
    for (i=0;i<Line.length;i++) {
        var found = false;
        if (sharpness[i][2] > cos_min && sharpness[i][3]=="OK") {
            if (last_found >= 0) {
                var dist_sq = distance_sq (last_found, i);
                if (dist_sq > d_max_sq) { 
                    n_found++;
                    found = true;
                } else if (sharpness[i][2] > sharpness[last_found][2]) {
                    found = true;
                }
            } else {
                n_found++;
                found = true;
            }
        }
        if (found) {
            last_found = i;
            corners[n_found] = i;
//          alert ("Found corner "+n_found+" at "+i);
        }
    }
}

function find_corners()
{
    var form_alpha_max = getvalue("alpha_max")
    if (form_alpha_max) {
        angle = (Math.PI * form_alpha_max)/180.0; 
        cos_min = Math.cos (angle);
/*
        alert ("Angle is "+form_alpha_max+
               " (radians: "+angle+") "+
               "Cosine: "+cos_min);
*/
    }
    var form_d_min = getvalue("d_min");
    if (form_d_min) {
        d_min = form_d_min;
        d_min_sq = d_min * d_min;
//      alert ("d_min is "+d_min+ "d_min_sq: "+d_min_sq);
    }
    var form_d_max = getvalue("d_max");
    if (form_d_max) {
        d_max = form_d_max;
        d_max_sq = d_max * d_max;
//      alert ("d_max is "+d_max+ "d_max_sq: "+d_max_sq);
    }
    first_pass();
    second_pass();
    canvas.show_corners();
}

function getvalue (id)
{
    var element = document.getElementById (id);
    var value = element.value;
    if (! value)
        return;
    return value;
}

var canvas;

onload = function () {
    canvas = new CornerCanvas();
}

Copyright © Ben Bullock 2009-2017. All rights reserved. For comments, questions, and corrections, please email Ben Bullock (benkasminbullock@gmail.com). / Privacy / Disclaimer