[metapost] MetaFont: Unexpected behavior of intersections times

[Dan Luecking]

At 09:53 AM 4/2/2011, Nicola wrote:
>In article <BANLkTi=rfM4mAY-1XD7JgoC-exeFh80kpA at mail.gmail.com>,
>  luigi scarso <luigi.scarso at gmail.com> wrote:
>
> >
> > Given that p1 is inside p2, perhaps in this case intersectiontimes
> > correctly doesn't find any  intersection --- there are infinite
> > intersections. But I'm a bit surprised .
>
>Rounding errors? Intersectiontimes can deal with multiple intersections, but
>MetaFont certainly cannot deal with quantities at that precision. Besides,
>intersectiontimes might become numerically unstable when paths are nearly
>parallel (but since I do not know the algorithm precisely I'm just guessing).

The algorithm calculates whether or not the quadrilaterals
determined by the 4 control points of each path overlap.
If not, -1 is returned. If yes, the paths are cut in half
and the algorithm is repeated on the 4 pairs of smaller paths.
Whenever the quadrilaterals don't overlap, that pair is not
further considered. I believe this is repeated if necessary
until the time intervals are reduce to 2 or 4 times MP's
numeric precision of 2^{-16}.[*]

A one-point path has a single point for all of its controls,
so the overlap of quadrilaterals is eqivalent to that point
being inside the other quadrilateral. Whether it is judged
to be inside can depend on the bounding lines being known
accurately. The inaccuracy of a line segment is the sum of
the inaccuracies of the  endpoints. So we have three
contributions: inaccuracy in the point itself and inaccuracy
of two endpoints.

If a point is on a path (theoretically), it is probably no
better than 50-50 odds whether MP will say the one-point
path intersects that path. If path p1 exactly follows path
p2 (theoretically) then the halving used in the algorithm
reduces the calculation to paths which are hardly different
from parallel straight lines. Whether these tiny lines
are judged to cross now depends on the inaccuracies of the
4 endpoints.

Increasing the precision of MP may or may not change things
for the better: The theoretical odds of a calculated point
being exactly on an infinitely precise path is 0. The odds
at finite precision is maybe 1 in 2 for each coordinate, so
1 in 4. This if the coordinates are calculated to maximum
precision: highly unlikely as most most calculations introduce
imprecisions that combine with those of the data.

Tangent paths are even more problematic.

Finally, since MP treats a path with multiple Bezier
segments by reducing to the individual segments, if two paths
cross at an endpoint of one of those segments, whether MP
decides they intersect can (as above) depend on the accuracy
of a single point. I once had two semicircles that crossed
(theoretically) at the midpoint of each, and MP said they did
not cross.

[*] There are optimizations possible: if two narrow quadrilaterals
cross each other transversely, it is possible to deduce that the
paths cross without further subdivisions. I don't know for sure
whether MP employs such optimizations. This would not affect the
current problem, as here the quadrilaterals are narrow, but nearly
parallel.


Dan


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