[metapost] Fwd: Re: all intersections between two paths

[Laurence Finston]

------ Forwarded message -------


From: Larry Siebenmann <laurent at math.toronto.edu>
To: B_Jackowski at GUST.org.pl, antonio.ramirez at gmail.com, elp-3dldf at gnu.org,  
laurent at math.toronto.edu, lfinsto1 at gwdg.de, metafont at ens.fr, pragma at wxs.nl
Date: Sat, 15 Jan 2005 23:34:17 -0500



Hi All,

I have a test program for intersecting bezier curves having 'sparse
intersections'; that may be what Jacko is looking for. At any rate
the approach is radically different from that in Jacko's
'intersect_curves' function.  The program dates from summer 2003 when
Richard Kinch and others discussed the same general problem on the
comp.graphics.algorithms news group.  It has never been publicly
posted. Here it is:

          http://topo.math.u-psud.fr/~lcs/graphics/

I welcome this opportunity to get it tested; there surely still are
bugs to squash. Just post here (or send me) in *simplest* MP language
any curve pairs that pose problems and lie in the scope of 
reasonable requirements.

Here is the header: 

 %%%%%% Metapost macro file "Hit.mp"
 %%%%%% FN_Hit(pp,qq) finds where composite bezier paths pp, qq intersect
 %%%%%% Examples and testbed included
 %%%% Limitations:
   %% -- Needs 'sparse' intersections 
   %%   (hence, no lingering grazing contacts, 
   %%    nor even extremely sharp angles of transverse intersection).
   %% -- Needs all intersection points distinct and maybe 1bp apart 
   %%    as met by pp when curves at page proof size.
   %% -- May require configuration for size od detail of your curves.
   %% -- May fail for over 30 intersection points since recursion used.
   %%    Workaround: break pp and qq into simple bezier paths 
   %%    (with 4 control points each) so that 9 is maximum number 
   %%    of intersection points that FN_Hit must find.
 %%%% Possible virtues:
   %%  -- No shape or *self*-intersection restrictions on pp, qq
   %%     (i.e. bezier control trilaterals have arbitrary shapes).
   %%  -- Applies to bezier curves of any degree
   %%     as soon as 'intersectiontimes' is provided for them.
 %%%% Things to do (maybe):
   %%  -- convenient listing of intersection points
   %%     (on pp, on qq, and in target plane).
   %%  -- some debugging still needed: bug reports please!
   %%  -- a tight production version with enough variable protection
   %%     (but speed seems already adequate)
   %%  -- some refinements to enlarge the 'sweet spot' in param space
   %%  -- apply tricks to use less recursion depth per intersection
   %%  -- optimization for cyclic paths
 %%%% Contact:
   %%  Laurent Siebenmann, 
   %%  Email via http://topo.math.u-psud.fr/~lcs/contact
   %%  Testbed Prototype 0 of January 2005
   %%  Updates: Read metafont at ens.fr archives or contact author.     
   %%  http://www.gutenberg.eu.org/pub/GUTenberg/archives/metafont/

There are a half dozen examples embedded.

My first example shows a cubic bezier meeting a quadratic bezier
in 4 transverse crossing points. The total turn angle can be made as
small as you want by 'yscale'ing. By playing with the control vectors
one can group the intersection points more or less at will, thus
frustrating naive recipes to split *automatically* into two segments
to which Jacko's 'intersect_curves' function directly applies.

The other examples resemble ones Jacko presented for his
'intersect_curves' function. Note that I do no preprocessing of paths
for any example.

The most problematic aspect of the program is the relatively small
'sweet spot' in the parameter space. Meaning the the parameter range
that you have to be in to make thing work. It would be *huge* for a 64
bit implementation of MF!  The key parameters to adjust are are your
drawing size and HitToleranceRatio_.

Incidentally, are there compiled versions of MP/MF that allow one to
adjust the 'input stack size' limit?  That would surely let one deal
with far more than 30 intersection points --- without segmenting
composite bezier curves before processing. Is 30 intersections already
adequate?

The idea behind the program is that if you can get one intersection
you will somehow get them all by recursion.  The main obstacle is that
without special tricks the program will give the same intersections
again and again. My trick to avoid getting into this rut is removal
of a small interval, in (say) the first curve, about any intersection
-- after it is found; this is done by drawing a (rather crude) circle of
diameter HitTolerance_ about it and excising the part of that first
curve within that circle. This costs two extra applications of
'intersectiontimes' per point found; but the cost seems affordable.
This trick (in general) breaks a bezier curve into two, and each piece
then has to be handled recursively.

'Sparse intersections' just means that this strategy works.  I could
someday attempt a definition without reference to 'Hit.mp', and try to
give useful (and machine verifiable!) sufficient conditions for this
sparseness.

Finally, apologies for the naive programming style. Maybe I should
pretend that it is just to let absolutely anyone understand the code;-)
but the truth is that I feel a complete beginner every time I start to
program again with MP!

Laurent S.

PS.  Who can offer MF substitutes for the MP functions 'ulcorner' and
'lrcorner' that I use for 'autosizing'.