[metapost] MetaFont: Unexpected behavior of intersections times

[Dan Luecking]

At 03:54 AM 4/6/2011, Boguslaw Jackowski wrote:

>Hekko, Everybody,
>
>Larry:
>>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 [...]
>
>Is it possible to construct such a quadrilateral efficiently?
>
>Dan:
>>I once had two semicircles that crossed
>>(theoretically) at the midpoint of each, and MP said
>>they did not cross.
>
>Larry:
>>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.
>
>To me also sounds strange; it was several times mentioned on this
>list that: `p intersectiontimes q = (-1,-1)' implies that the curves 
>don't touch/cross each other, although `p intersectiontimes q <> (-1, -1)'
>may sometimes occur for non-touching curves, but very close to each other.

Paths in MP can only be determined at a finite number of
values of t (2^{16} + 1) values to be exact). So they are
potentially just a very large array of pairs and there is
no such thing as curves "touching" unless some pair in one
array equals one in the other array.

MP only detects the overlap of quadrilaterals associated
to Bezier segments. This can be rather chancy if the overlap
only occurs at t=0 of one segment. This reduces to a case in
a previous post where one quadrilateral is in fact a single
point right at the edge of the (imprecise) other one.


>I'd be astonished if the former assertion was invalid. But, frankly 
>speaking, I am being astonished repeatedly... ;-)

I guarantee it happened to me. I was writing the MP/MF
support (grafbase.mp/mf) for mfpic to implement something
like cutbefore. Initially I used cutbefore directly, and two
curves that definitely intersected were not cut. They were
either two circular arcs (not actually semicircles as I
previously said, but grafbase defines arcs in more-or-less
the same way as plain.mp defines quartercircle, etc., but
they end up with ceiling(total_angle/45) nodes.)

The failure to find their intersection was a serious problem.
I did some experiments and found that even though MF/MP failed
to detect the paths intersection, it sometimes found that
subpaths DID intersect! I looked into the code and found
that MF/MP seemed to be a little bit less picky about the
endpoints (point 0 of p and point length p of p) of a path.

The actual point of intersection in the problem case was at
a non-endpoint node, so I implemented my modified cutbefore
using, instead of a simple
   (t,u) := p intersectiontimes;
the code
   for n=1 upto length p:
     (t,u) := subpath (0,n) of p intersectiontimes q;
     exitif t > -1;
   endfor

Since then I have lost the test case that produced the
problem, so I cannot provide that example.

I can assure you that I spent literally days working on
this. That is time I most certainly wouldn't have spent if
the problem case had not arisen. I guess it is possible
that changes in MP since then have removed some sort of bug
that I triggered. At the time it happened for both MP and MF.
Now I can't seem to create any examples.


Dan


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