Find A Point On A Line Closest To A Third Point Javascript

I'm trying to find a point on a line closest to a third point off of the line. The points are latitude/longitude. The simple graphic shows what I'm trying to achieve. I'm using it

Solution 1:

RCrowe @ Find a point in a polyline which is closest to a latlng

/* desc Static function. Find point on lines nearest test point
   test point pXy with properties .x and .y
   lines defined by array aXys with nodes having properties .x and .y 
   return is object with .x and .y properties and property i indicating nearest segment in aXys 
   and property fFrom the fractional distance of the returned point from aXy[i-1]
   and property fTo the fractional distance of the returned point from aXy[i]   */


function getClosestPointOnLines(pXy, aXys) {

    var minDist;
    var fTo;
    var fFrom;
    var x;
    var y;
    var i;
    var dist;

    if (aXys.length > 1) {

        for (varn=1 ; n < aXys.length ; n++) {

            if (aXys[n].x != aXys[n - 1].x) {
                vara= (aXys[n].y - aXys[n - 1].y) / (aXys[n].x - aXys[n - 1].x);
                varb= aXys[n].y - a * aXys[n].x;
                dist = Math.abs(a * pXy.x + b - pXy.y) / Math.sqrt(a * a + 1);
            }
            elsedist= Math.abs(pXy.x - aXys[n].x)

            // length^2 of line segment varrl2= Math.pow(aXys[n].y - aXys[n - 1].y, 2) + Math.pow(aXys[n].x - aXys[n - 1].x, 2);

            // distance^2 of pt to end line segmentvarln2= Math.pow(aXys[n].y - pXy.y, 2) + Math.pow(aXys[n].x - pXy.x, 2);

            // distance^2 of pt to begin line segmentvarlnm12= Math.pow(aXys[n - 1].y - pXy.y, 2) + Math.pow(aXys[n - 1].x - pXy.x, 2);

            // minimum distance^2 of pt to infinite linevardist2= Math.pow(dist, 2);

            // calculated length^2 of line segmentvarcalcrl2= ln2 - dist2 + lnm12 - dist2;

            // redefine minimum distance to line segment (not infinite line) if necessaryif (calcrl2 > rl2)
                dist = Math.sqrt(Math.min(ln2, lnm12));

            if ((minDist == null) || (minDist > dist)) {
                if (calcrl2 > rl2) {
                    if (lnm12 < ln2) {
                        fTo = 0;//nearer to previous point
                        fFrom = 1;
                    }
                    else {
                        fFrom = 0;//nearer to current point
                        fTo = 1;
                    }
                }
                else {
                    // perpendicular from point intersects line segment
                    fTo = ((Math.sqrt(lnm12 - dist2)) / Math.sqrt(rl2));
                    fFrom = ((Math.sqrt(ln2 - dist2)) / Math.sqrt(rl2));
                }
                minDist = dist;
                i = n;
            }
        }

        vardx= aXys[i - 1].x - aXys[i].x;
        vardy= aXys[i - 1].y - aXys[i].y;

        x = aXys[i - 1].x - (dx * fTo);
        y = aXys[i - 1].y - (dy * fTo);

    }

    return { 'x': x, 'y': y, 'i': i, 'fTo': fTo, 'fFrom': fFrom };
}

Solution 2:

Let A,B,C be double[] such that A = {x,y} of a, B = {x,y} of b, and C = {x,y} of c. If the line ab is y = mx + z, then

m = (A[1]-B[1])/(A[0]-B[0])

z = A[1] - m*A[0]

Now we need the line through c perpendicular to ab. If this line is y = m'x + z', then

m' = -1/m = (A[0]-B[0])/(B[1]-A[1])

z' = C[1] - m'*C[0]

Finally we need the intersection of these lines. We set y=y and solve

mx+z = m'x + z'

x(m-m') = z'-z

x = (z'-z)/(m-m')

y = m*x + z

D = {(z'-z)/(m-m'), m*x + z}. All that remains now is the trivial conversion to String. Hope it helps!

Solution 3:

The closest point on a line to a point can usually be determined by drawing a perpendicular line intersecting the point. To find the perpendicular slope, do the following code:

var slope = (Number(a.substring(a.indexOf(",") + 1, a.length)) //The Y coordinate of A
 - Number(b.substring(b.indexOf(",") + 1, b.length))) // The Y coordinate of B
 / (Number(a.substring(0, a.indexOf(","))) // The X coordinate of A
 - Number(b.substring(0, b.indexOf(",")))); //The Y coordinate of B

This is the slope formula (y2 - y1) / (x2 - x1) Now that we have the slope, it is easy to convert to a perpendicular slope.

var perpendicularSlope = -1 / slope;

Now, we need to apply the point-slope formula (y - y1 = slope * (x - x1)).

var newPointX = Number(c.substring(0, c.indexOf(",")); //Gets the X value of new pointvar newPointY = Number(c.substring(c.indexOf(",") + 1, c.length)); //Gets the Y value of new point//Note that in the formula provided above, y and x are not going to be assigned in code.//I'm going to bypass formatting it like that and go right to the slope intercept formvar perpendicularBValue = newPointY - perpendicularSlope * newPointX;

//Slope intercept form is y = mx + b. (m is slope and b is where the line intersects the y axis)

Next, we have to get the slope intercept form of the first line.

var lineX = Number(a.substring(0, a.indexOf(",")); 
var lineY = Number(a.substring(a.indexOf(",") + 1, a.length));
var lineB = lineY - slope * newPointY;

I've created a system of equations here. To solve it, we'll have to use the transitive property (if a = b and b = c, then a = c);

var xCollision = (lineB - perpendicularBValue) / (perpendicularSlope - slope);
var yCollision = slope * xCollosion + lineB;
var d = xCollision + "," + yCollision;

I eliminated the y variables using the transitive property and conjoined the equations. Then I solved for x. I then plugged the x value in and solved for the y value. This is where the original line and the perpendicular line meet.

Remember how earlier I stated that this usually works? Since you're using line segments not lines, sometimes the closest point will be the end points. Here's how to fix the value of d

var aDistance = Math.sqrt(
    Math.pow(lineX - newPointX, 2) +
    Math.pow(lineY - newPointY, 2));
var bDistance = Math.sqrt(
    Math.pow(Number(b.substring(0, b.indexOf(",")) - newPointX, 2) +
    Math.pow(Number(b.substring(b.indexOf(",") + 1, b.length) - newPointY, 2));
var dDistance = Math.sqrt(
    Math.pow(xCollision - newPointX, 2) +
    Math.pow(yCollision - newPointY, 2));
var closestEndpoint = aDistance < bDistance ? aDistance : bDistance;
var closestPoint = closestEndpoint < dDistance ? closestEndpoint : dDistance;

I used a formula called the distance formula (square root of (x1 - x2)^2 + (y1 - y2)^2) to determine the distance between the points. I then used shorthand if statements to determine the closest point. If you need more help, just leave a comment.