## RE: [Plib-devel] Minimum distance from line to line segment in SG

 RE: [Plib-devel] Minimum distance from line to line segment in SG From: Fay John F Contr AAC/WMG - 2004-01-28 12:23:05 Attachments: Message as HTML ```Eric, Thank you for your suggestions, but I have an algorithm already. See if this works: (1) Express the line as R = R1 + T1 u, where R1 is a point on the line, T1 is a unit direction vector, and "u" is a parametric coordinate. (2) Express the line segment as R = R2 + T2 v, where R2 is the first endpoint, T2 is the unit direction vector towards the other endpoint, and "v" is a parametric coordinate. Because this is a line segment, "v" will be limited to being between 0 and the distance between the two endpoints. (3) Express the distance (squared) between two arbitrary points on the lines as D^2 = [ ( R1 + T1 u ) - ( R2 + T2 v ) ] dot [ ( R1 + T1 u ) - ( R2 + T2 v ) ] (4) Differentiate D^2 with respect to "u" and "v" and set the derivatives to zero. This will give us two equations and two unknowns. In matrix notation, [ 1 -(T1 dot T2) ] [ u ] = [ ( R1 - R2 ) dot T1 ] [ -(T1 dot T2 ) 1 ] [ v ] [ -( R1 - R2 ) dot T2 ] (5) If the matrix is singular (meaning T1 dot T2 is 1 or -1), the two lines are parallel and the shortest distance between them is just the distance between one end of the line segment and the other line. (6) If the matrix is nonsingular, we invert it to get "u" and "v". (7) Constrain "v" to be between 0 and the distance between the endpoints of the line segments. (8) Find the distance between ( R1 + T1 u ) and ( R2 + T2 v ) -- with the constrained v -- and that is our answer. It's kind of cumbersome but I think it's robust. I have code that (I think) works. John F. Fay john.fay@... -----Original Message----- From: Eric Lavigne [mailto:lavigne@...] Sent: Tuesday, January 27, 2004 8:24 PM To: plib-devel@... Subject: Re: [Plib-devel] Minimum distance from line to line segment in SG Ignore all of this. Looking at it a second time, my method is totally dumb. The value from (3) will ALWAYS be the lowest value, so that my method would end up always computing distance to the nearest endpoint. Here's a second try. The first step is to turn the segment into a line (there's a function to do this) and use sgIsectInfLineInfLine to find a point on the extended segment which is closest to the infinite line. Next check if the point you found is on the original segment; if not then set its value to the closest endpoint. Finally compute distance from your point to the infinite line using sgDistSquaredToLineVec3. Hopefully I got it right this time. I don't like being wrong :( Eric On Tue, 2004-01-27 at 18:02, Eric Lavigne wrote: > To compute distance of line to segment: > 1)compute distance from line to one end of segment > (sqrt(sgDistSquaredToLineVec3)) > 2)compute distance from line to other end of segment > 3)compute distance from line to line > turn your segment into line using sgLineSegment3ToLine3 > actual computation performed by new function you made > 4)sort the 3 previous values and return the middle value ------------------------------------------------------- The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 3-5 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ plib-devel mailing list plib-devel@... https://lists.sourceforge.net/lists/listinfo/plib-devel ```

 RE: [Plib-devel] Minimum distance from line to line segment in SG From: Norman Vine - 2004-01-27 23:13:42 ```Eric Lavigne writes: > > I also didn't > find anything for computing the distance between two infinite lines. Umm... int sgIsectInfLineInfLine( sgVec3 dst, sgVec3 l1_org, sgVec3 l1_vec, sgVec3 l2_org, sgVec3 l2_vec ) code is in sgIsect.cxx Norman ```
 RE: [Plib-devel] Minimum distance from line to line segment in SG From: Fay John F Contr AAC/WMG - 2004-01-28 12:23:05 Attachments: Message as HTML ```Eric, Thank you for your suggestions, but I have an algorithm already. See if this works: (1) Express the line as R = R1 + T1 u, where R1 is a point on the line, T1 is a unit direction vector, and "u" is a parametric coordinate. (2) Express the line segment as R = R2 + T2 v, where R2 is the first endpoint, T2 is the unit direction vector towards the other endpoint, and "v" is a parametric coordinate. Because this is a line segment, "v" will be limited to being between 0 and the distance between the two endpoints. (3) Express the distance (squared) between two arbitrary points on the lines as D^2 = [ ( R1 + T1 u ) - ( R2 + T2 v ) ] dot [ ( R1 + T1 u ) - ( R2 + T2 v ) ] (4) Differentiate D^2 with respect to "u" and "v" and set the derivatives to zero. This will give us two equations and two unknowns. In matrix notation, [ 1 -(T1 dot T2) ] [ u ] = [ ( R1 - R2 ) dot T1 ] [ -(T1 dot T2 ) 1 ] [ v ] [ -( R1 - R2 ) dot T2 ] (5) If the matrix is singular (meaning T1 dot T2 is 1 or -1), the two lines are parallel and the shortest distance between them is just the distance between one end of the line segment and the other line. (6) If the matrix is nonsingular, we invert it to get "u" and "v". (7) Constrain "v" to be between 0 and the distance between the endpoints of the line segments. (8) Find the distance between ( R1 + T1 u ) and ( R2 + T2 v ) -- with the constrained v -- and that is our answer. It's kind of cumbersome but I think it's robust. I have code that (I think) works. John F. Fay john.fay@... -----Original Message----- From: Eric Lavigne [mailto:lavigne@...] Sent: Tuesday, January 27, 2004 8:24 PM To: plib-devel@... Subject: Re: [Plib-devel] Minimum distance from line to line segment in SG Ignore all of this. Looking at it a second time, my method is totally dumb. The value from (3) will ALWAYS be the lowest value, so that my method would end up always computing distance to the nearest endpoint. Here's a second try. The first step is to turn the segment into a line (there's a function to do this) and use sgIsectInfLineInfLine to find a point on the extended segment which is closest to the infinite line. Next check if the point you found is on the original segment; if not then set its value to the closest endpoint. Finally compute distance from your point to the infinite line using sgDistSquaredToLineVec3. Hopefully I got it right this time. I don't like being wrong :( Eric On Tue, 2004-01-27 at 18:02, Eric Lavigne wrote: > To compute distance of line to segment: > 1)compute distance from line to one end of segment > (sqrt(sgDistSquaredToLineVec3)) > 2)compute distance from line to other end of segment > 3)compute distance from line to line > turn your segment into line using sgLineSegment3ToLine3 > actual computation performed by new function you made > 4)sort the 3 previous values and return the middle value ------------------------------------------------------- The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 3-5 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ plib-devel mailing list plib-devel@... https://lists.sourceforge.net/lists/listinfo/plib-devel ```
 RE: [Plib-devel] Minimum distance from line to line segment in SG From: Norman Vine - 2004-01-28 13:58:52 ```Fay John F Contr AAC/WMG writes: > Thank you for your suggestions, but I have an algorithm already. Untested but .... see if this works Cheers Norman /* Given a point p, and a line through p0 with direction vector d, * find the closest point (p1) on the line */ void sgClosestPointToLine( sgVec3 p1, const sgVec3 p, const sgVec3 p0, const sgVec3 d ) { sgVec3 u, u1; sgSubVec3(u, p, p0); sgScaleVec3( u1, d, sgScalarProductVec3(u,d) / sgScalarProductVec3(d,d) ); sgAddVec3(p1, p0, u1); } /* given 2 lines through pX with direction vector vX * find 2 closest points * returns False if lines are parallel */ int sgPointsFromLineLine(const sgVec3 pl, const sgVec3 vl, const sgVec3 p2, const sgVec3 v2, sgVec3 pt1, sgVec3 pt2 ) { sgVec3 vtemp, vnorm; sgVec4 plane1, plane2; sgVectorProductVec3(vtemp, vl, v2); if (sgLengthSquaredVec3(vtemp) < FLT_EPSILON) { sgCopyVec3(pt1, p1); sgClosestPointToLine( pt2, p1, p2, v2 ); return FALSE; } sgVectorProductVec3(vnorm, v1, vtemp); sgNormalizeVec3(vnorm); sgmakePlane(plane1, vnorm, p1); sgVectorProductVec3(vnorm, v2, vtemp); sgNormalizeVec3(vnorm); sgmakePlane(plane2, vnorm, p2); return( sgIsectInfLinePlane(pt1, p1, v1, plane2) && sgIsectInfLinePlane( pt2, p2, v2, plane1) ); } ```
 RE: [Plib-devel] Minimum distance from line to line segment in SG From: Fay John F Contr AAC/WMG - 2004-02-02 14:39:37 Attachments: Message as HTML ```Steve, Did you get the code that I sent you (off the reflector) last week? It had a potential SG function in it to do this. It uses vectors and matrix algebra to calculate your "P" value. If anybody else is interested please say so and I can e-mail the code to you. It's embedded in the proposed "puAux" library changes but isn't at all hard to find. John F. Fay john.fay@... -----Original Message----- From: Steve Baker [mailto:sjbaker1@...] Sent: Wednesday, January 28, 2004 8:55 PM To: plib-devel@... Subject: Re: [Plib-devel] Minimum distance from line to line segment in SG Too confusing - and potentially still wrong! Here is the STANDARD method: First, you ned the PARAMETRIC form of the finite line. For a line between points (Ax,Ay,Az) and (Bx,By,Bz) you get: x = Ax + (Bx-Ax) * P y = Ay + (By-Ay) * P z = Az + (Bz-Az) * P That is to say: A set of equations that produce x, y and z from some parameter 'P' that varies from 0.0 at one end of the line to 1.0 at the other end. Now, compute the point of closest approach of the two infinite lines (we'll come back to this in a moment). Substitute that into (x,y,z) in the equations above and solve to give the value of P at that point. ie Figure out where that point is in parametric space. Now, if P for this point lies in the range 0..1 then the distance between the infinite lines is the right answer. If P is less than zero - then the answer is point A and if P is greater than one then the answer is point B. Notice that you don't need the x, y AND z of the point of closest approach of the two 3D lines - you can calculate P with any one of them providing that points A and B don't have the same value for that coordinate. This means that you could (in principle) do the 'nearest point' calculation in two dimensions. That's handy because lines ALWAYS intersect in 2D unless they are parallel. You could (in principle) find the intersection of the projection of the infinite line into Z==0 with (Ax,Ay)-->(Bx,By)...then use either the x or y coordinate to get P. The snag with that is that you might find that Ax==Bx, and Ay==By but Az!=Bz. This line cannot be intersected with the infinite line in the Z==0 plane because it has zero length in that projection. Hence, you need a test - and the one I use is to calculate abs(Ax-Bx), abs(Ay,By) and abs(Az,Bz) - and to drop whichever dimension has the smallest result. This has some advantages (even over a full 3D test) because it preserves the most possible precision in the math. Easy! ---------------------------- Steve Baker ------------------------- HomeEmail: WorkEmail: HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++\$ UL+++\$ P--- L++++\$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- ------------------------------------------------------- The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 3-5 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ plib-devel mailing list plib-devel@... https://lists.sourceforge.net/lists/listinfo/plib-devel ```
 RE: [Plib-devel] Minimum distance from line to line segment in SG From: Fay John F Contr AAC/WMG - 2004-02-02 16:53:10 Attachments: Message as HTML ```A quick look at the code shows that the function is returning a point on the line L2 in each case. The comment in the code should probably be reworded to: "or the point on line 2 closest to line 1 if they don't intersect." John F. Fay john.fay@... -----Original Message----- From: Steve Baker [mailto:sjbaker1@...] Sent: Saturday, January 31, 2004 11:25 AM To: plib-devel@... Subject: Re: [Plib-devel] Minimum distance from line to line segment in SG Eric Lavigne wrote: > The documentation at plib.sourceforge.net/sg/index.html seems to > disagree with you. Rather than halfway between the two lines, the point > dst is set to a point ON one of the lines and as close as possible to > the other. > > "Two infinite lines in 3D are unlikely to intersect - even if you > actually expect them to (because of roundoff error). Hence, this routine > sets dst to the closest point on the second line which is closest to the > first line. Return FALSE if the lines are parallel, TRUE otherwise." Hmmm - I havn't actually checked what it does - I was quoting from the source code comment at the top of the function. One or the other needs to be corrected - but I don't know which one. ---------------------------- Steve Baker ------------------------- HomeEmail: WorkEmail: HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++\$ UL+++\$ P--- L++++\$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- ------------------------------------------------------- The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 3-5 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ plib-devel mailing list plib-devel@... https://lists.sourceforge.net/lists/listinfo/plib-devel ```
 [Plib-devel] Re: Minimum distance from line to line segment in SG From: Juhana Sadeharju - 2004-02-03 19:36:02 ```>From: Steve Baker > >Now, compute the point of closest approach of the two infinite lines (we'll >come back to this in a moment). Did we come back to that? Did I miss something? >This means that you could (in principle) do the 'nearest point' calculation >in two dimensions. That's handy because lines ALWAYS intersect in 2D unless >they are parallel. You could (in principle) find the intersection of the >projection of the infinite line into Z==0 with (Ax,Ay)-->(Bx,By)...then use >either the x or y coordinate to get P. Is there something wrong there? Here is what I figured out on my own -- I could be wrong because I don't have any geometry book. 1. If d1 and d2 are the direction vectors of the lines, then calculate the cross product (the vector product) of d1 and d2. That gives vector d3 which is perpendicular to both d1 and d2. 2. Rotate the world so that d3 is parallel to Z axis. 3. Intersect the rotated lines in 2D (on XY plane). Calculate parameters (of two infinite lines) at the intersection. 4. For both lines, calculate Z coordinate at the intersection. Min distance between infinite lines is abs(z1 - z2). I see Steve skips the rotation, but in my opinion the 2D intersection doesn't work without it. Regards, Juhana ```
 RE: [Plib-devel] Minimum distance from line to line segment in SG From: Eric Lavigne - 2004-01-27 23:46:51 ```I overlooked this function. It doesn't compute distance between two infinite lines, but it would be very helpful in doing so. Use this function to find a point on one line1, then toss that point and line2 into the sgDistToLineVec3 function. This completes the solution to John's problem, now we just need to translate it into a few lines of code :) Eric On Tue, 2004-01-27 at 18:13, Norman Vine wrote: > Eric Lavigne writes: > > > > I also didn't > > find anything for computing the distance between two infinite lines. > > Umm... > > int sgIsectInfLineInfLine( sgVec3 dst, > sgVec3 l1_org, sgVec3 l1_vec, > sgVec3 l2_org, sgVec3 l2_vec ) > > code is in sgIsect.cxx > > Norman > ```
 Re: [Plib-devel] Minimum distance from line to line segment in SG From: Steve Baker - 2004-01-29 02:54:26 ```Norman Vine wrote: > Eric Lavigne writes: > >> I also didn't >>find anything for computing the distance between two infinite lines. > > > Umm... > > int sgIsectInfLineInfLine( sgVec3 dst, > sgVec3 l1_org, sgVec3 l1_vec, > sgVec3 l2_org, sgVec3 l2_vec ) > > code is in sgIsect.cxx It doesn't return the distance - it returns a point midway between the closest approach of the two lines. That may seem kinda weird - but that's what was needed in the original application. ---------------------------- Steve Baker ------------------------- HomeEmail: WorkEmail: HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++\$ UL+++\$ P--- L++++\$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- ```
 Re: [Plib-devel] Minimum distance from line to line segment in SG From: Eric Lavigne - 2004-01-31 06:03:32 ```The documentation at plib.sourceforge.net/sg/index.html seems to disagree with you. Rather than halfway between the two lines, the point dst is set to a point ON one of the lines and as close as possible to the other. "Two infinite lines in 3D are unlikely to intersect - even if you actually expect them to (because of roundoff error). Hence, this routine sets dst to the closest point on the second line which is closest to the first line. Return FALSE if the lines are parallel, TRUE otherwise." Eric Lavigne > > int sgIsectInfLineInfLine( sgVec3 dst, > > sgVec3 l1_org, sgVec3 l1_vec, > > sgVec3 l2_org, sgVec3 l2_vec ) > > > > code is in sgIsect.cxx > > It doesn't return the distance - it returns a point > midway between the closest approach of the two lines. > > That may seem kinda weird - but that's what was needed > in the original application. ```
 Re: [Plib-devel] Minimum distance from line to line segment in SG From: Steve Baker - 2004-01-31 17:31:44 ```Eric Lavigne wrote: > The documentation at plib.sourceforge.net/sg/index.html seems to > disagree with you. Rather than halfway between the two lines, the point > dst is set to a point ON one of the lines and as close as possible to > the other. > > "Two infinite lines in 3D are unlikely to intersect - even if you > actually expect them to (because of roundoff error). Hence, this routine > sets dst to the closest point on the second line which is closest to the > first line. Return FALSE if the lines are parallel, TRUE otherwise." Hmmm - I havn't actually checked what it does - I was quoting from the source code comment at the top of the function. One or the other needs to be corrected - but I don't know which one. ---------------------------- Steve Baker ------------------------- HomeEmail: WorkEmail: HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++\$ UL+++\$ P--- L++++\$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- ```