[metapost] MetaFont: Unexpected behavior of intersections times

[Dan Luecking]

Forgot to "reply all". Here's a copy of my reply to Jacko:

>Hello, Everybody,
>
>Dan Luecking:
>>I once had two semicircles that crossed
>>(theoretically) at the midpoint of each, and MP said
>>they did not cross.
>
>The only situation I can fancy is related to the inequality:
>
>  (point t of p) transformed T <> point t of (p transformed T)
>
>rather obvious in the realm of discrete geometry.

I can clear things up now, having found further
information on my example. My memory was faulty: the
problem was not one of failing to find an intersection,
but rather of not finding the one expected from the
description in "The Metafontbook". (I still can't reproduce
the example.)

I had two paths p and q, both with length 4. The paths
intersected at two points. The times on p were t=3 and t=4
(the locations on q are irrelevant except they were not at
nodes). The second intersection was the one found by
p intersectiontimes q. It seemed to me at the time (and
still) that since the third segment of p was the first to
intersect q, it should have been the one found if "The
METAFONTbook" were correct.

Having read the relevant sections of "METAFONT, the Program",
I think I may have an explanation. The algorithm is first run
with a tolerance variable set equal to 0. Only if that doesn't
find an intersection does it run it again with a positive value
of tolerance. With zero tolerance, and finite precision, it is
quite possible there was a failure to detect the intersection
at time 3, but success at time 4. If so, the routine would not
be run with positive tolerance and the value 4 returned.

I ended up changing my code to a loop
   for n=1 upto length p:
     w := = subpath (0,n) of p intersectiontimes q;
     exitif xpart w > -1;
   endfor
which exits with xpart w = 3 because (I now think) the
calculation
   (subpath (0,3) of p) intersectiontimes q
is tried both with zero tolerance  (failing) and positive
tolerance (succeeding).

By the way the paths were actually a semicircle and a
rectangle, which is how I could determine _exactly_ where
they did (ideally) intersect. There might have beeen some
scaling involved, which would likely change the ideal points
to something approximate.

>I'm not sure
>whether Dan observed a situation of this kind.

Answer: not really. Sorry for the noise.

Dan

P.S. I also got the algorithm a bit wrong. It doesn't
check if the quadrilaterals determined by the control
points overlap. It uses the rectangular bounding box of
the control points. Much simpler and faster per iteration,
though perhaps requiring a few more iterations.

P.P.S. The method proposed by Laurent would require a means
of testing whether the paths p and q remain inside a given
quadrilateral. A sufficiant (but not necessary) condition is
that the control points all lie inside the quadrilateral.
If p and q are single Bezier links, a necessary conditions
is that this is true for subpaths in a sufficiently fine
subdivision of the paths (and I think the number of
subdivisions needed may be computable from the data).

Still, the method would seem to require the same kind of
subdivide-and-test loop that the current algorithm uses.
Since each subdivision creates a possible roundoff error
of 2^{-15} (double 2^{-16} because of the two paths), the
method would be subject to pretty much the same level of
imprecision as the current one.


Daniel H. Luecking
Department of Mathematical Sciences
Fayetteville, Arkansas
http://www-cs-faculty.stanford.edu/~knuth/iaq.html