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;
}