How can I tell if a point belongs to a certain line?

Question

How can I tell if a point belongs to a certain line?

Examples are appreciated, if possible.

Hopi

Please be more specific. What information do you have to start with? Do you have an ordered pair of the point and an equation? – Perturbation

Answer 1

I just wrote an function which handles a few extra requirements since I use this check in a drawing application:

• Fuzziness - There must be some room for error since the function is used to select lines by clicking on them.
• The line got an EndPoint and a StartPoint, no infinite lines.
• Must handle straight vertical and horizontal lines, (x2 - x1) == 0 causes division by zero in the other answers.

private const double SELECTION_FUZZINESS = 3;

internal override bool ContainsPoint(Point point)
{
    LineGeometry lineGeo = geometry as LineGeometry;
    Point leftPoint;
    Point rightPoint;

    // Normalize start/end to left right to make the offset calc simpler.
    if (lineGeo.StartPoint.X <= lineGeo.EndPoint.X)
    {
        leftPoint   = lineGeo.StartPoint;
        rightPoint  = lineGeo.EndPoint;
    }
    else
    {
        leftPoint   = lineGeo.EndPoint;
        rightPoint  = lineGeo.StartPoint;
    }

    // If point is out of bounds, no need to do further checks.                  
    if (point.X + SELECTION_FUZZINESS < leftPoint.X || rightPoint.X < point.X - SELECTION_FUZZINESS)
        return false;
    else if (point.Y + SELECTION_FUZZINESS < Math.Min(leftPoint.Y, rightPoint.Y) || Math.Max(leftPoint.Y, rightPoint.Y) < point.Y - SELECTION_FUZZINESS)
        return false;

    double deltaX = rightPoint.X - leftPoint.X;
    double deltaY = rightPoint.Y - leftPoint.Y;

    // If the line is straight, the earlier boundary check is enough to determine that the point is on the line.
    // Also prevents division by zero exceptions.
    if (deltaX == 0 || deltaY == 0) 
        return true;

    double slope        = deltaY / deltaX;
    double offset       = leftPoint.Y - leftPoint.X * slope;
    double calculatedY  = point.X * slope + offset;

    // Check calculated Y matches the points Y coord with some easing.
    bool lineContains = point.Y - SELECTION_FUZZINESS <= calculatedY && calculatedY <= point.Y + SELECTION_FUZZINESS;

    return lineContains;            
}

Mopey

Why isnt this the accepted answer? All the others are just math and blah. This is a real world, battle-hardened function and should be preferred. I mean this is StackOverflow for gods sake, not MathOverflow. – Citify

this is the best answer thanks it works . but what would be the best value for SELECTION_FUZZINESS ?? – Achromaticity

@shakil.k, the SELECTION_FUZZINESS correspond to your line width. The smaller the value is, the greater the accuracy – Laminous

Answer 2

In the simplest form, just plug the coordinates into the line equation and check for equality.

Given:

Point p (X=4, Y=5)
Line l (Slope=1, YIntersect=1)

Plug in X and Y:

   Y = Slope * X + YIntersect
=> 5 = 1 * 4 + 1
=> 5 = 5

So yes, the point is on the line.

If your lines are represented in (X1,Y1),(X2,Y2) form, then you can calculate slope with:

 Slope = (y1 - y2) / (x1-x2)

And then get the Y-Intersect with this:

 YIntersect = - Slope * X1 + Y1;

Edit: I fixed the Y-Intersect (which has been X1 / Y1 ...)

You'll have to check that x1 - x2 is not 0. If it is, then checking if the point is on the line is a simple matter of checking if the Y value in your point is equal to either x1 or x2. Also, check that the X of the point is not 'x1' or 'x2'.

Unwatched

What language library is this? – Malpighiaceous

I would think about moving the EDIT: correction to the Y-Intersect formula over on top of the original incorrect version. Took a second reading to notice that. – Tracee

Easiest method is to compare the Math.Atan2 results from both the segment's start and end points to the subject point. See my answer below for an example. No worries about horizontal or vertical issues or how close to zero before its zero that the slope-intercept method confers. – Hooded

Answer 3

The best way to determine if a point R = (rx, ry) lies on the line connecting points P = (px, py) and Q = (qx, qy) is to check whether the determinant of the matrix

{{qx - px, qy - py}, {rx - px, ry - py}},

namely (qx - px) * (ry - py) - (qy - py) * (rx - px) is close to 0. This solution has several related advantages over the others posted: first, it requires no special case for vertical lines, second, it doesn't divide (usually a slow operation), third, it doesn't trigger bad floating-point behavior when the line is almost, but not quite vertical.

Impoverish

For a line from 0,0 to 10,10 with a point 5.1, 5.1, the determinant is zero. But the point is not on the line. – Schroeder

what does exactly mean "close to 0"? – Kosher

This is a much better answer than the "accepted" one. The only thing missing is a definition of "close to". This has to be understood in the context of the numbers being subtracted: since there are 5 subtractions, there are 5 opportunities for "significant loss of precision", meaning that it's actually somewhat hard to put a good spec on "close to". – Hannahannah

@Andy: Think again - the line from (0,0) through (10,10) can be described by the equation y = x, and all points that solve this equation lie on the line. (5.1, 5.1) solves the equation, and thus lies on the line. – Calf

Answer 4

Given two points on the line L0 and L1 and the point to test P.

               (L1 - L0) * (P - L0)
n = (P - L0) - --------------------- (L1 - L0)
               (L1 - L0) * (L1 - L0)

The norm of the vector n is the distance of the point P from the line through L0 and L1. If this distance is zero or small enough (in the case of rounding errors), the point lies on the line.

The symbol * represents the dot product.

Example

P = (5, 5)

