[metapost] all intersections between two paths

Daniel H. Luecking luecking at uark.edu
Wed Jan 5 22:46:50 CET 2005

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;
  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

More information about the metapost mailing list