Hi, Here is some comment on GB's intersection problem/solution from the polish mp expert Boguslaw Jackowski (those who will be in bremen next week can meet this personality). Hans

...

EHL> I implemented it by finding some intersectiontime and the recursively EHL> finding the intersectionstimes of the two subpaths (each with some EHL> neighbourhood of the first intersection point cut off). For the time EHL> being I cannot find my code, but here it is in pseude code.

EHL> When done this way, the intersection times will be sorted according to EHL> the first path.

Frankly speaking, such a procedure should belong to plain from the very beginning... Obviously, we added it in our plain_ex that we use for generating fonts (even more -- we find also common outlines).

Attached you'll find the relevant excerpt plus examples.

Incidentally, recursion seem still banned from the MF/MP realm. I complained about it some time ago, but it seems that nobody but me is hurted by this annoyin situation. Attached you'll find an example: 31-element series (in a reversed order) break down w2c mpost...

And finally, let me quote the post from Larry Siebenmann (from 30 Jun 2000):

...

I believe that value (-1,-1) for "intersectiontimes" is a 100% ironclad guarantee that its two path arguments are disjoint.

Is the converse true? That is, if "intersectiontimes" yields positive times, do the two paths necessarily intersect? NO! In writing the last post, I confirmed to my satisfaction that MP and MF report positive intersection times for paths that only come near. Start by looking at the following -- in which one of the paths is constant.

path c; pair v,w; c:=fullcircle scaled 2; v:=(1+19epsilon,0) rotated 33.1234567; w:=(1-15epsilon,0) rotated 33.1234567; show (v intersectiontimes c); show (w intersectiontimes c); v:=(1+20epsilon,0) rotated 33.1234567; w:=(1-16epsilon,0) rotated 33.1234567; show (v intersectiontimes c); show (w intersectiontimes c);

end

The log:

This is MetaPost, Version 0.641 **&Plain filetest.mp (filetest.mp

...

...

(0.47754,0.73682) (0.96869,0.7373) (-1,-1) (-1,-1) )

Thus "intersectionpoint" may return a point when the paths are disjoint. It is guaranteed only to return a point of close approach. Close approach algorithms are complicated when efficient. But they are trivial in principle and enjoy incredible generality:- indeed, since we have explicit bounds modulus of continuity, it suffices to measure image distances on a finite but fine net of points in source.

Question: Is there an *if-and-only-if* test for b'ezier curve intersection?

The answer is yes for linear segments, though in some, but not all, cases one needs exact rational arithmetic. So think of working in C.

I think you have now more comments than enough ;-)

Cheers -- Jacko

-- BOP s. c. ul. Bora-Komorowskiego 24, 80-377 Gdansk, Poland tel. (+48 58) 553 46 59, fax (+48 58) 511 03 81 bop@bop.com.pl, http://www.bop.com.pl

================================================================ Deze e-mail is door E-mail VirusScanner van Planet Internet gecontroleerd op virussen. Op http://www.planet.nl/evs staat een verwijzing naar de actuele lijst waar op wordt gecontroleerd.

------------------------------------------------------------------------- Hans Hagen | PRAGMA ADE | pragma@wxs.nl Ridderstraat 27 | 8061 GH Hasselt | The Netherlands tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com ------------------------------------------------------------------------- information: http://www.pragma-ade.com/roadmap.pdf documentation: http://www.pragma-ade.com/showcase.pdf -------------------------------------------------------------------------