[metapost] Re: all intersections between two paths *

[Laurence Finston]

On Tue, 11 Jan 2005, Larry Siebenmann wrote:

>
>  > How does one arrive at the value 9 for the maximum number of intersections
>  > of other `paths' of length 1?  Is there a (relatively) simple proof, or
>  > can I look this up somewhere?
>
> Given a generic bezier degree n planar path t |--> b(t), there
> is an "implicitization" process (that goes back to Euler they
> say) [...]


Thank you for your explanation.

>
>  > Given the manipulations possible with connectors, I think it may be
>  > difficult to filter out `paths' with infinitely many intersections.
>
> I am optimistic that it can be done in some practical sense. Have
> you a specific challenge?

My specific challenge is implementing routines for finding
intersections of arbitrary three-dimensional Metafont-like
`paths' in GNU 3DLDF.  Currently, this is not possible.  I
plan to reimplement them as NURBs because of the property of
projective invariance, which the latter possess.
I am not, however, bound by the arithmetical limitations
built into MF, since I haven't tried to implement whole
number arithmetic and just use `floats' or `doubles',
depending on the value of a preprocessor macro.

>
> I assume you mean by connectors the short paths that metafont seems
> to insert to link paths that almost but not quite chain together.
> (?)

No, that's not what I meant, but I expressed myself poorly.
I should have said "given the manipulations possible with
control points."  What I meant by "connectors" was actually
"path joins", e.g.,  ".. tension a and b .."  and "direction
specifiers", which, when present, are ultimately used to
find control points.

>
> By pairs of `paths' with infinitely many intersections I imagine
> you include paths that remain very near to one another for a
> 'noticeable' stretch?

Yes.  I also think that under certain circustances, the
dimensions of the `pens' used for drawing the `paths' should
be taken into account, since the drawings of two `paths' might
intersect or become tangent although the `paths' themselves
do not.  This opens another can of worms, though.

In discussions about intersections in GNU 3DLDF,
Martijn van Manen has pointed out that the case of objects
getting very close without actually becoming tangent or
intersecting are also problematical.

Laurence