[metapost] MetaFont: Unexpected behavior of intersections times

[laurent at math.toronto.edu]

     Concerning Knuth's algorithm for finding intersections
of two MF or MP paths, Dan Luecking mentioned (on Sat, 02
Apr 2011 16:14:57 -0500, this list) that, in reality, Knuth
applies a search algorithm for points and times of 'very
close approach', and if none exist, it says so. Under no
circumstances does Knuth's intersection algorithm prove by
itself that an intersection of the two paths exists,
whereas it can prove rigourously that none exist.

Thus, when Knuth's algorithm seems to assert points and
times for an intersection, Knuth is leaving up to us to
investigate whether this data corresponds to one (or more)
genuine intersection point(s), or whether the data merely
arises from a region of close approach of the two paths
containing no intersection.

One helpful sufficient condition for one or more genuine
intersections of the two paths p and q is this
criterion:

 ($) existence of a quadrilateral Q = ABCD (convex or not,
but embedded in the plane) such that p runs from A to C
within in Q and q runs from B to D within Q :

  D  ________________________________________  C
     \                                       |
      \                                      |
       \                                     |
        \                                    |
         \                                   |
          \                                  |
           \                                 |
            \                               /  B
             \                             /
              \                           /
               \                         /
                \                       /
                 \                     /
                  \                   /
                   \                 /
                    \               /
                     \             /
                      \           /
                       \         /
                        \       /
                         \     /
                          \   /
                           \ /

                            A

[View this figure with a constant width font.]

     In practice, I claim (without proof) that this
criterion will let you count and locate all sufficiently
transverse and nonsingular intersections of paths p' and q'
that are not very near to a path endpoint. Indeed, for any
such intersection X of p' and q' there exists,
after passage to subpaths p and q, a convex quadrilateral Q
as in ($) proving intersection of p and q at X.

 Dan Luecking > I once had two semicircles that crossed
 > (theoretically) at the midpoint of each, and MP said
 > they did not cross.

Loosely interpreted, this sounds to me like a bug, so I
would like to see a concrete example and its explanation.
It seems to contradict the claim I have just made.

Laurent S.