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.

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 d_max to a low value like 10. To make it less sensitive to kinks, set d_max 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
   https://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;

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

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

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

function find_sharp_points()
{
    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) {
                /* Keep going until we are at least d_min away from
                   point i. */
                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 the sharpest points of the sharp points. */

function find_sharpest_points()
{
    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) { 
                    /* Add a new point, because we are d_max away from
                       the previous one. */
                    n_found++;
                    found = true;
                } else if (sharpness[i][2] > sharpness[last_found][2]) {
                    /* Overwrite the less sharp point at "last_found"
                       by not incrementing "n_found". */
                    found = true;
                }
            } else {
                /* Add a new point, the first one. */
                n_found++;
                found = true;
            }
        }
        if (found) {
            last_found = i;
            corners[n_found] = i;
        }
    }
}

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

function find_corners()
{
    /* Read the parameters from the web page form. */

    var form_alpha_max = getvalue("alpha_max")
    if (form_alpha_max) {
        angle = (Math.PI * form_alpha_max)/180.0; 
        cos_min = Math.cos (angle);
    }
    var form_d_min = getvalue("d_min");
    if (form_d_min) {
        d_min = form_d_min;
        d_min_sq = d_min * d_min;
    }
    var form_d_max = getvalue("d_max");
    if (form_d_max) {
        d_max = form_d_max;
        d_max_sq = d_max * d_max;
    }

    /* Apply the algorithm. */

    find_sharp_points();
    find_sharpest_points();
    canvas.show_corners();
}

var canvas;

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