From: Lazlo Toth <ArtVandals@...>

Date: Sat, 13 Dec 97 09:00:29 +1100

Date: Sat, 13 Dec 97 09:00:29 +1100

>Does anyone know the answer to these two geometry questions? Thanks to the people who posted replies to this. I got another reply from a colleague who enclosed an FAQ list from < ftp://rtfm.mit.edu/pub/faqs/graphics/algorithms-faq> and guess what... these are the third and forth FAQ's. >---------------------------------------------------------------------- >Subject 1.03: How do I find intersections of 2 2D line segments? > > This problem can be extremely easy or extremely difficult depends > on your applications. If all you want is the intersection point, > the following should work: > > Let A,B,C,D be 2-space position vectors. Then the directed line > segments AB & CD are given by: > > AB=A+r(B-A), r in [0,1] > CD=C+s(D-C), s in [0,1] > > If AB & CD intersect, then > > A+r(B-A)=C+s(D-C), or > > XA+r(XB-XA)=XC+s(XD-XC) > YA+r(YB-YA)=YC+s(YD-YC) for some r,s in [0,1] > > Solving the above for r and s yields > > (YA-YC)(XD-XC)-(XA-XC)(YD-YC) > r = ----------------------------- (eqn 1) > (XB-XA)(YD-YC)-(YB-YA)(XD-XC) > > (YA-YC)(XB-XA)-(XA-XC)(YB-YA) > s = ----------------------------- (eqn 2) > (XB-XA)(YD-YC)-(YB-YA)(XD-XC) > > Let I be the position vector of the intersection point, then > > I=A+r(B-A) or > > XI=XA+r(XB-XA) > YI=YA+r(YB-YA) > > By examining the values of r & s, you can also determine some > other limiting conditions: > > If 0<=r<=1 & 0<=s<=1, intersection exists > r<0 or r>1 or s<0 or s>1 line segments do not intersect > > If the denominator in eqn 1 is zero, AB & CD are parallel > If the numerator in eqn 1 is also zero, AB & CD are coincident > > If the intersection point of the 2 lines are needed (lines in this > context mean infinite lines) regardless whether the two line > segments intersect, then > > If r>1, I is located on extension of AB > If r<0, I is located on extension of BA > If s>1, I is located on extension of CD > If s<0, I is located on extension of DC > > Also note that the denominators of eqn 1 & 2 are identical. > > References: > > [O'Rourke] pp. 249-51 > [Gems III] pp. 199-202 "Faster Line Segment Intersection," > > >---------------------------------------------------------------------- >Subject 1.04: How do I generate a circle through three points? > > Let the three given points be a, b, c. Use _0 and _1 to represent > x and y coordinates. The coordinates of the center p=(p_0,p_1) of > the circle determined by a, b, and c are: > > A = b_0 - a_0; > B = b_1 - a_1; > C = c_0 - a_0; > D = c_1 - a_1; > > E = A*(a_0 + b_0) + B*(a_1 + b_1); > F = C*(a_0 + c_0) + D*(a_1 + c_1); > > G = 2.0*(A*(c_1 - b_1)-B*(c_0 - b_0)); > > p_0 = (D*E - B*F) / G; > p_1 = (A*F - C*E) / G; > > If G is zero then the three points are collinear and no finite-radius > circle through them exists. Otherwise, the radius of the circle is: > > r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2 > > Reference: > > [O' Rourke] p. 201. Simplified by Jim Ward. Now to wade through and make FB code from this. (Hint :-) BTW, the project is a small program for generating fabric panels as three or four sided objects and adding seam allowances. Used for sail shades and tension membrane structures where the brain dead creation program only works out the outlines. BTW2, There's a future tool idea... A tension membrane program which works costs about $200,000 (ie 100 times Quark Xpress) and most of the people with them won't sell them. There are many people involved in this line who are paying structural engineers $35,000 a time to do this work. ===snip=== ftp://rtfm.mit.edu/pub/faqs/graphics/algorithms-faq ftp://ftp.seas.gwu.edu/pub/rtfm/comp/graphics/algorithms/comp.graphics.algo rithms_Frequently_Asked_Questions http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/algorithms-faq/ faq.html The (busy) rtfm.mit.edu site lists many alternative "mirror" sites. The ohio-state site is sometimes out of date. Also can reach the FAQ from http://www.geom.umn.edu/software/cglist/, which is worth visiting in its own right. ===snip=== Thanks to anyone else who replies. CJ ========================================================================== John Clark Aeronaut Automation 30 Kennedy Place Bayview 2104 Australia Phone: 61 2 99 97 28 42 Fax: 61 2 99 79 56 15 email: ArtVandals@... Visit the web site at <http://cygnus.uwa.edu.au/~peterh/> ==========================================================================