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.

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

Solution 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'.

Solution 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.

Solution 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)

Solution 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.

View more solutions

Comments

[Bravery Onions]

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

[ChrisW]

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.

[Sandeep Datta]

What language library is this?

[configurator]

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.

[ChrisW]

"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.

[Ryu]

+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.

[Patrick McDonald]

Fair Point (pun intended), changed them to PointF

[hussain nayak Banoth]

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.

[configurator]

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.

[ThiefMaster]

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

[nenito]

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).

[jacob]

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.

[Andy]

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.

[MSA]

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

[diegoaguilar]

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

[Leggy7]

what does exactly mean "close to 0"?

[Robin Rodricks]

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.

[Floris]

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".

[Tomas Aschan]

@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.

[IAbstract]

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.

[shakil.k]

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

[Pierre-Luc]

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