See if a point lies on a line(vector)

问题:

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?

回答1:

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.

回答2:

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.

回答3:

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

回答4:

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

回答5:

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