Sign in to follow this  

point belongs to line in 3D

This topic is 4736 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

Hello! I need help with an algorithm that is supposed to determine if a point belongs to a line in 3D. I was trying to rewrite the "school" algorithm. Let A = [ax, ay, az] and p: x = px + ux*t y = py + uy*t z = pz + uz*t ; t is parameter The point A belongs to line p if ax = px + ux*t ay = py + uy*t az = pz + uz*t There are 7 possible cases of vector u (u cannot be [0,0,0]). The general algorithm would first need to determine which case it is and then proceed accordingly. For example: 1) (ux != 0) and (uy != 0) and (uz != 0) --> you have to express the parameter from all three equations and compare them with each other. 2) (ux != 0) and (uy = 0) and (uz = 0) --> the parameter is missing in the second and third equation. These propositions must be true (ay = py) and (az = pz). 3) (ux != 0) and (uy != 0) and (uz = 0) --> you have to express the parameter from first and second equation. The parameters must be equal. And the proposition (az = pz) must be true. 4)..7) are similar This solution has a big nested if-then-else command at the beginning to determine what to do. My question is if there is a better solution for this problem, without all this branching. Thanks for help.

Share this post


Link to post
Share on other sites
maybe use an implicit equation:

if i remember correctly: (x-x1)/u = (y-y1)/v = (z-z1)/w

(x1, x2, x3) point on line
(u, v, w) direction

this reduces to 2 equation, just fill your point and see you become 0 (or near 0)

edit: actually you have also to check if u or v or w is 0: same problem as yours
don't think you will get away without if's

Share this post


Link to post
Share on other sites
The next problem you will have is that on computer, in most cases point that "should be" on the line will not be on the line because of roundoff errors. I never encountered a single task that really required point-on-line test, never. Usually what you really need is to know if point is inside some cone, or inside some cylinder, or other meaningfull thing, but not line.

So:

By Pythagoras theorem, distance between line P+t*D and point A is equal to
sqrt(|A-P|2-((A-P).D)2)
where "." is vector dot product , and D is unit-length(that is, normalized) vector.

Therefore, point is inside cylinder if
|A-P|2-|(A-P).D|2 <= r2
where r is radius of cylinder. You can set this radius to be small. If you set r=0, it degenerates into point on line test, exactly what you asked for, but i suggest you not to use r=0

edit: in case you don't understand notation i've used, |Q|2=Qx2+Qy2+Qz2

Share this post


Link to post
Share on other sites

This topic is 4736 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this