[metapost] Re: all intersections between two paths (fwd)

[Laurence Finston]

Forwarded to `metapost at tug.org' at Larry Siebenmann's request.

Laurence Finston

---------- Forwarded message ----------
Date: Tue, 11 Jan 2005 00:33:48 -0500
From: Larry Siebenmann <laurent at math.toronto.edu>
To: hoffmasv at imail.de, laurent at math.toronto.edu, lcs at math.toronto.edu,
     lfinsto1 at gwdg.de, metafont at ens.fr
Subject: Re: all intersections between two paths



Jacko wrote,

 > Convincing ;-) I reworked the examples and now the archive has 5.5kB.
 >
 > Laurence> Would your algorithm be extensible for use with other forms of
 > Laurence> spline curve, in particular NURBs?
 >
 > No idea. I'm out of math business since long time. I'd ask Larry
 > Siebenmann...

Suppose we are seeking the self-intersections of a map f : X
--> Y. Say when Y=R^2, and X is two intervals, while f is
b'ezier of degree n on each.

The binary search method that Knuth chose to seek intersections
is exceedingly general. The key prerequisite to start
programming a 'solver' is to have a fast routine giving a small
easily prescribed set |S| in Y that contains the image f(S) of
a nice small set S.

The nice sets S in the case at hand are all the closed
subintervals of X.  The de Casteljau observation that f(S) then
lies in the convex hull of the n+1 control points for f on S is
just what we need! This works in all degrees and all
dimensions.

Who knows of nice implementations in math and graphics environments?
Not I. There is considerable distance between theory and practice.  The
best method really available may be to
 --- approximate by bezier cubics
 --- apply the metafont intersection algorithm
 --- check out candidates solutions

There are some simplest rational splines to which the Casteljau
observation can be extended.  At levels of generality beyond that I
know almost nothing of use.

Cheers

Laurent Siebenmann (Larry)