CODEWITHSUNDEEP
vectorlinepoint
otoomey
otoomey

Reputation: 999

Check if a point lies on a line vector

To get another point (r) on the line that passes through point p in the direction v we can use the following formula, and substitute any value for a:

r = p + a*v

To test if r is on the line, we must only find a value for a that satisfies. In my current implementation, I check if a is the same for each component of the vectors by reorganizing the equation for r to:

a = px - rx / vx

In code terms, this looks like the following:

boolean isPointOnLine(Vector2f r, Vector2f p, Vector2f v) {
    return (p.x - r.x) / v.x == (p.y - r.y) / v.y; 
}

However, this method does not work: If any component of v is 0, the fraction will evaluate to infinity. Hence we get an incorrect result.

How do I check if r is on the line correctly?

Upvotes: 4

Views: 6504

Answers (2)

John Alexiou
John Alexiou

Reputation: 29244

In 3D you do the following:

If a point r=(x,y,z) is on the line with p=(px,py,pz) another point on the line and v=(vx,vy,vz) the direction calculate the following

CROSS(v,r-p)=0

or by component

(py-ry)*vz - (pz-rz)*vy==0
(pz-rz)*vx - (px-rx)*vz==0
(px-rx)*vy - (py-ry)*vx==0

For the 2D version, make all z-components zero

(px-rx)*vy - (py-ry)*vx == 0

No division needed, no edge cases and simple fast multiplication.

Of course due to round-off the result will be never be exactly zero. So what you need is a formula for the minimum distance, and a check if the distance is within some tolerance

d = abs((px-rx)*vy-(py-ry)*vx)/sqrt(vx*vx+vy*vy) <= tol

Upvotes: 5

otoomey
otoomey

Reputation: 999

It turns out that the equation I had was in fact correct, the division by 0 is just an edge case that must be handled beforehand. The final function looks like this:

boolean isPointOnLine(Vector2f r, Vector2f p, Vector2f v) {
    if (v.x == 0) {
        return r.x == p.x;
    }
    if (v.y == 0) {
        return r.y == p.y;
    }
    return (p.x - r.x) / v.x == (p.y - r.y) / v.y; 
}

Upvotes: 1

Related Questions