[metapost] precision of division

[Dan Luecking]

At 05:21 PM 10/10/2006, you wrote:
>On 10/10/06, Dan Luecking <luecking at uark.edu> wrote:
>>MP may decide that paths do
>>intersect which actually do not, and vice versa.
>
>That's really annoying. Should be fixed.

It can't be. The best one can do is raise the level of arithmetic
precision and reduce the number of cases where it happens. It is
a consequence of the fact that, while curves are theoretically
smooth and continuous, their computer representations are necessarily
discrete and imprecise.


>>One should never actually rely on MP to detect that paths intersect
>>except in one circumstance: if the paths intersect transversally
>>(i.e., not tangentially) at a points on each that are strictly between
>>nodes (i.e., at non-integer times). Even then the points of
>>intersection that one obtains need not be strictly equal.
>
>Ah-a! You have done some studies on this subject, right?
>Would you be so kind as to provide a predictable implementation of a
>intersectionpoint macro?

There can be no such thing (predictable, I mean). However, there is
a technique that tends to reduce the _likelyhood_ of _some_ errors.

Some background: MP (and MF) determine the intersection of two paths p
and q by examining pairs of segments:
   subpath (i,i+1) of p  versus  subpath(j,j+1) of q
Thus we can consider only single Bezier segments between integer
times. MP (or MF) check whether the convex quadrilaterals determined
by the control points intersect. If so, both segments are split into
two segments and the process repeated on each possible pair.

Because of finite precision, it can be difficult to detect the
intersection of these quadrilaterals if it happens at a single
corner. If this happens, it typically happens at an endpoint of
the segment (an integer time point of the original curve). MP
therefore treats these points slightly differently from others,
but I confess I couldn't figure out exactly what was going on.
It also seems (but I can't be sure) that endpoints of paths are
treated differently from a segment endpoint that is internal to
the path.

I encountered two problem with MP's results: sometimes it failed to
detect an intersection, and sometimes, when there are more than one,
it found the wrong one. What does that mean "the wrong one"? Well, the
MFbook (which also documents MP's behavior) says that
   p intersectiontimes q
is supposed to find the first intersection point on p (provided different
intersections occur in different segments). But sometimes I get a later
one when the first intersection is at an integer time.

I came up with the following loop trying to force MP to find the first
one. Surprisingly, it sometimes causes intersections to be found where
a simple "p intersectiontimes q" produces none.

%%% begin code snippet
% _Xtime and _Ytime will store the times of
% intersection for later use:
numeric _Xtime, _Ytime;

% "intersects" returns true if intersectiontimes finds one:
tertiarydef a intersects b =
   begingroup
     thetimes := a intersectiontimes b;
     _Xtime := xpart thetimes;
     _Ytime := ypart thetimes;
     (_Xtime > -1)
   endgroup
enddef;
%...
% loop through the segments of p:
n := length p;
for k = 1 upto n:
   exitif (subpath (0,k) of p) intersects q;
endfor
% then test
if _Xtime = -1:
   % they don't intersect (probably).
else:
   % they do (probably).
fi


Dan


Daniel H. Luecking
Department of Mathematical Sciences
University of Arkansas
"I reject your reality, and substitute my own." -- Adam Savage