[metafont] Re: [metapost] all intersections between two paths

[Laurence Finston]

On Wed, 5 Jan 2005, Dan Luecking wrote:

> Paths can't have discontinuities at all. However, calculations of
> points on paths *can* be discontinuous because MF's numeric resolution
> is limited to 2^{-16}.
>

Thanks for the information.  I'll have to look up the definition of
"discontinuity".  I found something in the _MFbook_ which expresses
something similar to what I was thinking:  Knuth gives an example of a
`path' of length 1 that forms a
"cusp", but indicates that one must specify the control points to achieve
this effect.

> Also, there are cases where an intersection is not detected (by
> intersectiontimes) if it occurs at a node of one of the paths.
>
> Mathematically, paths of length 1 can intersect as many as 9 times.
> Actually, infinitely many if they happen to be dependent. For example,
> (0,0)--(1,0) and (1/3,0)--(2/3,0).
>

Given the manipulations possible with connectors, I think it may be
difficult to filter out `paths' with infinitely many intersections.

How does one arrive at the value 9 for the maximum number of intersections
of other `paths' of length 1?  Is there a (relatively) simple proof, or
can I look this up somewhere?

> Just replace this with a routine that computes all intersections and
> you have it. Reducing to subpaths of length 1 has the advantage of
> making the time-matching consistent (see my earlier response to Antonio),
> so the code will be easier.

`intersectiontimes' should be used, because `intersectionpoint' signals an
error if none is found.  With `intersectiontimes', one can check whether
the result is (-1, -1).

Reversing the subpaths, finding the intersection point, if any, and
checking whether it's the same as the one found for the original subpaths
would be an easy way to check whether they have more than one intersection
point.  [This would just be the first step of the binary search suggested
by Dan Luecking.]
I think it may not be foolproof, though, because of the way MF
finds intersections of paths of length 1, i.e., using a "shuffled binary"
representation.  In this case, it might be worthwhile to convert the
subpaths to paths of length 2, so that MF will find the first intersection
point.  This may not be worth the effort though.  The points will probably
have to be compared using an "epsilon" value, since I think they might not
be _exactly_ the same.

>
> >       ctr = incr ctr;
>

`=' should be `:=', of course.  Please excuse my carelessness.


Laurence