L0 = (0, 10)
L1 = (20, -10)

L1 - L0 = (20, -20)
P  - L0 = (5, -5)

              (20, -20) * (5, -5)
n = (5, -5) - --------------------- (20, -20)
              (20, -20) * (20, -20)

              200
  = (5, -5) - --- (20, -20)
              800

  = (5, -5) - (5, -5)

  = (0, 0)

Adolpho

+1 for mentioning rounding errors. Using exact equality in floating point arithmetic will cause the other proposed solutions to fail in a lot of cases. I'm not sure about the numerical robustness of the proposed algorithm, but numerical robustness is complicated enough that if precision is important, then it's advisable to look at scientific literature on the topic. Or at least use a library where it's probable that the author has done the research. – Suitcase

I don't think that your example is correct, because after some transformations n = (p - L0) - (p - L0) and in every case you have you will get always n = (0, 0). – Pugilist

Answer 5

I think Mr.Patrick McDonald put the nearly correct answer and this is the correction of his answer:

public bool IsOnLine(Point endPoint1, Point endPoint2, Point checkPoint)
{
    return (((double)checkPoint.Y - endPoint1.Y)) / ((double)(checkPoint.X - endPoint1.X))
        == ((double)(endPoint2.Y - endPoint1.Y)) / ((double)(endPoint2.X - endPoint1.X));
}

and of course there are many other correct answers especially Mr.Josh but i found this is the best one.

Thankx for evryone.

Hopi

Gives you a div by zero if checkPoint.x == endPoint.x or if the end points have the same x value – Kbp

Answer 6

y = m * x + c

This is the equation of a line. x & y are the co-ordinates. Each line is characterized by its slope (m ) and where it intersects the y-axis (c).

So given m & c for a line, you can determine if the point (x1, y1) is on the line by checking if the equation holds for x = x1 and y = y1

Hyaluronidase

Except that this equation can't describe a vertical line, and except that you didn't mention the possibility of the line's having non-zero thickness. – Tektite

"A line has no thickness" -- It does when it's drawn on a screen (i.e. when it's a programming question): its thickness is at least one pixel, and may be more. – Tektite

I would consider a line to be 1 pixel thick (when drawing to a screen), which works with this equation. If you wanted to find if a point is in a line with X thickness you're really asking if a point is in a rectangle. – Aurangzeb

Answer 7

A 2D line is generally represented using an equation in two variables x and y here is a well known equation

Now imagine your GDI+ line is drawn from (0,0) to (100, 100) then the value of m=(0-100)/(0-100) = 1 thus the equation for your line is y-0=1*(x-0) => y=x

Now that we have an equation for the line in question its easy to test if a point belongs to this line. A given point (x3, y3) belongs to this line if it satisfies the line equation when you substitute x=x3 and y=y3. For example the point (10, 10) belongs to this line since 10=10 but (10,12) does not belong to this line since 12 != 10.

NOTE: For a vertical line the value of the slope (m) is infinite but for this special case you may use the equation for a vertical line directly x=c where c = x1 = x2.

Though I have to say I am not sure if this is the most efficient way of doing this. I will try and find a more efficient way when I have some more time on hand.

Hope this helps.

Malpighiaceous

Answer 8

If you have a line defined by its endpoints

PointF pt1, pt2;

and you have a point that you want to check

PointF checkPoint;

then you could define a function as follows:

bool IsOnLine(PointF endPoint1, PointF endPoint2, PointF checkPoint) 
{
    return (checkPoint.Y - endPoint1.Y) / (endPoint2.Y - endPoint1.Y)
        == (checkPoint.X - endPoint1.X) / (endPoint2.X - endPoint1.X);
}

and call it as follows:

if (IsOnLine(pt1, pt2, checkPoint) {
    // Is on line
}

You will need to check for division by zero though.

Barimah

This can't be right... Since point coordinates are ints, you'd have (a critical) loss of percision when the checkPoint is close to endPoint1 and far from endPoint2. Perhaps if you changed it to decimal or double it would work well for both sides, but I still wouldn't trust this equasion's exactness. – Criollo

Fair Point (pun intended), changed them to PointF – Barimah

There are two problems left: You didn't check the end of the line, so (4,6) would be between (1,2) and (3,4) according to this function, and there's the problem of precision - suppose a line goes from (1,100) to (2,200). There's not a single point in the middle with integer coordinates - the check would always be false for integer coordinates. – Criollo

java.lang.ArithmeticException: divide by zero - NOT OK – Sphingosine

As algorithm is only checking for slope ratio, parallel lines would give false positive results – Christmastide

Answer 9

Equation of the line is:

y = mx + c

So a point(a,b) is on this line if it satisfies this equation i.e. b = ma + c

Exhibit

Answer 10

As an alternative to the slope/y-intercept method, I chose this approach using Math.Atan2:

// as an extension method
public static bool Intersects(this Vector2 v, LineSegment s) {
    //  check from line segment start perspective
    var reference = Math.Atan2(s.Start.Y - s.End.Y, s.Start.X - s.End.X);
    var aTanTest = Math.Atan2(s.Start.Y - v.Y, s.Start.X - v.X);

    //  check from line segment end perspective
    if (reference == aTanTest) {
        reference = Math.Atan2(s.End.Y - s.Start.Y, s.End.X - s.Start.X);
        aTanTest = Math.Atan2(s.End.Y - v.Y, s.End.X - v.X);
    }

    return reference == aTanTest;
}

The first check reference determines the arcTan from the start point of the line segment to it's end-point. Then from the start point perspective, we determine the arcTan to the vector v.

If those values are equal, we check from the perspective of the end-point.

Simple and handles horizontal, vertical and all else in between.

Hooded