[metapost] Fwd: Re: all intersections between two paths
lfinsto1 at gwdg.de
Sun Jan 16 17:36:10 CET 2005
------ 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
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
Here I comment on discussion between Laurence Finston (LF
here) and Boguslaw Jackowski (BJ here) <B_Jackowski at
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> 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
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.
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?
More information about the metapost