[metapost] all intersections between two paths

[Antonio Ramirez]

For what it's worth, below is my last attempt at writing the macro,
which commits the fallacy that I explained in my previous message to
comp.text.tex , forwarded by Laurence Finston to the lists.

The problem clearly has to do with the speed of parameterization;
which suggests that this should be fixable by using the arctime and
arclength primitives of metapost (I am not sure if they exist in
metafont). However, this is inelegant and seems likely to lead to more
roundoff error than necessary. But if it works, it works... so I'll
give it a try next time I have a chance.

The (broken) macro is meant to be used as
all_intersection_times.x(p,q), whereupon
x[1],...,x[x.count] become the pairs of intersection times.

vardef all_intersection_times@#(expr p, q) =
  numeric @#count;   pair @#[];
  @#count := 0;
  save curpath; path curpath;
  save curpair; pair curpair;
  save time,_x,l; numeric l,_x,time;
  time := 0 ;
  l := length p if cycle p: - epsilon fi;
  forever:
    curpath := subpath (time,l) of p ; 
    curpair := (curpath intersectiontimes q) ;
    _x := xpart curpair ;
    exitif (_x = -1) or (_x > l) ;
    @#[(incr @#count)] := (time+_x, ypart curpair) ;
    time := time + _x +epsilon ; 
  endfor
enddef;

On Wed, 5 Jan 2005 11:47:10 +0100 (MET), Laurence Finston
<lfinsto1 at gwdg.de> 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'.
> 
> On Wed, 5 Jan 2005, Antonio Ramirez wrote:
> 
> > Laurence Finston wrote:
> > >
> > > Plain Metafont does not provide a way of doing this, so if you're trying
> > > to find the intersections of arbitrary `paths', I think iterating
> > > through the subpaths would be be your best bet.  Someone might have
> > > written a macro to solve this problem, though, so I suggest you post your
> > > query to `metafont at ens.fr' and `metapost at tug.org'.
> > >
> > > [...]
> >
> > Yeah, they are arbitrary paths. I tried my hand at it but apparently I
> > don't know enough about how subpaths are parameterized. The goal is to
> > have a macro that computes all the pairs (u,v) such that point u of p
> > equals point v of q, given paths p and q.
> >
> > 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.
> >
> 
> Off the top of my head, I suspect it has to do with the "speed" of the
> `paths'.  I think you should iterate over subpaths of length 1, but
> perhaps someone has a more clever suggestion.
> 
> Laurence
> 
> >
> > Meanwhile, thanks for your suggestions about mailing lists; I will
> > probably post my query there after reading through archives.
> >
> > Thanks,
> >
> > Antonio
> >
> 
> _______________________________________________
> metapost mailing list
> http://tug.org/mailman/listinfo/metapost
>