Find if point lays on line segment

问题:

I have line segment defined by two points A(x1,y1,z1) and B(x2,y2,z2) and point p(x,y,z). How can I check if the point lays on the line segment?

回答1:

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

回答2:

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;

回答3:

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.

回答4:

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

回答5:

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

回答6:

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

回答7:

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.

回答8:

Based on Konstantin's answer above, here is some C code to find if a point is actually on a FINITE line segment. This takes into account horizontal/vertical line segments. This also takes in to account that floating point numbers are never really "exact" when comparing them with one another. The default epsilon of 0.001f will suffice in most cases. This is for 2D lines... adding "Z" would be trivial. PointF class is from GDI+, which is basically just: struct PointF{float X,Y};

Hope this helps!

#define DEFFLEQEPSILON 0.001
#define FLOAT_EQE(x,v,e)((((v)-(e))<(x))&&((x)<((v)+(e))))

static bool Within(float fl, float flLow, float flHi, float flEp=DEFFLEQEPSILON){
    if((fl>flLow) && (fl<flHi)){ return true; }
    if(FLOAT_EQE(fl,flLow,flEp) || FLOAT_EQE(fl,flHi,flEp)){ return true; }
    return false;
}

static bool PointOnLine(const PointF& ptL1, const PointF& ptL2, const PointF& ptTest, float flEp=DEFFLEQEPSILON){
    bool bTestX = true;
    const float flX = ptL2.X-ptL1.X;
    if(FLOAT_EQE(flX,0.0f,flEp)){
        // vertical line -- ptTest.X must equal ptL1.X to continue
        if(!FLOAT_EQE(ptTest.X,ptL1.X,flEp)){ return false; }
        bTestX = false;
    }
    bool bTestY = true;
    const float flY = ptL2.Y-ptL1.Y;
    if(FLOAT_EQE(flY,0.0f,flEp)){
        // horizontal line -- ptTest.Y must equal ptL1.Y to continue
        if(!FLOAT_EQE(ptTest.Y,ptL1.Y,flEp)){ return false; }
        bTestY = false;
    }
    // found here: http://stackoverflow.com/a/7050309
    // x = x1 + (x2 - x1) * p
    // y = y1 + (y2 - y1) * p
    // solve for p:
    const float pX = bTestX?((ptTest.X-ptL1.X)/flX):0.5f;
    const float pY = bTestY?((ptTest.Y-ptL1.Y)/flY):0.5f;
    return Within(pX,0.0f,1.0f,flEp) && Within(pY,0.0f,1.0f,flEp);
}

回答9:

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

回答10:

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.

回答11:

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