petrus@alex.stacken.kth.se (Lars Petrus) (05/17/91)
Hello world! I'm doing some PostScript processing in C, and I could use your help! 1) What is the correct mathematical way to split a curve into two curves at a specified value of t? 2) What is the best way to find all intersections of two curves? "Madness is the first sign of dandruff" | Email: petrus@alex.stacken.kth.se - Dr Winston O'Boogie | Reality: Lars Petrus, Solna, Sweden
gershon%gr.utah.edu@cs.utah.edu (Elber Gershon) (05/23/91)
In article <PETRUS.91May17160853@alex.alex.stacken.kth.se> petrus@alex.stacken.kth.se (Lars Petrus) writes: > > Hello world! > > I'm doing some PostScript processing in C, and I could use your help! > >1) What is the correct mathematical way to split a curve into two curves >at a specified value of t? This is easy. Evaluate the curve at t. The left side of the evaluation is the left polygon and the right side is the right polygon. >2) What is the best way to find all intersections of two curves? This is hard. Two curves of degrees d1 and d2 intersect at most d1 * d2 times. For two cubics, which PS uses, it means they can intersects 9 times! Common methods for solving the problem uses some kind of divide and concour techniques - put a bounding box on the control polygon. if bounding boxes intersect, subdivide the two curves and recurse with the 4 sub curves, until bounding boxes are small enough. Numeric improvements (Newton Raphson!?) may be of help here. Tom Sederberg (BYU) has some papers describing new ideas in this area: 1. "Comparison of three curve intersection algorithms", Thomas W Sederberg and Scott R Parry, Computer Aided design, volume 18, number 1, jan/feb 1986. 2. "Curve intersection using Bezier clipping", T W Sederberg and T Nishita, Computer Aided Design, volume 22, number 9, nov 1990. 3. "Analytic approach to intersection of all piecewise parametric rational cubic curves", R N Goldman and T W Sederberg, Computer Aided Design, volume 19, number 6, july/aug 1987. Hope this helps. Gershon Elber Gershon gershon@cs.utah.edu 918 University village Tel: (801) 582-1807 (Home) Salt Lake City, Utah 84108-1180 Tel: (801) 581-7888 (Work)