Projection of a point on line defined by 2 points

Question

I have been trying to figure this out for sometime now..

The problem to solve..

Say I have 3 Points..

P1 ---------- P2, and P3 can be anywhere around P1 and P2

What is the formula to calculate so that P3 is interpolated onto the line between P1 and P2?

I need a formula that calculates new X,Y coordinates for P3 that falls on the line between P1 and P2..

My code as of so far..

        public Point lerp(Point P0, Point P1, Point P) 
        {
            double y1 = P0.Y + (P1.Y - P0.Y) * ((P.X - P0.X) / (P1.X - P0.X));
            double x1 = P.X;

            double y2 = P.Y;
            double x2 = P0.X + (P1.X - P0.X) * ((P.Y - P0.Y) / (P1.Y - P0.Y));

            return new Point((x1 + x2) / 2, (y1 + y2) / 2);
        }

And my reference.. http://en.wikipedia.org/wiki/Linear_interpolation

The above code gets it close, but its slightly off...

Here is the converted javascript code from Corey Ogburn

        public Point _pointOnLine(Point pt1, Point pt2, Point pt)
        {
            bool isValid = false;

            var r = new Point(0, 0);
            if (pt1.Y == pt2.Y && pt1.X == pt2.X) { pt1.Y -= 0.00001; }

            var U = ((pt.Y - pt1.Y) * (pt2.Y - pt1.Y)) + ((pt.X - pt1.X) * (pt2.X - pt1.X));

            var Udenom = Math.Pow(pt2.Y - pt1.Y, 2) + Math.Pow(pt2.X - pt1.X, 2);

            U /= Udenom;

            r.Y = pt1.Y + (U * (pt2.Y - pt1.Y));
            r.X = pt1.X + (U * (pt2.X - pt1.X));

            double minx, maxx, miny, maxy;

            minx = Math.Min(pt1.X, pt2.X);
            maxx = Math.Max(pt1.X, pt2.X);

            miny = Math.Min(pt1.Y, pt2.Y);
            maxy = Math.Max(pt1.Y, pt2.Y);

            isValid = (r.X >= minx && r.X <= maxx) && (r.Y >= miny && r.Y <= maxy);

            return isValid ? r : new Point();
        }

Answer 1

This is an old question and I found the Corey Ogburn solution quite useful. But I thought it might be helpful for others to post a less "map" version of the javascript code - which I used in canvas drawing.

export const pointOnLine = (p0, p1, q) => {

  // p0 and p1 define the line segment
  // q is the reference point (aka mouse)
  // returns point on the line closest to px

  if (p0.x == p1.x && p0.y == p1.y) p0.x -= 0.00001;

  const Unumer = ((q.x - p0.x) * (p1.x - p0.x)) + ((q.y - p0.y) * (p1.y - p0.y));
  const Udenom = Math.pow(p1.x - p0.x, 2) + Math.pow(p1.y - p0.y, 2);
  const U = Unumer / Udenom;

  const r = {
    x: p0.x + (U * (p1.x - p0.x)),
    y: p0.y + (U * (p1.y - p0.y))
  }

  const minx = Math.min(p0.x, p1.x);
  const maxx = Math.max(p0.x, p1.x);
  const miny = Math.min(p0.y, p1.y);
  const maxy = Math.max(p0.y, p1.y);

  const isValid = (r.x >= minx && r.x <= maxx) && (r.y >= miny && r.y <= maxy);

  return isValid ? r : null;
}

Answer 2

Here's some javascript code we've used here at work (a GIS company) to figure out the closest point on a line the mouse is next to in a situation where a user wants to split the line by adding a vertex to it. Should be easy to move over to C#:

function _pointOnLine(line1, line2, pt) {
    var isValid = false;

    var r = new Microsoft.Maps.Location(0, 0);
    if (line1.latitude == line2.latitude && line1.longitude == line2.longitude) line1.latitude -= 0.00001;

    var U = ((pt.latitude - line1.latitude) * (line2.latitude - line1.latitude)) + ((pt.longitude - line1.longitude) * (line2.longitude - line1.longitude));

    var Udenom = Math.pow(line2.latitude - line1.latitude, 2) + Math.pow(line2.longitude - line1.longitude, 2);

    U /= Udenom;

    r.latitude = line1.latitude + (U * (line2.latitude - line1.latitude));
    r.longitude = line1.longitude + (U * (line2.longitude - line1.longitude));

    var minx, maxx, miny, maxy;

    minx = Math.min(line1.latitude, line2.latitude);
    maxx = Math.max(line1.latitude, line2.latitude);

    miny = Math.min(line1.longitude, line2.longitude);
    maxy = Math.max(line1.longitude, line2.longitude);

    isValid = (r.latitude >= minx && r.latitude <= maxx) && (r.longitude >= miny && r.longitude <= maxy);

    return isValid ? r : null;
}

line1 is a point with a latitude and longitude to represent one of the endpoints of the line, equivalent to your P1. line2 is the other endpoint: P2. pt is your P3. This will return the point on the line that P3 is perpendicular through. If P3 is past either end of the line, this will return null which means that one of the two end points is the closest point to P3.

For clarity:

Answer 3

The problem is that you Point has integer values for X and Y and therefore you are doing integer division. Try to cast your values into float or double, do the calculations and then return them back to the integers.

Note that when you are doing this: (P1.Y - P0.Y) * ((P.X - P0.X) / (P1.X - P0.X)) you are actualy loosing the precision since the result of 5/2 is 2, not 2.5 but when your values are real numbers then 5.0/2.0 is indeed 2.5.

You should try this:

double y1 = P0.Y + (double)(P1.Y - P0.Y) * ((double)(P.X - P0.X) / (double)(P1.X - P0.X));
double x1 = P.X; //these two are implicit casts

double y2 = P.Y;
double x2 = P0.X + (double)(P1.X - P0.X) * ((double)(P.Y - P0.Y) / (double)(P1.Y - P0.Y));

return new Point((x1 + x2) / 2.0, (y1 + y2) / 2.0); //put 2.0 for any case even though x1+x2 is `double`

Also, then you are converting from double to int, decimal part of the number is automatically cut off so for instance 3.87 will become 3. Than your last line should be more precise if you could use this:

   return new Point((x1 + x2) / 2.0 + 0.5, (y1 + y2) / 2.0 + 0.5);

which will effectively round double values to the closer integer value.

EDIT:

But if you just want to find the point p3 on the line between the two points, than it is easier to use this approach:

public Point lerp(Point P0, Point P1) 
{
      double x = ((double)P0.X + P1.X)/2.0;

      double y = (double)P0.Y + (double)(P1.Y - P0.Y) * ((double)(x - P0.X) / (double)(P1.X - P0.X));
      return new Point(x + 0.5, y + 0.5);
}