Archived

This topic is now archived and is closed to further replies.

CGameProgrammer

Point on a line a given distance from another point

Recommended Posts

I''m trying to find the most optimal way to find the points on a 3D line that are within "radius" units of another point. Here''s the thing: I already know the minimum distance from the point to the line. Thus I know that if that distance is greater than radius then there are zero points on the line; if the distance is equal to the radius then there is one point on the line; otherwise there are two. I need to find the point/points. I don''t know how. I also don''t know the best way to find the nearest point on a line. If I did then I could use the Pyathagorean Theorem to find out the distance away from that point that the final points are, and I''d be done. I''m not sure if that''s the fastest way to do it, however. If the above method is the one I have to use, then whats the most optimal way to get the nearest point on a line, if I already have the mindistance? ~CGameProgrammer( );

Share this post


Link to post
Share on other sites
So your vector equation for the line is
(x,y,z) = (a,b,c)*t + (x0,y0,z0)

and the point is given by (X,Y,Z). The vector from (X,Y,Z) to the nearest point on the line will be perpendicular to the vector (a,b,c).

I think you can just write the dot product

(X - a*t - x0, Y - b*t - y0, Z - c*t - z0) . (a, b, c) = 0

and then solve for t?

Share this post


Link to post
Share on other sites
Interesting suggestion. I solved the equation and got:

T = Line.Direction * (Point - Line.Endpoint) / (Line.Direction dot Line.Direction)

Because Line.Direction is normalized in my case, that simplifies to:

T = Line.Direction * (Point - Line.Endpoint)

And that is incorrect. A simple illustration makes it obvious.

However when I drew the picture I realized what an idiot I am. (I tend to forget my degree of idiocy sometimes.) It really is a simple right triangle problem. The length of the hypotenuse is the distance from Point to Line.Endpoint. The length of one of the other sides is the minimum distance that I already have. Therefore I solve for the remaining side:

C^2 = A^2 + B^2
C^2 - A^2 = B^2
B = sqrt(C^2 - A^2)

C is Length(Point - Line.Endpoint), A is MinDistance, B is "T". I can't believe this didn't occur to me before. Well hopefully this will work.

~CGameProgrammer( );

EDIT: In case you're curious, here is the steps I took in solving the equation:

(P.X - L.A*L.T - L.X, P.Y - L.B*L.T - L.Y, P.Z - L.C*L.T - L.Z) dot (L.A, L.B, L.C) = 0

(L.A * (P.X - L.A*L.T - L.X)) + (L.B * (P.Y - L.B*L.T - L.Y)) + (L.C * (P.Z - L.C*L.T - L.Z)) = 0

(L.A * P.X) - (L.A * L.A * L.T) - (L.A * L.X) +
(L.B * P.Y) - (L.B * L.B * L.T) - (L.B * L.Y) +
(L.C * P.Z) - (L.C * L.C * L.T) - (L.C * L.Z) = 0

(L.A * P.X) - (L.A * L.X) +
(L.B * P.Y) - (L.B * L.Y) +
(L.C * P.Z) - (L.C * L.Z) = (L.A * L.A * L.T) +
(L.B * L.B * L.T) +
(L.C * L.C * L.T)

(L.A * P.X) - (L.A * L.X) +
(L.B * P.Y) - (L.B * L.Y) +
(L.C * P.Z) - (L.C * L.Z) = L.T * ((L.A * L.A) + (L.B * L.B) + (L.C * L.C))

L.A * (P.X - L.X) +
L.B * (P.Y - L.Y) +
L.C * (P.Z - L.Z) = L.T * ((L.A * L.A) + (L.B * L.B) + (L.C * L.C))


