Jump to content
  • Advertisement
Sign in to follow this  
PunaProgrammer chris

Checking if a point is on a line in 3D space

This topic is 4495 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi. I would like to know how to check if a point (which is represnted by a Vector containing the x, y, and z coordiantes) is directly between two other points in 3D space. Google doesn't seem to be coming up with any real helpful results, and I know this is probably something quite simple, so I figured I might as well ask. If you can help, I would really appreciate it.

Share this post


Link to post
Share on other sites
Advertisement
Lemme make sure I understand the problem. If you have two points and (I assume) they form a line segment in three dimensional space, you want to see if a third point is on that line segment.

If the two points do form a line, then they should be scalar multiples of each other. If the third point / vector is on that line, it should also be a scalar multiple of one of those points. Thus, to see if the third point / vector is on the line segment, you need to determine if it is greater than the point closest to the origin and less than the point furthest away from the origin. You can do this by comparing the components of the vectors.

I hope that helps.

Edit: I just want to add that I am thinking in terms of vector spaces. I don't know if that applies to your situation because your two points may not be in the same vector space, and thus the above information won't work.

Share this post


Link to post
Share on other sites
Given the limits of floating-point precision, a point will rarely lie exactly on a line (in 2D or 3D). The best approach is to instead find the distance from the point to the line (or ray or segment), and see if it's below some threshold.

Google 'distance point line' to find out how to do this. Post back here if you get stuck on anything.

Share this post


Link to post
Share on other sites
I wasn't think in terms of vector spaces, but your solution should work with a little modification (I think). If I subtract from the x, y, and z coordiantes from the point that isn't an endpoint line so that it lies at origin, then I subtract the same amounts from the x, y, and z of my other 2 points, then if they are opposite sides of the origin and are scalar mutilples, then the point that is now at the origin is between them. I think that this makes sense, I'm not really sure though, I'll try it out and see it it works. Thanks for the help.

Share this post


Link to post
Share on other sites
How about the parametric representation of a line where:
L(t) = A + bt
where A is the starting point of a line which goes from A to B and b is the vector representing that line as in b = B - A so then:
L(0) = A, since A + (b * 0) = A and
L(1) = B, since A + (b * 1) = B the full length vector starting at A and ending at B.

What does all this mean, well if a point is on that line and you solve for t for your x, y, and z then all three t's or time along the line vector should be the same or very close as jyk mentioned.

let me give you an easy example, the line from (1, 1, 1) to (3, 3, 3) how can you tell that the point (2, 2, 2) is on the line but the point (2, 3, 2) isn't on the line. Other than the fact that it's obvious enough it's also very easy to solve using the parametric representaion. L(t) = A + bt, first we need to find b which is just (3-1), (3-1), (3-1) or 2, 2, 2 so to expand out the equation it's just:
L(t) = 1 + 2t, 1 + 2t, 1 + 2t then just plug the point you want to solve for into each equation like this:
2 = 1 + 2t, 2 = 1 + 2t, 2 = 1 + 2t

it's obvious that the point 2, 2, 2 is on the line since you will get the same value of t since all three equations are the same. The point 2, 3, 2 is a different story though:
2 = 1 + 2t, 3 = 1 + 2t, 2 = 1 + 2t

as you can see the value of t from the y component will not equal 1/2 like the x and z component do so this point is not on the line.

Also when solving for line segments make sure the value of t is between 0 and 1 which is where your line segment begins and ends. If you get a value that is higher or lower than your point isn't between points A and B.

Hope this helps.

Share this post


Link to post
Share on other sites
The parametric equation is probably the best solution, but if that doesn't float your boat, you can also solve this problem with a dot product:
given A and B which form a line, and a point C which you are testing for, make two vectors
v = B - A
u = C - A
normalize these vectors, v /= mag(v), u /= mag(u), and take the dot product u(dot)v.

Remember, the dot product formula is
a(dot)b = |a||b|cos(theta), where theta is the angle between the two vectors a and b. Applying that to the above, since u and v have |v| = |u| = 1, we get u(dot)v = cos(theta). if the angle between u and v is close to 0 (that is, u and v have the same direction), then you get cos(~0) = ~0 (IIRC, but my trig isn't what it used to be, is it sin(0) = 1 or cos(0) = 1?). Either way, if you get ~0 (or if I'm wrong, ~1) from the dor product, you know that C is on the infinite extension of the line formed by A and B. To determine if it is between the two, you can just directly compair the x, y, and z coords.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!