[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:31:11 -0500



Hi All,

This thread (sparked by antonio.ramirez at gmail.com) has
been partly on the metapost at tug.org mail list which, for me,
is still a "read only" list. That's not a
huge problem since its archives are open to the whole world
at http://tug.org/pipermail/metapost/.

Here I comment on discussion between Laurence Finston (LF
here) and Boguslaw Jackowski (BJ here) <B_Jackowski at
GUST.org.pl>.

The main problem is to find, using metapost or metafont,
all the intersection points of two composite bezier cubic
paths. A useful near solution was posted by BJ last week. I
fear some of you will have to write him for a copy since I
don't see it in the archives. The function is called
'intersect_curves' and the macro package is "findoutI.mp"
assisted by "qck_sort.mp".

BJ> The crucial assumptions for the algorithm to work are: (1)
BJ> B\'ezier segments have no selfintersections and (2) two
BJ> B\'ezier segments do not intersect at more than two
BJ> points.
...
BJ> Another argument in favor of the assuption (2) is that
BJ> such an algorithm can be implemented in both MF and MP;
BJ> otherwise, as rightly pointed out Antonio, the problem
BJ> cannot be handled efficiently without arclength and
BJ> arctime operations (at least I do not know how to do it
BJ> efficiently) and these operations are missing from MF.

I seem to manage without arclength and arctime operations.

BJ> My question is: which constraints imposed on single
BJ> B\'ezier segments you would consider reasonable?

I currently favor a technical notion I call 'sparse
intersections', that I'll explain in a later post.

LF> I don't quite understand why you don't want your macros to
LF> process the `paths' until all of the resulting `paths'
LF> fulfill your two conditions.

BJ> I do want, but I don't know how to do it reliably. As you have
BJ> seen, even the question whether two curves touch each other
BJ> cannot be reliably answered. In general, I to not know how to
BJ> deal efficiently and reliably with infinitezimal artefacts. I
BJ> can agree that my knowledge about discrete geometry is
BJ> insufficient.

Unsolved problem I think -- with condition (2).  

BJ> Still, I'd bet that: give me a ``universal''
BJ> MP/MF algorithm and I'll find you a counterexample...

Well, finally, that is a boast ;-)

BJ> Needless to say, if there existed a reliable criterion that
BJ> would tell naughty paths from tidy ones, I'd be happy. No idea
BJ> whether such a criterion exists. Frankly speaking, I doubt.
BJ> But maybe I'm wrong. Therefore I asked the question about such
BJ> a criterion.

Unsolved I fear. But fragments of solution exist.

Good news (?): Two planar b'ezier cubic segments both without
inflexions and turning through \leq 180 degrees, have *at
most four* intersection points -- unless they intersect
infinitely in, which case they just parametrize overlapping
segments of the same planar locus of degree \leq 3.
(Counterexample?)

Bad news: One cannot straightforewardly do better for 90 degrees
or even eps degrees. Examples shortly.

LF> I just think it's likely that breaking up
LF> `paths' that don't fulfill them until all of the resulting
LF> `paths' do would be a good way of handling the general
LF> case.  I think it might be easier than inventing a cleverer
LF> algorithm that can handle "naughtier" `paths'.  However,
LF> maybe someone knows such an algorithm already.  On the other
LF> hand, if it fails for some cases, then it just fails.  I
LF> think it would be worthwhile to implement it even if it only
LF> handles, say, 90% of the cases.

Maybe.  But beware of above frustrating fact.

BJ> This is one of the possibilities I took into account.
BJ> Intuitively, it looked less promising than the other one,
BJ> i.e., loosening constraints. Anyway, needs re-thinking.

I too feel that loosening constraints is the better option
but I may be wrong.

LF> My specific challenge is implementing routines for finding
LF> intersections of arbitrary three-dimensional Metafont-like
LF> `paths' in GNU 3DLDF.

Are these generalized paths allowed to have dimension 2, ie to
be surface patches?  Any degrees >3 badly wanted?

Cheers

Laurent S.