# closest points on two line segments (3D)

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

## Recommended Posts

I need to find the point on a line segment that is closest to another line segment. Need this for collision detection. Anyone want to share some code? =)

##### Share on other sites
I just used this the other week:

//////////////////////////////////////////////////////////////////////////// MATHEMATICS for 3D GAME PROGRAMMING & COMPUTER GRAPHICS (second edition)// 4.1.2 Distance between 2 lines//////////////////////////////////////////////////////////////////////////		// Find closest point on both lines	// from S1 to S2 going in directions V1 and V2	CVector S1 ,S2, V1, V2;	Initilize the variables above...	and make sure V1 and V2 are normalized		CVector P1, P2;	float t1 = 0.0f, t2 = 0.0f;	float V1dotV2 = V1.dotProduct(V2);	float denom = V1dotV2 * V1dotV2 - 1.0f;	if( fabs(denom) < .0001f ){		//Lines are parallel 	}else{		float c = 1.0f / denom;		float dot1 = (S2-S1).dotProduct(V1);		float dot2 = (S2-S1).dotProduct(V2);		t1 = c * (-1.0f * dot1 + V1dotV2 * dot2);		t2 = c * (-V1dotV2 * dot1 + 1.0f * dot2);			}	P1 = S1 + t1 * V1;	P2 = S2 + t2 * V2;

##### Share on other sites
One way to solve the problem of finding the closest pair of points on two linear components is by minimizing the quadratic squared distance function. If the linear components are L0(s) = O0+sD0 and L1(t) = O1+tD1, then the squared distance function is f(s, t) = (L0(s)-L1(t)).(L0(s)-L1(t)).

Multiply through and re-arrange and you get a quadratic in s and t. If the linear components are not parallel, the graph is a parabaloid. It is always 'concave up', and the minimum is always >= 0. At the minimum point, the partial derivatives in s and t are both 0. You can set this up as two equations in two unknowns and solve for s and t.

If the linear components are parallel, there is an infinite number of st pairs that satisfy the minimization; they form a line on the st plane running beneath the graph, which is now a parabolic cylinder. In this case you can pick any value for one of the parametric values and solve for the other.

Working with rays or segments adds the complication that the minimization is constrained to a domain. The mathematical details require some thought, although in the end it still comes out to just a few lines of code per case.

I know of two references on this subject. One can be found here at Dave Eberly's site. The other is Graham's article in GPG2. IIRC Graham deals with the constraint aspect as a geometric rather than a calculus problem, so if the calculus of the edge cases is daunting that's an option to consider.

thanks alot =)

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634092
• Total Posts
3015442
×