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

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

Daiseydaisi

jsfiddle.net/soulwire/UA6H5 demonstrates a great example with a visual. – Ferdinandferdinanda

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

Daiseydaisi

Answer 2

Here's a simpler solution adapted for TypeScript based on this original blog.

export function findNearestPointOnLine(px: number, py: number, ax: number, ay: number, bx: number, by: number)
{
    const atob = { x: bx - ax, y: by - ay };
    const atop = { x: px - ax, y: py - ay };
    const len = (atob.x * atob.x) + (atob.y * atob.y);
    let dot = (atop.x * atob.x) + (atop.y * atob.y);
    const t = Math.min(1, Math.max(0, dot / len));

    dot = ((bx - ax) * (py - ay)) - ((by - ay) * (px - ax));

    return { x: ax + (atob.x * t), y: ay + (atob.y * t) };
}

I extended this to handle a given rect.

export function findNearestPointOnRect(px: number, py: number, x: number, y: number, width: number, height: number)
{
    const left = x;
    const right = x + width;
    const top = y;
    const bottom = top + height;

    // top, right, bottom, left
    const { x: topX, y: topY } = findNearestPointOnLine(px, py, left, top, right, top);
    const { x: rightX, y: rightY }  = findNearestPointOnLine(px, py, right, top, right, bottom);
    const { x: bottomX, y: bottomY }  = findNearestPointOnLine(px, py, left, bottom, right, bottom);
    const { x: leftX, y: leftY }  = findNearestPointOnLine(px, py, left, top, left, bottom);

    const topD = distanceBetween(px, py, topX, topY);
    const rightD = distanceBetween(px, py, rightX, rightY);
    const bottomD = distanceBetween(px, py, bottomX, bottomY);
    const leftD = distanceBetween(px, py, leftX, leftY);

    const points: {
        side: 'top' | 'right' | 'bottom' | 'left';
        d: number;
        x: number;
        y: number;
    }[] = [
        { side: 'top', d: topD, x: topX, y: topY },
        { side: 'right', d: rightD, x: rightX, y: rightY },
        { side: 'bottom', d: bottomD, x: bottomX, y: bottomY },
        { side: 'left', d: leftD, x: leftX, y: leftY },
    ];

    points.sort((a, b) =>
    {
        if (a.d < b.d)
        {
            return -1;
        }
        if (a.d > b.d)
        {
            return 1;
        }

        return 0;
    });

    return points[0];
}

Note: If your lines or rectangle are transformed then make sure you first transform the input point down to local coordinates to make life a lot easier.

Owenism

This should be the answer. It's simpler and faster. One correction though, the second dot calculation dot = ((bx - ax) * (py - ay)) - ((by - ay) * (px - ax)) is not necessary, is not used and it gives the same result. Seems like a leftover from a previous version. – Lymphangial

Also, I would try to just answer the original question and not include extra code that is not directly related to that. It can be confusing. – Lymphangial

Answer 3

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!

Audile

Answer 4

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.

Kirov

Does this handle horizontal lines? It looks it might take the slope of the perpendicular as -1/0. – Abrade