Find if point lies on line segment

I have line segment defined b开发者_如何转开发y these two points: A(x1,y1,z1) and B(x2,y2,z2). I have point p(x,y,z). How can I check if the point lies on the line segment?

Find the distance of point P from both the line end points A, B. If AB = AP + PB, then P lies on the line segment AB.

AB = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1));
AP = sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1));
PB = sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y)+(z2-z)*(z2-z));
if(AB == AP + PB)
    return true;

If the point is on the line then:

(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) = (z - z1) / (z2 - z1)

Calculate all three values, and if they are the same (to some degree of tolerance), your point is on the line.

To test if the point is in the segment, not just on the line, you can check that

x1 < x < x2, assuming x1 < x2, or
y1 < y < y2, assuming y1 < y2, or
z1 < z < z2, assuming z1 < z2

First take the cross product of AB and AP. If they are colinear, then it will be 0.

At this point, it could still be on the greater line extending past B or before A, so then I think you should be able to just check if pz is between az and bz.

This appears to be a duplicate, actually, and as one of the answers mentions, it is in Beautiful Code.

in case if someone looks for inline version:

public static bool PointOnLine2D (this Vector2 p, Vector2 a, Vector2 b, float t = 1E-03f)
{
    // ensure points are collinear
    var zero = (b.x - a.x) * (p.y - a.y) - (p.x - a.x) * (b.y - a.y);
    if (zero > t || zero < -t) return false;

    // check if x-coordinates are not equal
    if (a.x - b.x > t || b.x - a.x > t)
        // ensure x is between a.x & b.x (use tolerance)
        return a.x > b.x
            ? p.x + t > b.x && p.x - t < a.x
            : p.x + t > a.x && p.x - t < b.x;

    // ensure y is between a.y & b.y (use tolerance)
    return a.y > b.y
        ? p.y + t > b.y && p.y - t < a.y
        : p.y + t > a.y && p.y - t < b.y;
}

Your segment is best defined by parametric equation

for all points on your segment, following equation holds: x = x1 + (x2 - x1) * p y = y1 + (y2 - y1) * p z = z1 + (z2 - z1) * p

Where p is a number in [0;1]

So, if there is a p such that your point coordinates satisfy those 3 equations, your point is on this line. And it p is between 0 and 1 - it is also on line segment

Here's some C# code for the 2D case:

public static bool PointOnLineSegment(PointD pt1, PointD pt2, PointD pt, double epsilon = 0.001)
{
  if (pt.X - Math.Max(pt1.X, pt2.X) > epsilon || 
      Math.Min(pt1.X, pt2.X) - pt.X > epsilon || 
      pt.Y - Math.Max(pt1.Y, pt2.Y) > epsilon || 
      Math.Min(pt1.Y, pt2.Y) - pt.Y > epsilon)
    return false;

  if (Math.Abs(pt2.X - pt1.X) < epsilon)
    return Math.Abs(pt1.X - pt.X) < epsilon || Math.Abs(pt2.X - pt.X) < epsilon;
  if (Math.Abs(pt2.Y - pt1.Y) < epsilon)
    return Math.Abs(pt1.Y - pt.Y) < epsilon || Math.Abs(pt2.Y - pt.Y) < epsilon;

  double x = pt1.X + (pt.Y - pt1.Y) * (pt2.X - pt1.X) / (pt2.Y - pt1.Y);
  double y = pt1.Y + (pt.X - pt1.X) * (pt2.Y - pt1.Y) / (pt2.X - pt1.X);

  return Math.Abs(pt.X - x) < epsilon || Math.Abs(pt.Y - y) < epsilon;
}

Or let the dotnet do the heavy lifting for you if using visual studio use a GraphicsPath

this will also allow you to add tolerances for if just clicked outside the line.

