From: Fay John F Contr AAC/WMG <john.fay@eg...>  20040128 12:23:05

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: plibdevel@... Subject: Re: [Plibdevel] 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, 20040127 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 35 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ plibdevel mailing list plibdevel@... https://lists.sourceforge.net/lists/listinfo/plibdevel 