[metapost] all intersections between two paths
Dan Luecking
luecking at uark.edu
Wed Jan 5 23:33:05 CET 2005
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
More information about the metapost
mailing list