[metapost] Re: all intersections between two paths * (fwd)

[Laurence Finston]

---------- Forwarded message ----------
Date: Tue, 11 Jan 2005 00:33:22 -0500
From: Larry Siebenmann <laurent at math.toronto.edu>
To: hoffmasv at imail.de, laurent at math.toronto.edu, lcs at math.toronto.edu,
     lfinsto1 at gwdg.de, metafont at ens.fr
Subject: Re: all intersections between two paths *




Hi Laurence, Antonio and all,

I got wind of your curve intersection quieries via the Metafont
list. If this reply (and others) do not get to the
<metapost at tug.org> list maybe Laurence F. could relay them.


 > 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) it gives a degree n real valued polynomial B in two
variables such that the points on the bezier curve  b  are
one component of the plane locus {(x,y) \in C | B(x,y) = 0}
The points where curve b meets a degree m bezier curve t |-->
c(t) then genericly lie among the roots of the one-variable
degree m*n polynomial B(c(t)). So there are at most m*n such
points.  A reference for implicitization is Van der Waarden,
Modern Algebra, a great classic.

A useful informal source of information is the usenet
comp.graphics.algorithms group.

 > 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?

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

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

Cheers

Laurent S.

PS.  When I look closely at examples I get the feeling that today's
Metapost is a fairly blunt instrument that should be kept under
human supervision. To feel confident that metapost will almost
always give results free from roundoff artifacts overflows etc. --
without too much human intervention, it would be nice to have a 64
bit implementation of metafont/metapost. Is such a project
underway?