find a point on a line closest to a third point ja

Question

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 for javascript, but any language or formula would still work. I know this is basic geometry, but I'm still having trouble finding a formula on google :S lol... stay in school!

var a = '48,-90';
var b = '49,-92';
var c = '48.25,-91.8';
var d = 'calculated point on line';

Answer 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 (var n = 1 ; n < aXys.length ; n++) {

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

            // length^2 of line segment 
            var rl2 = 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 segment
            var ln2 = Math.pow(aXys[n].y - pXy.y, 2) + Math.pow(aXys[n].x - pXy.x, 2);

            // distance^2 of pt to begin line segment
            var lnm12 = 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 line
            var dist2 = Math.pow(dist, 2);

            // calculated length^2 of line segment
            var calcrl2 = ln2 - dist2 + lnm12 - dist2;

            // redefine minimum distance to line segment (not infinite line) if necessary
            if (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;
            }
        }

        var dx = aXys[i - 1].x - aXys[i].x;
        var dy = 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 };
}

Answer 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!

Answer 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 point
var 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 form
var 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.