[edited by - CGameProgrammer on October 31, 2002 11:36:33 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by LilBudyWizer
I'm pretty sure t=((x,y,z)-(x0,y0,z0)).(a,b,c) since (a,b,c) is a unit vector. The magnitude of the cross product of those two vectors would be the distance of the point from the line.


(Line.Position - Point) dot Line.Direction is the equation for the distance from a point to a line. If you had read my post you would see that I already knew that! That's not what I'm trying to find.

~CGameProgrammer( );

EDIT: I shouldn't say "trying" since the equations I derived do seem to work. Unfortunately the collision algorithm itself is not working perfectly correctly yet. It's amazing how tricky it is writing sphere-triangle collision detection/handling that works correctly in all cases.

[edited by - CGameProgrammer on November 1, 2002 10:50:39 PM]

Share this post


Link to post
Share on other sites
quote:
I also don''t know the best way to find the nearest point on a line. If I did then I could use the Pyathagorean Theorem to find out the distance away from that point that the final points are, and I''d be done.

That was my suggestion To find that point, you can still use the Pythagorean Theorum. You know the distance between the point and the 3D line, and you can calculate the distance between the point and a point you know to be on the 3D line somewhere else. You use the PT to find the distance from that point on the 3D line to the nearest point. Use the direction of the line to scale the distance and add to point.

Share this post


Link to post
Share on other sites
Ah. I usually jump to the last post in a topic to see if something has been solved, and since the last line of your third post - the one after the second - was in the present tense ("That's not what I'm trying to find."), I assumed that a solution hadn't been found

It's a bit more complicated than looking for present tence and stuff, but the system works... usually

[edited by - Zipster on November 1, 2002 11:50:30 PM]

Share this post


Link to post
Share on other sites
Oh, and I was wrong about the distance equation. It''s (Point - Line.Endpoint) cross Line.Direction. Cross product, not dot product.

It seems to work! Yay! The problem with the collision was apparently due to the incorrect distance formula, and also to this limitation of the Pythagorean formula used for getting the points - you can''t tell which direction to place them. In other words, because the algorithm deals with magnitudes of sides, you don''t know whether you want to place the nearest point to the left or right of Line.Endpoint, and you don''t know if you want to place the intersection point to the left or right of the nearest point.

I''ve hacked a solution by moving Line.Endpoint 1000 units away in the negative Line.Direction direction, to ensure everything is on the positive side.

~CGameProgrammer( );

Share this post


Link to post
Share on other sites
The dot product gives you one side of the right triangle and the magnitude of the cross product gives you the other, i.e. cosine and sine. You know distance and you know direction. So the nearest point is np=((p-p0).d)*d+p0. A vector from the point to the nearest point on the line is np-p. The points of intersection are np+/-sqrt(r^2-|np-p|^2))*d. If that square root is complex there is no interesection, if it is zero there is one point of intersection and otherwise there are two.

Hehe, I just can't resist. If you had of read my post...

[edited by - LilBudyWizer on November 2, 2002 11:52:05 AM]

Share this post


Link to post
Share on other sites
As I said I got it working even before you wrote your first post... but I'm calculating mindistance completely differently from you; you keep saying it's (endpoint - point) dot direction, but it's the size of the cross-product. I initially used the dot-product and it turned out to be incorrect.

~CGameProgrammer( );

EDIT: You do know that A . B indicates a dot product, right? A x B means a cross-product.

[edited by - CGameProgrammer on November 2, 2002 6:28:12 PM]

Share this post


Link to post
Share on other sites
Oh, you mean the distance from the nearest point to the circle-intersection point? I just used the Pyathagorean Theorem to find that. It works at any rate.

~CGameProgrammer( );

EDIT: Oh so I see what you were saying. With "(p-p0).d" you found the distance from the nearest point to the line's endpoint and got the point that way, and used Pythagorean's to get the distance from the external point to the nearest point. Whereas I did it the other way, using (p-p0)xd to find the distance from the external point to the nearest point, and using Pythagorean's to get the distance from the line's endpoint to the nearest point.

Of course that would mean the fastest thing would in fact be not using Pythagorean's at all and using the dot and cross products to get both vectors, since square root is slow. I'll have to try that.

[edited by - CGameProgrammer on November 2, 2002 6:54:33 PM]

Share this post


Link to post
Share on other sites
((p-p0)xd)xd+p=((p-p0).d)*d+p0=np and |(np-p)|=|(p-p0)xd|. Either way you are going to have to find the magnitude of a vector. You can find the nearest point without a square root, but not the distance of the point from the line. If you actually want to know where the intersections of the line and circle are you need the nearest point and the dot product is an easier way to find that.

Share this post


Link to post
Share on other sites