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

`