using (Drawing2D.GraphicsPath gp = new Drawing2D.GraphicsPath())
{
    gp.AddLine(new Point(x1, y1), new Point(x2, y2));

    // Make the line as wide as needed (make this larger to allow clicking slightly outside the line) 
    using (Pen objPen = new Pen(Color.Black, 6))
    {
        gp.Widen(objPen);
    }

    if (gp.IsVisible(Mouse.x, Mouse.y))
    {
        // The line was clicked
    }
}

The cross product (B - A) × (p - A) should be much much shorter than B - A. Ideally, the cross product is zero, but that's unlikely on finite-precision floating-point hardware.

I use this to calculate the distance AB between points a and b.

static void Main(string[] args)
{
        double AB = segment(0, 1, 0, 4);
        Console.WriteLine("Length of segment AB: {0}",AB);
}

static double segment (int ax,int ay, int bx, int by)
{
    Vector a = new Vector(ax,ay);
    Vector b = new Vector(bx,by);
    Vector c = (a & b);
    return Math.Sqrt(c.X + c.Y);
}

struct Vector
{
    public readonly float X;
    public readonly float Y;

    public Vector(float x, float y)
    {
        this.X = x;
        this.Y = y;
    }
    public static Vector operator &(Vector a, Vector b)  
    {
        return new Vector((b.X - a.X) * (b.X - a.X), (b.Y - a.Y) * (b.Y - a.Y));
    }
}

based on Calculate a point along the line A-B at a given distance from A

Let V1 be the vector (B-A), and V2 = (p-A), normalize both V1 and V2.

If V1==(-V2) then the point p is on the line, but preceding A, & therefore not in the segment. If V1==V2 the point p is on the line. Get the length of (p-A) and check if this is less-or-equal to length of (B-A), if so the point is on the segment, else it is past B.

This is my code which can run in WPF

    public static class Math2DExtensions
    {
        public static bool CheckIsPointOnLineSegment(Point point, Line line, double epsilon = 0.1)
        {
            // Thank you @Rob Agar           
            // (x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)
            // x1 < x < x2, assuming x1 < x2
            // y1 < y < y2, assuming y1 < y2          

            var minX = Math.Min(line.APoint.X, line.BPoint.X);
            var maxX = Math.Max(line.APoint.X, line.BPoint.X);

            var minY = Math.Min(line.APoint.Y, line.BPoint.Y);
            var maxY = Math.Max(line.APoint.Y, line.BPoint.Y);

            if (!(minX <= point.X) || !(point.X <= maxX) || !(minY <= point.Y) || !(point.Y <= maxY))
            {
                return false;
            }
            
            if (Math.Abs(line.APoint.X - line.BPoint.X) < epsilon)
            {
                return Math.Abs(line.APoint.X - point.X) < epsilon || Math.Abs(line.BPoint.X - point.X) < epsilon;
            }

            if (Math.Abs(line.APoint.Y - line.BPoint.Y) < epsilon)
            {
                return Math.Abs(line.APoint.Y - point.Y) < epsilon || Math.Abs(line.BPoint.Y - point.Y) < epsilon;
            }

            if (Math.Abs((point.X - line.APoint.X) / (line.BPoint.X - line.APoint.X) - (point.Y - line.APoint.Y) / (line.BPoint.Y - line.APoint.Y)) < epsilon)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }

    public record Line
    {
        public Point APoint { get; init; }

        public Point BPoint { get; init; }
    }

My code is in github

Thank you @Rob Agar and @MetaMapper

You could check if the point lies between the two planes defined by point1 and point2 and the line direction:

///  Returns the closest point from @a point to this line on this line.
vector3 <Type>
line3d <Type>::closest_point (const vector3 <Type> & point) const
{
    return this -> point () + direction () * dot (point - this -> point (), direction ());
}

///  Returns true if @a point lies between point1 and point2.
template <class Type>
bool
line_segment3 <Type>::is_between (const vector3 <Type> & point) const
{
    const auto closest = line () .closest_point (point);
    return abs ((closest - point0 ()) + (closest - point1 ())) <= abs (point0 () - point1 ());
}