[metapost] all intersections between two paths

[Daniel H. Luecking]

On Wed, 5 Jan 2005, Laurence Finston wrote:

> Hello Antonio,
>
> I'm posting this to the mailing lists for the following reasons:
>
> 1.  I've been a subscriber to the Metafont list for some time, and I
>     don't remember this question coming up.
>
> 2.  The Metapost list is new and I know this question hasn't come up.
>
> The question is about finding all of the intersections of two arbitrary
> `paths'.
>
> > The problem is this: say p1 is some path and I have
> >
> > p2 := subpath (t,infinity) of p1,
> >
> > then it is not always the case that (point s of p2) equals (point (s+t)
> > of p1) as seemed reasonable to me at first; somehow I need to obtain the
> > parameter time in the original path p1, but this is apparently not the
> > way to do it.

Use of infinity gives a problem with cyclic paths, one can use
(length p1) in its place. However, this has nothing to do with the
problem at hand.

If p2 = subpath (t, length p1) of p1; suppose that n = floor t;

Then the first segment of p2 is subpath (t,n+1) of p1, but
reparametrized. For the rest of p2 (s >= 1),
  point s of p2 = point n+s of p1.

The first segment of p2 is reparametrized so that
  point 0 of p2 = point t of p1;
and
  point 1 of p2 = point n+1 of p1
with linear interpolation in between (0 <= s <= 1):
  point s of p2 = point (1-s)*t + s of p1.

In summary (n = floor t):
  point s of p2 = point s[t, n + 1] of p1,  0 <= s <= 1,
                = point s + n of p1,        1 <= s <= length p2.

This is laid out in the Metafontbook (look up subpath in the index).

-- 
Dan Luecking
Dept. of Mathematical Sciences
University of Arkansas
Fayetteville, AR 72101