views:

1396

answers:

9

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

Examples are appreciated, if possible.

A: 

Could you be more specific?

What programming language are you talking about?

What environment are you talking about?

What "lines" are you talking about? Text? What point? XY on the screen?

joshcomley
Excuse this I should have commented on the original question
joshcomley
You can still delete your post, and post the comment : )
Boris Guéry
+4  A: 
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

Gishu
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.
ChrisW
A line has no thickness.
Willie Wheeler
"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.
ChrisW
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.
ebrown
+14  A: 

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:

 Y-Intersect = - Slope * X1 / Y2;

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.

Eclipse
What language library is this?
SDX2000
It's not - it's just pseudo-code.
Eclipse
It's not even pseudo-code - it's just math.
configurator
Yeah, pretty much.
Eclipse
A: 

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

Naveen
+1  A: 
SDX2000
+2  A: 

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.

Patrick McDonald
Thank u very very much.
Wahid Bitar
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.
configurator
Fair Point (pun intended), changed them to PointF
Patrick McDonald
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.
configurator
+3  A: 

Given to 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)
Daniel Brückner
+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.
Ants Aasma
+3  A: 

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.

Dave
+1  A: 

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.

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