🚀 go-pugleaf

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)