[metapost] all intersections between two paths

[Dan Luecking]

At 12:51 PM 1/5/2005, you wrote:

>Unfortunately, I'm not a good enough mathematician to be able to
>tell you whether `paths' of length 1 can have discontinuities,
>or whether two of them can have more than one intersection.

Paths can't have discontinuities at all. However, calculations of
points on paths *can* be discontinuous because MF's numeric resolution
is limited to 2^{-16}.

Also, there are cases where an intersection is not detected (by 
intersectiontimes) if it occurs at a node of one of the paths.

Mathematically, paths of length 1 can intersect as many as 9 times.
Actually, infinitely many if they happen to be dependent. For example,
(0,0)--(1,0) and (1/3,0)--(2/3,0).

>path a, b;
>
>a = [...]
>b = [...]
>
>length_a = length a;
>length_b = length b;
>
>pair p[];
>
>ctr = 0;
>
>for i = 0 upto length_a - 1:
>    for j = 0 upto length_b - 1:

You can save length_a subtraction operations if you set length_b =
length b - 1 and use that here.

>       p[ctr] = subpath (i, i + 1) of a intersectionpoint
>                subpath (j, j + 1) of b;

Just replace this with a routine that computes all intersections and
you have it. Reducing to subpaths of length 1 has the advantage of
making the time-matching consistent (see my earlier response to Antonio),
so the code will be easier.

I would do a binary search within such segments. If I have the time
(and someone doesn't do it before me) I'll try to produce some actual
code.

>       ctr = incr ctr;

Skip this step if they don't intersect.

>    endfor;
>endfor;


Dan


Daniel H. Luecking
Department of Mathematical Sciences
University of Arkansas