See if a point lies on a line(vector)

Question

enter image description here

I have currently the following line in my program. I have two other whole number variables, x and y.

I wish to see if this new point(x, y) is on this line. I have been looking at the following thread:

Given a start and end point, and a distance, calculate a point along a line

I've come up with the following:

if(x >= x1 && x <= x2 && (y >= y1 && y <= y2 || y <= y1 && y >= y2))
{
    float vx = x2 - x1;
    float vy = y2 - y1;
    float mag = sqrt(vx*vx + vy*vy);
    // need to get the unit vector (direction)
    float dvx = vx/mag; // this would be the unit vector (direction) x for the line
    float dvy = vy/mag; // this would be the unit vector (direction) y for the line

    float vcx = x - x1;
    float vcy = y - y1;
    float magc = sqrt(vcx*vcx + vcy*vcy);
    // need to get the unit vector (direction)
    float dvcx = vcx/magc; // this would be the unit vector (direction) x for the point
    float dvcy = vcy/magc; // this would be the unit vector (direction) y for the point

    // I was thinking of comparing the direction of the two vectors, if they are the same then the point must lie on the line?
    if(dvcx == dvx && dvcy == dvy)
    {
        // the point is on the line!
    }
}

It doesn't seem to be working, or is this idea whack?

Its in 2D, why not simply put (x,y) in equation of line obtained from (x1,y1) and (x2,y2) ? — P0W, Nov 10 '14 at 17:43
Is `(x, y)` a point (as the title indicates) or a vector (as the question seems to indicate)? The question only really seems to make much sense if it's a point, but perhaps you're talking about whether the lines defined by two vectors intersect? — Jerry Coffin, Nov 10 '14 at 17:45
First, please state your conditions/assumptions. If you are dealing with floats, you must consider floating point inaccuracies. Direct math into formulas won't work. — dornhege, Nov 10 '14 at 17:46
@JerryCoffin a point! apologize for the inconsistent notation. — basickarl, Nov 10 '14 at 17:47
Also: Are those lines always in the first quadrant, i.e. do you have a guarantee that x1 <= x2, y1 <= y2. Otherwise you condition filters all other lines. — dornhege, Nov 10 '14 at 17:47
@KarlMorrison Your question should be more specific than "It doesn't seem to be working". Does it give a compilation error? A crash? An incorrect result (I guess so)? People here have rightly guessed that your problem is caused by round-off errors, but maybe this is not the only problem. Also, you might want to specify what "on a line" means for you (i.e. what tolerance you need). — anatolyg, Nov 10 '14 at 18:37

Mike Seymour · Answer 1 · 2014-11-10T18:22:51.147

Floating point numbers have a limited precision, so you'll get rounding errors from the calculations, with the result that values that should mathematically be equal will end up slightly different.

You'll need to compare with a small tolerance for error:

if (std::abs(dvcx-dvx) < tolerance && std::abs(dvcy-dvy) < tolerance)
{
    // the point is (more or less) on the line!
}

The hard part is choosing that tolerance. If you can't accept any errors, then you'll need to use something other than fixed-precision floating point values - perhaps integers, with the calculations rearranged to avoid division and other inexact operations.

In any case, you can do this more simply, without anything like a square root. You want to find out if the two vectors are parallel; they are if the vector product is zero or, equivalently, if they have equal tangents. So you just need

if (vx * vcy == vy * vcx)  // might still need a tolerance for floating-point
{
    // the point is on the line!
}

If your inputs are integers, small enough that the multiplication won't overflow, then there's no need for floating-point arithmetic at all.

@KarlMorrison: In that case, you should be able to avoid floating-point shenanigans altogether. See my updated answer. — Mike Seymour, Nov 10 '14 at 17:57

score 1 · Answer 2 · edited Nov 10 '14 at 19:09

An efficient way to solve this problem is to use the signed area of a triangle. When the signed area of the triangle created by points {x1,y1}, {x2,y2}, and {x,y} is near-zero, you can consider {x,y} to be on the line. As others have mentioned, picking a good tolerance value is an important part of this if you are using floating point values.

bool isPointOnLine (xy p1, xy p2, xy p3) // returns true if p3 is on line p1, p2
    {
    xy va = p1 - p2;
    xy vb = p3 - p2;
    area = va.x * vb.y - va.y * vb.x;
    if (abs (area) < tolerance)
        return true;
    return false;
    }

This will let you know if {x,y} lies on the line, but it will not determine if {x,y} is contained by the line segment. To do that, you would also need to check {x,y} against the bounds of the line segment.

score 0 · Answer 3 · answered Nov 10 '14 at 17:47

First you need to calculate the equation of your line. Then see if this equation holds true for the values of x and y that you have. To calculate the equation of your line, you need to work out where it croses the y-axis and what its gradient is. The equation will be of the form y=mx+c where m is the gradient and c is the 'intercept' (where the line crosses the y-axis).

score 0 · Answer 4 · answered Nov 10 '14 at 17:49

For float values, don't use == but instead test for small difference:

if (fabs(dvcx-dvx) < delta && fabs(dvcy-dvy) < delta)

Also, you don't really need the unit vector, just the tangent:

float originalTangent = (y2 - y1) / (x2 - x1);
float newTangent = (y - y1) / (x - x1);
if (fabs(newTangent - originalTangent) < delta) { ... }

(delta should be some small number that depends on the accuracy you are expecting.)

score 0 · Answer 5 · answered Nov 10 '14 at 17:57

Given that (x, y) is actually a point, the job seems a bit simpler than you're making it.

You probably want to start by checking for a perfectly horizontal or vertical line. In those cases, you just check whether x falls between x1 and x2 (or y between y1 and y2 for vertical).

Otherwise you can use linear interpolation on x and see if it gives you the correct value for y (within some possible tolerance for rounding). For this, you'd do something like:

slope = (y2-y1)/(x2-x1);
if (abs(slope * (x - x1) - y) < tolerance)
    // (x,y) is on the line
else
    // (x,y) isn't on the line

See if a point lies on a line(vector)

5 Answers5

Linked