Finding shortest line segment between two rays / Closest Point of Approach

Question

Assuming I have two rays (or, alternately, two position vectors and 2 corresponding speed vectors), what is the fastest / most resource-efficient (i.e. no for loops etc.) way to find the shortest possible line segment connecting the two rays, OR the Closest Point of Approach (for the 2+2 vectors)? Thanks in advance!

Answer 1

Best Answer

Answer by molokh · Dec 18, 2011 at 02:23 PM

Nobody answered, and I figured on my own. Sample solution in case somebody else is interested:

 public static float ClosestTimeOfApproach(Vector3 pos1, Vector3 vel1, Vector3 pos2, Vector3 vel2)
 {
     //float t = 0;
     var dv = vel1 - vel2;
     var dv2 = Vector3.Dot(dv, dv);
     if (dv2 < 0.0000001f)      // the tracks are almost parallel
     {
         return 0.0f; // any time is ok.  Use time 0.
     }
     
     var w0 = pos1 - pos2;
     return (-Vector3.Dot(w0, dv)/dv2);
 }

 public static float ClosestDistOfApproach(Vector3 pos1, Vector3 vel1, Vector3 pos2, Vector3 vel2, out Vector3 p1, out Vector3 p2)
 {
     var t = ClosestTimeOfApproach(pos1,vel1,pos2,vel2);
     p1 = pos1 + (t * vel1);
     p2 = pos2 + (t*vel2);

     return Vector3.Distance(p1, p2);           // distance at CPA
 }

 public static Vector3 ClosestPointOfApproach(Vector3 pos1, Vector3 vel1, Vector3 pos2, Vector3 vel2)
 {
     var t = ClosestTimeOfApproach(pos1, vel1, pos2, vel2);
     if (t<0) // don't detect approach points in the past, only in the future;
     {
         return (pos1); 
     }

     return (pos1 + (t * vel1));
     
 }

Add comment · Show 4 · Share

aldonaletto · Dec 18, 2011 at 03:04 PM 2

Share

@molokh, mark your own answer as accepted (click the "check" button below the voting thumbs). This will help others to find this great solution - and may render you some up votes too!

sdgd · Mar 09, 2014 at 11:12 PM 0

Share

actually I get the resaults wrong:

 Vector3 P1;
 Vector3 P2;
 ClosestDistOfApproach(new Vector3(1, 0, 0), new Vector3(0,1,1), new Vector3(-1,0,0), new Vector3(0,1,-1),out P1,out P2);
 Debug.Log(P1 + " : " + P2); //(1.0, 0.0, 0.0) : (-1.0, 0.0, 0.0)

actually closest points are:

0,0,0 AND 0,1,0

sdgd · Mar 09, 2014 at 11:58 PM 0

Share

ok found this video:

http://www.youtube.com/watch?v=HC5YikQxwZA

explains very good.

by asking and searching around I found a solution

WilliamLeu sdgd · Feb 08, 2018 at 04:44 AM 0

Share

Yea, it took me about an hour to figure out this guy's solution wasn't correct - and I was so happy I didn't have to write one myself - which took less than to get my textbook out, search for the page and transcribe the code (before I read the comments and saw your link and then beat myself up over it).

I guess I'll chalk it up to my mentality to thinking my code's always the problem and marked solutions on Unity Answers are always checked and correct.

I took the line-to-line collision code in Christer Ericson's RealTime Collision Detection book, turned into into ray collision by unclamping the ends, and it pretty much looked exactly like that wiki's code.

Answer 2

Answer by RobSCoatsink · Oct 31, 2019 at 11:40 AM

Found this post that helped me when I couldn't get this solution to work. https://answers.unity.com/questions/759630/point-of-intersection-between-two-rays.html

The answer links to these resources (the function ClosestPointsOnTwoLines helped me out the most with my problem): http://wiki.unity3d.com/index.php/3d_Math_functions?_ga=2.104569024.1350420062.1572253629-1502904723.1553610781

Hope it helps :)

Add comment · Show 1 · Share

Rosehardt · May 05, 2021 at 06:35 PM 0

Share

This helped me, thanks for adding it!

Finding shortest line segment between two rays / Closest Point of Approach

2 Replies

Your answer

Follow this Question

Related Questions