How to insert a point in the correct location of an array of points (polyline)

Question

Say I have an array of points that I'm using to draw a polyline. When I click on the polyline I want to add a new point on the line where the click occurred. I need to figure out where to insert the new point in the array so the line is drawn correctly. A line can go in any direction: up, down, left, right, up & left, down & right, etc, so my initial thought was to figure out the direction and slope the line was traveling in and then making comparisons from there. With that in mind, I came up with this code:

 /**
 * Determines direction line is traveling in
 * @param {Object} point1 - starting point
 * @param {Object} point2 - ending point
 * @param {Object} offset - position offset
 * @return {Number} direction traveling (0 - straight up, 1 - up & right, 2 - straight right, 3 - down & right, etc.)
 */
getLineDirection: function(point1, point2, offset){
    var rise, run, abs1, abs2, dirX, dirY,
        slope, direction, ceil = {}, floor = {};

    //get normalized positions
    abs1 = this.getPointPosition(null,offset,point1);
    abs2 = this.getPointPosition(null,offset,point2);

    dirX = abs1.x > abs2.x ? -1 : 1;
    dirY = abs1.y > abs2.y ? 1 : -1;

    ceil.x = abs2.x > abs1.x ? abs2.x : abs1.x;
    ceil.y = abs2.y > abs1.y ? abs2.y : abs1.y;

    floor.x = abs2.x > abs1.x ? abs1.x : abs2.x;
    floor.y = abs2.y > abs1.y ? abs1.y : abs2.y;

    run = ceil.x - floor.x;
    rise = ceil.y - floor.y

    if(abs2.y > abs1.y){
        rise = -rise;
    }

    if(abs2.x < abs1.x){
        run = -run;
    }

    if(rise !== 0){
        slope = rise/run;
        if(slope === 0){
            //horizontal
            direction = dirX > 0 ? 2 : 6;
        } else {
            //angle
            if(dirX === 1){
                direction = dirY === 1 ? 1 : 3;
            } else {
                direction = dirY === -1 ? 5 : 7;
            }
        }
    } else {
        //vertical
        direction = dirY > 0 ? 0 : 4;
    }

    return direction;
}

With this, I figured I could iterate through the points that make up the line and then determine if the new point should get inserted before that respective point or not. This almost works, but something is off.

findInsertionIndex : function(x,y){
    var count = this.points.length-1;
    var p1 = this.points[0];
    var p2 = { x : p1.x, y : p1.y };
    var offset = this.offset();
    var direction, pos;

    for(i = 1; i < count;i++){
        p2.x += this.points[i].x;
        p2.y += this.points[i].y;
        direction = this.getLineDirection(p1,p2,offset);
        pos = this.getPointPosition(null,offset,p2);

        //TODO: handle vertical lines
        if(direction > 0 && direction < 4){
            if(x < pos.x){
                break;
            }
        } else if (direction > 4){
            if(x > pos.x){
                break;
            }
        }

        p1 = p2;
    }

    return i;
}

I suck at math, but this seemed like a logical approach. I'm thinking there is probably a better way to do this. If anyone can point me in the right direction, I would appreciate it.

Ok, no more cheap puns :)

Edit

Thanks to @MvG, here is the completed findInsertionIndex block for reference:

findInsertionIndex : function(x,y){
    var count = this.points.length;
    var offset = this.offset();
    var p1 = this.getPointPosition(0,offset), p2;
    var direction, pos, ox, oy, dx, dy, t, ex, ey, errSq,best,bestIndex = count-1;

    for(var i = 1; i < count;i++){
        p2 = this.getPointPosition(i,offset);
        ox = x - p1.x;
        oy = y - p1.y;
        dx = p2.x - p1.x;
        dy = p2.y - p1.y;

        t = (ox*dx + oy*dy)/(dx*dx + dy*dy);
        if (t < 0) t = 0;
        if (t > 1) t = 1;
        ex = t*dx - ox;
        ey = t*dy - oy;
        errSq = ex*ex + ey*ey;
        if (!best || errSq < best) {
          best = errSq;
          bestIndex = i;
        }

        p1 = p2;
    }

    return bestIndex;

}

Answer 1

Drop the slope concept, since it forces you to do special cases for vertical lines. Instead, you can compute something like this:

ox = x - p1.x;
oy = y - p1.y;
dx = p2.x - p1.x;
dy = p2.y - p1.y;
t = (ox*dx + oy*dy)/(dx*dx + dy*dy);
if (t < 0) t = 0;
if (t > 1) t = 1;
ex = t*dx - ox;
ey = t*dy - oy;
errSq = ex*ex + ey*ey;
if (errSq < best) {
  best = errSq;
  bestIndex = i;
}

This looks at the point on each segment which is closest to your input point. It first determines a parameter t which tells you where along the segment this closest point occurs. This is the dot product of the direction vector of the line (dx,dy) and the vector from the starting point to the mouse point (ox,oy), divided by the squared norm of the direction vector. Capping this t to the [0,1] range, you restruct yourself to the segment instead of the whole line. Then you can compute the difference vector (ex,ey) between this closest point and your input point, and take its squared norm as a measure of how close to the current segment the input point actually is. Iterate over all line segments and remember the best, and you are done.