[metapost] Re: all intersections between two paths * (fwd)
Laurence Finston
lfinsto1 at gwdg.de
Tue Jan 11 12:17:50 CET 2005
---------- 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?
More information about the metapost
mailing list